Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-033 | 1st March 2022 00:26

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 this, we prove a weak variant of Karchmer-Raz-Wigderson conjecture. To be more precise, we prove the existence of two functions $f \colon \{0,1\}^n \rightarrow \{0,1\}$ and $g \colon \{0,1\}^n \rightarrow \{0,1\}^n$ such that $f(g(x) \oplus y)$ is not computable by depth $(1 + \alpha - \varepsilon) n$ formulas with $(2 \alpha - \varepsilon) n$ layers of AND gates at the top. We do this by a top-down approach, which was only used before for depth-$3$ model.

Our technical contribution includes combinatorial insights into structure of composition with random boolean function, which led us to introducing a notion of well-mixed sets. A set of functions is well-mixed if, when composed with a random function, it does not have subsets that agree on large fractions of inputs. We use probabilistic method to prove the existence of well-mixed sets.


Comment #1 to TR22-033 | 6th March 2022 18:20

The file was tremporarily removed

Authors: Oded Goldreich
Accepted on: 6th March 2022 18:20


The original file, which contained a sentence that may be viewed as violating a law of some country was removed by the request of the authors. We hope to post a "legitimate" version soon. (This action is made in violation of ECCC's policy not to remove or replace files. Oded Goldreich, EiC)

Comment #2 to TR22-033 | 6th March 2022 21:45

A revised file is in place

Authors: Oded Goldreich
Accepted on: 6th March 2022 21:45


A revised file is now available. As its Section 7 says, the wording of this section has been revised so to avoid violating a censorship law of Russia.

I wish to express my deep sympathy to the authors, and join them in their hopes for peace.

Although Russia's military assault is far more shocking and the suffering that it inflicted is far more acute, it is also sad to note that citizens of a country have to fear consequences of merely expressing their opinion.

ISSN 1433-8092 | Imprint