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$.
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$.
Important reference added; minor changes in abstract and acknowledgments.
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.
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)
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.
