A nearly-4 n depth lower bound for formulas with restriction on top

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a. k. a, the P versus NC¹ problem. The current best depth lower bound is (3-o (1) ) n, and it is widely open how to prove a super-3 n depth lower bound. Recently Mihajlin and Sofronova (CCC'22) show if considering formulas with restriction on top, we can break the 3 n barrier. Formally, they prove there exist two functions f: \0, 1\ⁿ \0, 1\, g: \0, 1\ⁿ \0, 1\ⁿ, such that for any constant 00. They ask whether the parameter can be push up to nearly 1 thus implying a nearly-3. 5 n depth lower bound. In this paper, we provide a stronger answer to their question. We show there exist two functions f: \0, 1\ⁿ \0, 1\, g: \0, 1\ⁿ \0, 1\ⁿ, such that for any constant 0<<2-o (1), their XOR composition f (g (x) 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) ) 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.