Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR22-033 | 4th January 2023 18:52

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

RSS-Feed




Revision #2
Authors: Ivan Mihajlin, Anastasia Sofronova
Accepted on: 4th January 2023 18:52
Downloads: 204
Keywords: 


Abstract:

In this work we explore a variant of a weak Karchmer-Raz-Wigderson conjecture. To be 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 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.

As a corollary it immediately follows 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$.


Revision #1 to TR22-033 | 4th January 2023 18:41

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





Revision #1
Authors: Ivan Mihajlin, Anastasia Sofronova
Accepted on: 4th January 2023 18:41
Downloads: 188
Keywords: 


Abstract:

In this work we explore a variant of a weak Karchmer-Raz-Wigderson conjecture. To be 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 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.

As a corollary it immediately follows 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 $0 0$.



Changes to previous version:

Important reference added; minor changes in abstract and acknowledgments.


Paper:

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


Abstract:

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(s):

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


Comment:

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


Comment:

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