One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the \(\textbf{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) [18] 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<\alpha <0.4\) and constant \(0<\epsilon <\alpha /2\) , their XOR composition \(f(g(x)\oplus y)\) is not computable by an AND of \(2^{(\alpha -\epsilon )n}\) formulas of size at most \(2^{(1-\alpha /2-\epsilon )n}\) . This implies a modified version of Andreev function is not computable by any circuit of depth \((3.2-\epsilon )\log n\) with the restriction that top \(0.4-\epsilon \) layers only consist of AND gates for any small constant \(\epsilon >0\) . They ask whether the parameter \(\alpha \) 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<\alpha <2-o(1)\) , their XOR composition \(f(g(x)\oplus y)\) is not computable by an AND of \(2^{\alpha n}\) formulas of size at most \(2^{(1-\alpha /2-o(1))n}\) . This implies a \((4-o(1))\log n\)  depth lower bound with the restriction that top \((2-o(1))\log n\) 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. It is pointed out that actually similar result already follows from Komargodski, Raz and Tal’s average-case lower bound [12]. The advantage of our work is not providing quantitatively better parameters. Instead, the main merit of our result is that our proof is based on a top-down approach and provides a new angle to questions about composition of functions.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Nearly- \(4\log n\) Depth Lower Bound for Formulas With Restriction on Top

  • Hao Wu

摘要

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the \(\textbf{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) [18] 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<\alpha <0.4\) and constant \(0<\epsilon <\alpha /2\) , their XOR composition \(f(g(x)\oplus y)\) is not computable by an AND of \(2^{(\alpha -\epsilon )n}\) formulas of size at most \(2^{(1-\alpha /2-\epsilon )n}\) . This implies a modified version of Andreev function is not computable by any circuit of depth \((3.2-\epsilon )\log n\) with the restriction that top \(0.4-\epsilon \) layers only consist of AND gates for any small constant \(\epsilon >0\) . They ask whether the parameter \(\alpha \) 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<\alpha <2-o(1)\) , their XOR composition \(f(g(x)\oplus y)\) is not computable by an AND of \(2^{\alpha n}\) formulas of size at most \(2^{(1-\alpha /2-o(1))n}\) . This implies a \((4-o(1))\log n\)  depth lower bound with the restriction that top \((2-o(1))\log n\) 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. It is pointed out that actually similar result already follows from Komargodski, Raz and Tal’s average-case lower bound [12]. The advantage of our work is not providing quantitatively better parameters. Instead, the main merit of our result is that our proof is based on a top-down approach and provides a new angle to questions about composition of functions.