Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DEPTH LOWER BOUNDS:
Reports tagged with Depth Lower bounds:
TR19-120 | 11th September 2019
Or Meir

Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions \$f ... more >>>

ISSN 1433-8092 | Imprint