ECCC-Report TR22-033https://eccc.weizmann.ac.il/report/2022/033Comments and Revisions published for TR22-033en-usWed, 04 Jan 2023 18:52:46 +0200
Revision 2
| A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates |
Ivan Mihajlin,
Anastasia Sofronova
https://eccc.weizmann.ac.il/report/2022/033#revision2In 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$.Wed, 04 Jan 2023 18:52:46 +0200https://eccc.weizmann.ac.il/report/2022/033#revision2
Revision 1
| A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates |
Ivan Mihajlin,
Anastasia Sofronova
https://eccc.weizmann.ac.il/report/2022/033#revision1In 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$.Wed, 04 Jan 2023 18:41:39 +0200https://eccc.weizmann.ac.il/report/2022/033#revision1
Comment 2
| A revised file is in place |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2022/033#comment2A 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.Sun, 06 Mar 2022 21:45:32 +0200https://eccc.weizmann.ac.il/report/2022/033#comment2
Comment 1
| The file was tremporarily removed |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2022/033#comment1The 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) Sun, 06 Mar 2022 18:20:06 +0200https://eccc.weizmann.ac.il/report/2022/033#comment1
Paper TR22-033
| A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates |
Ivan Mihajlin,
Anastasia Sofronova
https://eccc.weizmann.ac.il/report/2022/033We 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.Sun, 06 Mar 2022 05:05:43 +0200https://eccc.weizmann.ac.il/report/2022/033