I'm most interested in the $2^{n-Omega(n)}$-sized circuit for inverting any efficiently computable function. An analogous result was shown by Fiat and Naor in 1991, but this was in an advice-aided ROM model. The issue at hand is implementing such algorithms in a circuit model (which has a fixed wiring). The non-triviality of the implementaion is reflected in the fact that the complexity bound obtained is infirior to the one obtained in the advice-aided ROM model.
A key ingrediant in the implementation is the construction of a circuit for performing batch computation of searching elements in a list. That is, we seek a circuit that given a list $L$ of $\ell$ elements and inputs $(x_1,...,x_m)$ returns $(b_1,...,b_m)$ such that $b_i$ indicates whether $x_i\in L$. Indeed, this generalizes the standard case of $m=1$, which has a circuit of size $\tildeO(\ell n)$, when assuming that all elements have length $n$. Using sorting tricks the general case can be solved by a circuit of size $\tildeO((\ell+m) n)$.
The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ? = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search.
In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(·), there exists of a circuit of size $2^{4n/5+o(n)}$ that solves the t(·)-bounded Kolmogorov complexity problem on every instance.
Our algorithm is black-box in the description of the Universal Turing Machine employed in the definition of Kolmogorov Complexity, and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity problem of Liu and Pass (FOCS’20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC’91). We additionally demonstrate that no such black-box algorithm can have sub-exponential circuit size.
Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size $2^{4n/5+o(n)}$; as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function.
See ECCC TR23-175.