Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Karchmer-Raz-Wigderson conjecture:
TR22-033 | 1st March 2022
Ivan Mihajlin, Anastasia Sofronova

A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates

Revisions: 2 , Comments: 2

We prove that a modification of Andreev's function is not computable by $(3 + \alpha - \varepsilon) \log{n}$ depth De Morgan formula with $(2\alpha - \varepsilon)\log{n}$ layers of AND gates at the top for any $1/5 > \alpha > 0$ and any constant $\varepsilon > 0$. In order to do ... more >>>

TR23-078 | 30th May 2023
Or Meir

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

Revisions: 3

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 of a composition of functions $f \diamond g$ is roughly ... more >>>

ISSN 1433-8092 | Imprint