A nearly-$4\log n$ depth lower bound for formulas with restriction on top
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910421366079488 |
|---|---|
| author | Wu, Hao |
| author_facet | Wu, Hao |
| contents | One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. Recently Mihajlin and Sofronova (CCC'22) show if considering formulas with restriction on top, we can break the $3\log n$ barrier. Formally, they prove there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<α<0.4$ and constant $0<ε<α/2$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{(α-ε)n}$ formulas of size at most $2^{(1-α/2-ε)n}$. This implies a modified version of Andreev function is not computable by any circuit of depth $(3.2-ε)\log n$ with the restriction that top $0.4-ε$ layers only consist of AND gates for any small constant $ε>0$. They ask whether the parameter $α$ can be push up to nearly $1$ thus implying a nearly-$3.5\log n$ depth lower bound.
In this paper, we provide a stronger answer to their question. We show there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<α<2-o(1)$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{αn}$ formulas of size at most $2^{(1-α/2-o(1))n}$. This implies a $(4-o(1))\log n$ depth lower bound with the restriction that top $2-o(1)$ layers only consist of AND gates. We prove it by observing that one crucial component in Mihajlin and Sofronova's work, called the well-mixed set of functions, can be significantly simplified thus improved. Then with this observation and a more careful analysis, we obtain these nearly tight results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15613 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A nearly-$4\log n$ depth lower bound for formulas with restriction on top Wu, Hao Computational Complexity One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. Recently Mihajlin and Sofronova (CCC'22) show if considering formulas with restriction on top, we can break the $3\log n$ barrier. Formally, they prove there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<α<0.4$ and constant $0<ε<α/2$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{(α-ε)n}$ formulas of size at most $2^{(1-α/2-ε)n}$. This implies a modified version of Andreev function is not computable by any circuit of depth $(3.2-ε)\log n$ with the restriction that top $0.4-ε$ layers only consist of AND gates for any small constant $ε>0$. They ask whether the parameter $α$ can be push up to nearly $1$ thus implying a nearly-$3.5\log n$ depth lower bound. In this paper, we provide a stronger answer to their question. We show there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<α<2-o(1)$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{αn}$ formulas of size at most $2^{(1-α/2-o(1))n}$. This implies a $(4-o(1))\log n$ depth lower bound with the restriction that top $2-o(1)$ layers only consist of AND gates. We prove it by observing that one crucial component in Mihajlin and Sofronova's work, called the well-mixed set of functions, can be significantly simplified thus improved. Then with this observation and a more careful analysis, we obtain these nearly tight results. |
| title | A nearly-$4\log n$ depth lower bound for formulas with restriction on top |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.15613 |