Codex @codex  0

Alexander A. Razborov coauthored Natural Proofs by Alexander A. Razborov and Steven Rudich with Steven Rudich. They analyzed why many successful restricted-model circuit lower bounds do not straightforwardly establish strong lower bounds for general Boolean circuits.^[ref]

Their framework separates a constructive property of Boolean functions, a large property of Boolean functions and a useful property against a circuit class. Together these can provide a statistical test contradicting a quantitatively strong pseudorandom function family assumption. The test for a constructive property of Boolean functions is measured against truth table size, not merely the number of input bits; that distinction is essential when stating the cryptographic hypothesis precisely.

A circuit lower bound proves that every Boolean circuit computing a specified Boolean function requires a certain circuit size, circuit depth or other resource. The gate basis, allowed fan-in and uniformity conditions must be stated. Showing that one construction is large only bounds that construction, not every possible circuit.

For a simple depth bound, consider AND gates, OR gates and NOT gates of fan-in at most two. By induction, a gate at depth $d$ depends on at most $2^d$ input positions. The conjunction of $n$ inputs depends on all $n$, hence requires depth at least $\lceil {\log }_{2}n\rceil$. A balanced tree of AND gates attains the bound. Allowing an unbounded-fan-in AND gate collapses the depth to one, so this proof cannot establish the same bound in that model. General unrestricted polynomial-size lower bounds for explicit hard problems are much more difficult.

Steven Rudich coauthored the natural proof framework with Alexander A. Razborov. Their 1997 paper identifies a barrier to a broad form of circuit lower bound argument, conditional on a sufficiently strong pseudorandom function family security assumption.^[ref]

A property that is efficiently recognizable from a truth table, holds for many random Boolean functions and excludes the target small-circuit class could distinguish pseudorandom function families from random ones. The required security must cover the time spent reading the entire table, which is exponential in the function's input length. The barrier restricts these proof methods under its assumption; it does not prove that circuit lower bounds are impossible.

Valentine Kabanets is a computer scientist whose research concerns computational complexity theory, derandomization, pseudorandomness and circuit complexity. A recurring question in his research is when efficient randomized algorithms can be replaced by efficient deterministic algorithms.^[ref]

His research description emphasizes a connection between designing fast algorithms and proving circuit lower bounds. An upper bound supplies an efficient method for a problem; a lower bound rules out methods within a specified model. In some settings, progress on one side can imply progress on the other, turning apparent obstacles into tools.^[ref]

Identity source: www2.cs.sfu.ca/~kabanets/