Entropy of contact circuits and lower bounds on their complexity

Random walks, universal traversal sequences, and the complexity of maze problems

Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations

Computing, Computer Science, Mathematics +15

Bounded-width polynomial-size branching programs recognize exactly those languages in <i>NC</i>¹

David A. Mix Barrington · 1986 · 686 citations

Computing, Computer Science, Mathematics +6

Almost optimal lower bounds for small depth circuits

Johan Håstad · 1986 · 630 citations

Computing, Computer Science, Algorithms +10

Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

David A. Mix Barrington · Journal of Computer and System Sciences · 1989 · 407 citations

Computing, Computer Science, Algorithms +9

The monotone circuit complexity of boolean functions

Noga Alon, Ravi B. Boppana · COMBINATORICA · 1987 · 350 citations

Computing, Computer Science, Mathematics +14