Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KRW CONJECTURE:
Reports tagged with KRW conjecture:
TR18-160 | 12th September 2018
Anna Gal, Avishay Tal, Adrian Trejo Nuñez

#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with 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