Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KW RELATION:
Reports tagged with KW relation:
TR13-190 | 28th December 2013
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

TR19-120 | 11th September 2019
Or Meir

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

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