Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOOLEAN FORMULA COMPLEXITY:
Reports tagged with boolean formula complexity:
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 >>>




ISSN 1433-8092 | Imprint