Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KARCHMER-RAZ-WIGDERSON CONJECTURE:
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

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 >>>