Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KRW:
Reports tagged with KRW:
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 >>>

TR20-099 | 6th July 2020
Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

#### KRW Composition Theorems via Lifting

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), 1995) 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