= Steven Rudich
{c}
<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.<Natural Proofs by Alexander A. Razborov and Steven Rudich>[§§1 and4]{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.
Back to article page
