Computational Complexity

Non-deterministic exponential time has two-prover interactive protocols

László Babai, Lance Fortnow, Carsten Lund · 1992 · 533 citations · Full text

Computing, Computer Science, Cryptography +3

Non-deterministic exponential time has two-prover interactive protocols

László Babai, Lance Fortnow, Carsten Lund · 1991 · 459 citations

Computing, Computer Science, Cryptography +3

On the degree of boolean functions as real polynomials

Noam Nisan, Márió Szegedy · 1994 · 404 citations

Natural Sciences, Computer Science, Mathematics +9

A new recursion-theoretic characterization of the polytime functions

Stephen Cook · 1992 · 397 citations

Computing, Computer Science, Mathematics +11

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Valentine Kabanets, Russell Impagliazzo · 2004 · 384 citations

Computing, Computer Science, Mathematics +16