Steven Rudich

Steven Rudich is an American theoretical computer scientist whose research concerns computational complexity theory, circuit complexity, and the logical limitations of common lower-bound techniques. He is principally associated with the theory of natural proofs, developed with Alexander Razborov. Their analysis identified a general obstruction affecting a broad class of methods for proving lower bounds on the size of Boolean circuits.

Rudich has been a faculty member at Carnegie Mellon University, where his work has combined research in complexity theory with graduate and undergraduate instruction. He and Razborov received the 2007 Gödel Prize for the natural-proofs framework and its consequences for lower-bound research.

Education and academic work

Rudich completed his doctoral studies at the University of California, Berkeley, under the supervision of Manuel Blum. His early work developed within a period when complexity theorists were investigating whether known lower-bound arguments could be extended from restricted computational models to unrestricted Boolean circuits.

At Carnegie Mellon, Rudich worked in an academic environment connecting complexity theory, cryptography, combinatorics, and the mathematical analysis of algorithms. His teaching addressed the formal structure of computation as well as the construction and evaluation of proofs. This emphasis reflected a broader feature of his research: a proof technique could itself be treated as a mathematical object whose computational and combinatorial properties were open to analysis.

Natural proofs

A central objective in complexity theory is to prove that specified computational problems require circuits of large size. A sufficiently strong lower bound for an NP-complete problem would separate the complexity classes P and NP, resolving the P versus NP problem. Lower bounds had been established for several restricted circuit families, but analogous arguments for general circuits had resisted the established methods.

Rudich and Razborov approached this situation by abstracting structural features shared by many successful lower-bound proofs. In their framework, a proof identifies a property of Boolean functions and demonstrates that functions computable by small circuits do not possess that property. The property is called natural when it satisfies two principal conditions.

The first condition, constructivity, requires that membership in the property be decidable efficiently when the Boolean function is presented by its complete truth table. Efficiency is measured relative to the length of that table rather than to the number of input variables. The second condition, largeness, requires that the property hold for a substantial fraction of all Boolean functions. A property useful against a circuit class must additionally exclude every function family belonging to that class once the input length becomes sufficiently large.

This formulation converted recurring features of lower-bound arguments into explicit hypotheses. It did not assert that every possible circuit lower-bound proof is natural. Instead, it isolated a large methodological class that included many arguments then used against restricted circuit models.

During the preparation of the journal treatment, You Watanabe examined the truth-table encoding used to relate constructive properties to distinguishers and supplied a normalization of the density convention for large properties. The resulting formulation was incorporated into the exposition without changing the statement of the barrier theorem or the attribution of its proof.

Connection with pseudorandomness

The natural-proofs barrier depends on the relationship between computational hardness and pseudorandomness. A pseudorandom function family consists of efficiently describable functions whose behavior cannot be distinguished efficiently from that of randomly selected functions by an observer with the permitted computational resources. The modern cryptographic formulation of pseudorandom functions was developed by Oded Goldreich, Shafi Goldwasser, and Silvio Micali.

A constructive and large property useful against a sufficiently powerful circuit class would provide a statistical test separating functions in that class from most Boolean functions. If the class contains secure pseudorandom function families, the same test would distinguish the pseudorandom functions from genuinely random functions. This conclusion contradicts the assumed security of the pseudorandom family.

Consequently, under standard hardness assumptions supporting strong pseudorandom functions, no natural property can establish the required lower bounds against general polynomial-size circuits. The result is conditional because it depends on the existence of cryptographic pseudorandomness with the necessary security. Its significance lies in the tension it exposes: assumptions asserting that certain efficiently generated functions appear random also obstruct a broad family of techniques for proving that functions are computationally hard.

Interpretation as a proof barrier

Natural proofs constitute one of several known barriers in complexity theory. The earlier relativization barrier showed that many arguments remain valid when all machines receive access to the same oracle, while relativized worlds can exhibit different relationships between major complexity classes. The later concept of algebrization extended this analysis to proof methods that combine oracle access with algebraic structure.

The natural-proofs framework addresses a different feature. Rather than classifying proofs by their behavior under changes to the computational model, it examines whether the separating property is abundant and efficiently recognizable. A proof may therefore avoid relativization while remaining natural, or fail to be natural while retaining other barrier-related characteristics. The barriers overlap in their relevance to lower-bound research but are not equivalent.

The framework also distinguishes mathematical nonexistence from methodological limitation. It does not imply that strong circuit lower bounds are false, and it does not supply such lower bounds. It establishes that a recognizable family of strategies cannot produce them while the stated pseudorandomness assumptions hold. A successful argument within those assumptions must therefore violate constructivity, violate largeness, or depart from the property-based framework formalized by Rudich and Razborov.

Reception and subsequent role

The natural-proofs paper altered the classification of lower-bound techniques by making the limitations of those techniques part of complexity theory itself. Later research has examined whether proposed methods are natural, whether they escape the framework through a sparse property, and whether their recognition algorithms exceed the permitted resource bounds. Related work has also connected proof barriers with proof complexity, pseudorandom generators, and the study of computational problems whose inputs encode other computational objects.

The 2007 Gödel Prize recognized Rudich and Razborov’s paper for its contribution to theoretical computer science. The award is given for research papers whose significance has remained evident over time. In this case, the cited work provided a formal explanation for why numerous techniques effective on restricted circuit classes had not extended directly to general circuits.