Steven Rudich

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.