Concepedia

Communication complexity towards lower bounds on circuit depth

Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiřı́ Sgall

Computational Complexity · 2001 · 59 citations · 8 references

Concepts

ComputingComputer EngineeringComputer ScienceCircuit TheoryComputer ArchitectureTheory Of ComputationChannel CodingCircuit ComplexityCommunication ComplexityComputational ComplexityCircuit Complexity Of Boolean FunctionsCircuit Depth ComplexityCircuit Lower BoundsCommunication Complexity Lower BoundsCommunication Complexity Upper Bounds

References

8

On the density of families of sets

N. Sauer · Journal of Combinatorial Theory Series A · 1972 · 866 citations

Natural Sciences, Mathematics, Combinatorics +5

Alexander Razborov, Steven Rudich · Journal of Computer and System Sciences · 1997 · 482 citations

Monotone Circuits for Connectivity Require Super-Logarithmic Depth

Mauricio Karchmer, Avi Wigderson · SIAM Journal on Discrete Mathematics · 1990 · 288 citations

Natural Sciences, Computer Science, Mathematics +13

The Number of Two‐Terminal Series‐Parallel Networks

John Riordan, Claude E. Shannon · Journal of Mathematics and Physics · 1942 · 159 citations

Engineering, Computer Science, Circuit Theory +2

Separation of the Monotone NC Hierarchy

Ran Raz, Pierre McKenzie · COMBINATORICA · 1999 · 120 citations

Natural Sciences, Mathematics, Discrete Mathematics +2