A nearly-$4\log n$ depth lower bound for formulas with restriction on top
Hao Wu







A nearly-4log n depth lower bound for formulas with restriction on top
    Hao WuCollege of Information Engineering, Shanghai Maritime University, Shanghai, China. My email is , you can also reach me via .
    
======================================================================================================================================


One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the 𝐏 versus 𝐍𝐂^1 problem.  The current best depth lower bound is (3-o(1))·log n, and it is widely open how to prove a super-3log n depth lower bound. Recently Mihajlin and Sofronova (CCC'22) show if considering formulas with restriction on top, we can break the 3log n barrier. Formally, they prove there exist two functions f:{0,1}^n →{0,1},g:{0,1}^n →{0,1}^n, such that for any constant 0<α<0.4 and constant 0<ϵ<α/2,  their XOR composition f(g(x)⊕ 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.5log 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 →{0,1},g:{0,1}^n →{0,1}^n, 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))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.










§ INTRODUCTION

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the 𝐏 versus 𝐍𝐂^1 problem.  The current best depth lower bound <cit.> is (3-o(1))·log n, and we still don't even know how to obtain  a lower bound strictly larger than 3log n. One promising approach to tackle this problem was suggested by  Karchmer, Raz and Wigderson <cit.>, they proposed that we should understand the complexity of  (block)-composition of Boolean functions. Given two  functions f: {0,1}^m →{0,1}, g: {0,1}^n →{0,1}, we define their composite function f♢ g:({0,1}^n)^m →{0,1} as:
f ♢ g(x_1, …, x_m)=f(g(x_1), …, g(x_m)).
Given any Boolean function f, we denote the depth complexity of f by 𝖣(f), that is  the minimal depth of a circuit of AND, OR and NOT gates of fan-in 2 that computes f.  And it is easy to see the depth complexity of  f ♢ g  is upper-bounded by 𝖣(f)+𝖣(g) and it is natural to ask whether the depth complexity of  f ♢ g  is far from this upper bound. Karchmer, Raz and Wigderson <cit.> conjectured that the depth complexity of  f ♢ g  is not far from its upper bound:
Given two arbitrary non-constant Boolean functions f:{0,1}^m→{0,1} and g:{0,1}^n→{0,1}, then
	𝖣(f ♢ g) ≈𝖣(f)+𝖣(g).

If the conjecture is proved and the “approximate equality” is instantiated with proper parameters,  by an argument of  iterative composition <cit.>, we will obtain an explicit function with super-logarithmic depth, which separates 𝐏 from 𝐍𝐂^1.  Many restricted cases of KRW conjecture have been proved to be true. For example, there are composition theorems when the inner function g satisfies certain property <cit.>. There are composition theorems about universal relation <cit.>. There are composition theorems where the composition itself is restricted such as monotone composition, semi-monotone composition <cit.> and strong composition <cit.>. There are also some variants <cit.> of original conjecture with the similar effect to the 𝐏 versus 𝐍𝐂^1 problem, but we don't know how to prove them either. Maybe to prove the general form of KRW conjecture is far out of our reach now.
 
Note that we don't even know how to prove a super-3log n depth lower bound, maybe we should consider following weaker conjecture which suffices to break the 3log n barrier in the first place.
There exist two non-constant Boolean functions f,g:{0,1}^n→{0,1} such that
𝖣(f ♢ g) ≥(1+ϵ)n for some small constant ϵ∈ (0,1).




Unfortunately, we don't even know how to prove this weaker conjecture. Currently, the closest answer to Conjecture <ref>  is  Meir's strong composition theorem <cit.>, but we don't know how to prove it for the case of standard composition. Mihajlin and Sofronova <cit.> proposed we should consider proving depth lower bound against even weaker formulas by considering restriction on top of the formulas.  They managed to prove  a  composition  theorem for formulas with restriction on top via XOR composition. The so-called XOR composition, proposed by Mihajlin and Smal <cit.>, is a useful special case of standard composition. In fact, the first nontrivial composition theorem <cit.> of a universal relation and some function is proved via XOR composition.


Given two functions f:{0,1}^n →{0,1},g:{0,1}^n →{0,1}^n, their XOR composition f⊞ g is defined as :
 
    f⊞ g(x,y)=f(g(x)⊕ y)

 where ⊕ denotes the bit-wise XOR of two binary strings. Mihajlin and Sofronova <cit.> proved following result.
  If we choose a function f:{0,1}^n →{0,1} randomly, with probability 1-o(1), there exists a function g:{0,1}^n →{0,1}^n, such that for any constant 0<α<0.4 and constant 0<ϵ<α/2,  their XOR composition f⊞ g is not computable by an AND (or OR) of 2^(α-ϵ)n formulas of size at most 2^(1-α/2-ϵ)n.


This implies a super-3log n depth lower bound for a modified version of the Andreev function against formulas with restriction on top.
 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(or OR) gates for any small constant ϵ>0.

Such kind of super-3log n depth lower bound is unknown before their work even for such strong restriction. They asked whether their result can be improved as asked by following question.
[<cit.>]Is it possible to extend the  range of parameter α in Theorem <ref>  to 0<α <1?

In this paper, we give a positive answer to their question  with an even better result. In fact, we extend the  range of parameter α to 0<α <2-o(1) which is nearly optimal. 


 §.§ Our results

Our main result is an improved XOR composition theorem for formulas with restriction on top. Formally, we have following result.
Let (f) be the protocol size of any Boolean function f. For most  functions f:{0,1}^n →{0,1},  
	there exists a function g : {0, 1}^n →{0, 1}^n, such that f⊞ g is not computable by an AND (or OR) of 2^α n formulas of size at most  2^n+log𝖫(f)-α n-2loglog n/2 for any 0<α < 1+ log𝖫(f)-2loglog n/n.

This implies a nearly-4log n depth lower bound for formulas with restriction on top.
A modified version of  Andreev function 𝐀𝐧𝐝𝐫' is not computable by any circuit of depth (4-o(1))log n with the restriction that top (2-o(1))log n layers only consist of AND (or OR) gates.
Comparing to the results of Mihajlin and Sofronova <cit.>, our results are nearly tight and our approach is much simpler to be described next.


  
Our approach.Here we give a concise description of the proof idea of Theorem <ref>. The whole proof strategy is similar to that in <cit.>, we call such strategy as a double-measurement argument, a generalized form of the double-counting argument. One crucial component in such argument is the notion of  well-mixed set of functions, and our improvement is mainly due to the simplification and improvement for such well-mixed set of functions. 

Let 𝒢 be the set of all functions from {0,1}^n →{0,1}^n. Now given a hard function f:{0,1}^n →{0,1}, we want to show 
there exists a function g ∈𝒢, such that if f⊞ g can be computed by a formula ϕ_g =⋀_i=1^2^α nϕ_g,i, there must be a sub-formula ϕ_g,i such that (ϕ_g,i) is large. To show this, Mihajlin and Sofronova defined a sub-additive measure μ for Boolean functions of two arguments and μ(f⊞ g) is large, thus by averaging, for every g, there exists some i_g such that μ(ϕ_g,i_g) is large enough. Note that for every g,i_g, ϕ_g,i_g computes some function  h_g,i_g, and let  ℋ be the set of all such functions h_g,i_g. If the size of ℋ is large,  by a standard counting argument, there must be a  hard function h ∈ℋ as required. But ℋ may be a small set, to prevent this, we need to show for every h∈ℋ, there  only exists a small subset of 𝒢_h ⊆𝒢 such that for every g∈𝒢_h,  h_g,i_g is the same function as h.  Formally, denote the {g|g∈𝒢, h_g,i_g =h} by 𝒢_h.
Let h_⋆ be the function such that the size of 𝒢_h_⋆ is maximum among all  𝒢_h, it suffices to show 𝒢_h_⋆ is a small set. To this end, we need to show an up bound of measurement μ(h_⋆) in another way and this is why the notion of well-mixed set is involved. 

Now consider this function 
ℳ_f,𝒢_h_⋆(x,y) =⋁_g∈𝒢_h_⋆ f(g(x)⊕ y). Let ℳ_f,𝒢_h_⋆^x be the function ℳ_f,𝒢_h_⋆ with the first argument is fixed to be some x∈{0,1}^n, we want to show if the set 𝒢_h_⋆ is large, there are many xs such that ℳ_f,𝒢_h_⋆^x is almost a constant function, and it eventually  implies  μ(h_⋆) is small which contradicts  the fact that μ(h_⋆) is already large. This is essentially the property that Mihajlin and Sofronova wanted for 𝒢_h_⋆, or in their terms,  𝒢_h_⋆ is well-mixed for function f. In their work, Mihajlin and Sofronova used a rather complicated probabilistic method to show that property.

We will show such complication is entirely unnecessary and the well-mixed property could be obtained by a simple counting argument if you choose the function f properly. For convenience, let N=2^n,  now choose  a hard function f:{0,1}^n →{0,1} such that density(f^-1(1)) = |f^-1(1)|/N≥δ, typically, we set δ to be 1/4. Note that given any fixed x, ℳ_f,𝒢_h_⋆^x(y) =1 if there is a function g∈𝒢_h_⋆ such that (g(x)⊕ y) ∈ f^-1(1). Given any x∈{0,1}^n, denote the set {z|∃ g ∈𝒢_h_⋆, g(x)=z} by 𝒢_h_⋆(x). Similarly, given x,y∈{0,1}^n, we denote the set {z|∃ g ∈𝒢_h_⋆, g(x)⊕ y=z} by 𝒢_h_⋆(x)⊕ y. Given an x, if |𝒢_h_⋆(x)| > N(1-δ), for any fixed y, we also have |𝒢_h_⋆(x)⊕ y| > N (1-δ), since for any fixed y, z⊕ y is permutation function of z. When |𝒢_h_⋆(x)⊕ y| > N (1-δ), (𝒢_h_⋆(x)⊕ y) ∩ f^-1(1) is not empty,  this means there exists g ∈𝒢_h_⋆ such that for that x, f(g(x)⊕ y)=1.

 Now we say x is bad, if |𝒢_h_⋆(x)| ≤ N (1-δ). If 𝒢_h_⋆ is a dense subset of 𝒢, the number of bad xs is small. Assume the size of 𝒢_h_⋆ is (at least) |𝒢| ·(1-δ)^P, then  there are at most P bad xs. If not,  the number of functions in 𝒢_h_⋆ is less than 
    (N(1-δ))^P · N^N-P =N^N· (1-δ)^P =|𝒢| ·(1-δ)^P
 which is a contradiction. This means, given any x which is not bad, the function  ℳ_f,𝒢_h_⋆^x(y) =1 for any y, thus ℳ_f,𝒢_h_⋆^x is a constant function. This eventually  implies  μ(h_⋆) is small which leads to the desired contradiction. Finally, since 𝒢_h_⋆ has to be a small set, the set ℋ must be a large set of functions which contains a hard function h∈ℋ as required. See more details in Lemma <ref> and Theorem <ref>.




  
Other related works.Besides Mihajlin and Sofronova's work, we note that Bathie and Williams <cit.>   established a super-3 log n depth lower bound against uniform circuits  consisting of only NAND gates. Since their result is against uniform circuits, it is incomparable to ours. They also pointed out that results similar to Mihajlin and Sofronova's work could be obtained from average-case lower bounds <cit.> via restriction-based techniques but they didn't provide further details. In a personal communication, Meir <cit.> pointed out that results similar to Mihajlin and Sofronova's work can also be obtained via techniques from communication complexity but it is not clear whether such results are as tight as ours.


 §.§ Organization of the rest of the paper

The rest of the paper is organized as follows. In Section <ref>, we provide necessary preliminaries. In Section <ref>, we prove Theorem <ref>, an improved XOR composition theorem of formulas with restriction on top. In Section <ref>, we prove Theorem <ref>, a nearly-4log n depth lower bound for formulas with restriction on top. In Section <ref>, we conclude and make some discussion  about future directions.



§ PRELIMINARIES

A  De Morgan  formula ϕ is a binary tree, its internal vertices are gates such as AND(∧) or OR(∨), its leaves are  literals such as  x_i or its negation x_i. The depth of a formula is the depth of underling tree of the formula. The size of a formula is the number of its leaves. 


The formula complexity of a boolean function f:{0,1}^n→{0,1}, denoted (f), is the size of the smallest formula that computes f . The depth complexity of f, denoted 𝖣(f), is the smallest depth of a formula that computes f.

We will need following fact, given a large set of distinct functions, there is a function with large formula size in that set.
[<cit.>, Theorem 1.23]Let ℱ be a set of distinct Boolean functions with input length n, then there exists a function f∈ℱ such that (f) ≥log|ℱ|/log n+4.



Let f:{0,1}^n →{0,1}, g:{0,1}^n →{0,1}^n be two functions, their XOR composition f⊞ g :{0,1}^n ×{0,1}^n →{0,1} is defined as follows:
	
    f⊞ g(x,y)=f(g(x)⊕ y)

where ⊕ denotes the bit-wise XOR of two binary strings.



We recall a measure μ(h) of any Boolean function h of two arguments defined in  <cit.>.
Let h be a Boolean function of two arguments, given any fixed x as the first argument, we define the function h^x by setting h^x (y)=h(x,y) and define
	
    μ(h) = ∑_x∈ X𝖫(h^x).



[<cit.>]μ (f⊞ g) ≥ 2^n ·(f) and for every x, (h^x) ≤(h).





The  measure μ is sub-additive in the following sense:
Let h(x, y) = ∘(g_1, g_2,… , g_k)(x, y), where ∘ is ∧ or ∨. Then μ (h) ≤μ (g_1) +… + μ (g_k).




  
Matrix representation for a function of two arguments.
For convenience, we follow a notation in <cit.> which treats a Boolean function of two arguments as a Boolean matrix.
Set X={0,1}^n, Y={0,1}^n, given a function h:X × Y →{0,1}, define a corresponding matrix ℳ_h  such that
	
		
  * the rows of ℳ_h  are indexed by x ∈ X and the columns are indexed by y
		∈ Y,
		
  * and ℳ_h(x,y) = h(x,y) for every x,y.
	
Similarly, given two functions  f:{0,1}^n →{0,1}, g:{0,1}^n →{0,1}^n, define a matrix ℳ_f,g such that 
  ℳ_f,g(x,y) = f(g(x)⊕ y) for every x,y.
  
 Furthermore, given a function  f:{0,1}^n →{0,1} and a set 𝒵 of functions from {0,1}^n →{0,1}^n, define a matrix ℳ_f,𝒵 such that  for every x,y,
  
    ℳ_f,𝒵(x,y) = ⋁_g∈𝒵 f(g(x)⊕ y).

  Finally, given a subset of indexes A⊆ X for rows in  a matrix ℳ,  the matrix ℳ^A is a sub-matrix of ℳ restricted to rows indexed by A.
  



  
Concentration of measure
Given  n independent random variables  X_1,…, X_n which distribute in {0, 1},  let X =∑_i=1^n X_i be their sum and	𝔼[X] = μ. For any constant δ such that 0<δ <1, we have
	
    (X ≥ (1+δ)μ)≤ e^-δ^2 μ/2+δ

	and 
		
    (X ≤  (1-δ)μ)≤ e^-δ^2 μ/2.


By Chernoff bound, we have following fact.
Let N=2^n. If we choose a function f:{0,1}^n →{0,1} randomly, then (|f^-1(1)|/N< 1/4) ≤ e^-Ω(N) and (|f^-1(0)|/N< 1/4) ≤ e^-Ω(N).




§ AN IMPROVED XOR COMPOSITION THEOREM FOR  FORMULAS WITH RESTRICTION ON TOP

In this section, we prove Theorem <ref>. At first, let's recall the notion of well-mixed set of functions.

	A set of functions 𝒢 from {0, 1}^n →{0, 1}^n is
	(Q, D, P)-well-mixed for f if ∀𝒵⊆𝒢, |𝒵| ≥ Q, there exist a set K⊆{0, 1}^n, |K| ≤  P , such
	that ℳ^X∖ K_f,𝒵 has no more than D zeroes in total  where ℳ_f,𝒵(x,y) =⋁_g∈𝒵 f(g(x)⊕ y).	

Now we show given any approximately balanced function f, the set 𝒢 of all functions  {0,1}^n →{0,1}^n is already a well-mixed set of functions for f.

 Let f:{0,1}^n →{0,1} be a function,  𝒢 be the set of all functions {0,1}^n →{0,1}^n. For convenience, let N =2^n and X ={0,1}^n. Assume  density(f^-1(1)) = |f^-1(1)|/N≥δ,  then 𝒢 is (|𝒢|· (1-δ)^P,0,P)-well-mixed for f.   Particularly, let  𝒵⊆𝒢 be a set of functions and density(𝒵) = |𝒵|/|𝒢|, there exists a set  K⊆{0,1}^n such that |K|= P ≤logdensity(𝒵) /log (1-δ)  and all entries in ℳ^X∖ K_f,𝒵 are  ones.


 Let  𝒵⊆𝒢 be a set of functions, given any x∈{0,1}^n, denote the set {z|∃ g ∈𝒵, g(x)=z} by 𝒵(x), and we say x is bad if |𝒵(x)|≤ N(1-δ). Similarly, given x,y∈{0,1}^n, we denote the set {z|∃ g ∈𝒵, g(x)⊕ y=z} by 𝒵(x)⊕ y.
	
Now assume there are  P bad xs, the number of functions in 𝒵 is at most 
    (N(1-δ))^P · N^N-P =N^N· (1-δ)^P =|𝒢| ·(1-δ)^P.

This implies
density(𝒵) = |𝒵|/|𝒢|≤  (1-δ)^P, this means P≤logdensity(𝒵) /log (1-δ).

Now we show when x is not bad, for every y∈{0,1},   ℳ_f,𝒵(x,y) =⋁_g∈𝒵 f(g(x)⊕ y) =1. Since |𝒵(x)|>N(1-δ), we have |𝒵(x)⊕ y|>N(1-δ).  Since  |𝒵(x)⊕ y| > N (1-δ), (𝒵(x)⊕ y)∩ f^-1(1) is not empty, there must be a g ∈𝒵 such that g(x)⊕ y ∈ f^-1(1), thus ⋁_g∈ Z f(g(x)⊕ y) must be 1 as required.

Now we are ready to prove Theorem <ref> rephrased as follows. It is proved via a similar idea  in <cit.> and a more careful analysis.

	Let  f:{0, 1}^n →{0, 1} be a function and 
	density(f^-1(1)) ≥1/4, 
	there exists a function g : {0, 1}^n →{0, 1}^n, such that f⊞ g is not computable by an AND of 2^α n formulas of size at most  2^n+log𝖫(f)-α n-2loglog n/2 for any 0<α < 1+ log𝖫(f)-2loglog n/n.

We prove it by contradiction. Let 𝒢 be the set of all functions {0,1}^n →{0,1}^n. Assume the contrary that for all g ∈𝒢 the XOR composition f⊞ g is computable by   AND of  small enough formulas. That is, for any g∈𝒢, there is a formula ϕ_g computing f⊞ g and ϕ_g is  of following form
 
    ϕ_g =⋀_i=1^2^α nϕ_g,i

	where the size of every ϕ_g,i is at most  2^n+log𝖫(f)-α n-2loglog n/2. Now let h_g,i be the function that ϕ_g,i computes, thus (h_g,i) ≤ 2^n+log𝖫(f)-α n-2loglog n/2 and f⊞ g can be represented as  ⋀_i=1^2^α n
	h_g,i. 
	
Recall that for every g∈𝒢, μ (f⊞ g) ≥ 2^n ·(f). By Lemma <ref>,  there must be an i_g ∈ [2^α n] such that, the measure μ(h_g,i_g) is large:

    μ(h_g,i_g ) ≥ 2^(1-α)n·𝖫(f).


Now we collect all such functions h_g,i_g and let  ℋ be the set of all such functions h_g,i_g. We want to show that the size of ℋ is large, thus by a standard counting argument, there must be a function h ∈ℋ which requires large formulas  which contradicts the hypothesis. 

Given any h∈ℋ,  denote the {g|g∈𝒢, h_g,i_g =h} by 𝒢_h.
Let h_⋆ be the function such that the size of 𝒢_h_⋆ is maximum among all  𝒢_h. We will prove 
    -4 logdensity(𝒢_h_⋆) ·(h_⋆) ≥μ(h_⋆ ) ≥ 2^(1-α)n·(f),

before proving this, let's show it indeed leads to the contradiction required. Recall by assumption (h_⋆) ≤ 2^n+log𝖫(f)-α n-2loglog n/2, this means

    density(𝒢_h_⋆) ≤ 2^-2^n+log𝖫(f)-α n+2loglog n-4/2.

Now we are ready to lower bound the size of |ℋ|, that is the number of distinct functions in ℋ.
Since |ℋ|· |𝒢_h_⋆| ≥ |𝒢|,

    |ℋ| ≥1/density(𝒢_h_⋆)≥ 2^2^n+log𝖫(f)-α n+2loglog n-4/2.

By Fact <ref>, there exists an h∈ℋ such that 

    (h)    ≥2^n+log𝖫(f)-α n+2loglog n-4/2/log 2n +4 
       > 2^n+log𝖫(f)-α n-2loglog n/2,when n is large enough,

which is a contradiction to the assumption. Now we show -4logdensity(𝒢_h_⋆) ·(h_⋆) ≥μ(h_⋆ ) by considering the matrix ℳ_f,𝒢_h_⋆. By Lemma <ref>, 

	
  * there exists a set  K⊆{0,1}^n such that
	
    |K|     ≤logdensity(𝒢_h_⋆) /log (1-1/4)
       ≤ -4·logdensity(𝒢_h_⋆),  since  log3/4≈ -0.415 thus 1 <log3/4/-0.25.

	
  * And all entries in ℳ^X∖ K_f,𝒢_h_⋆ are  ones.

Now we have following key fact about the function h_⋆.
For every x,y ∈{0,1}^n, ℳ_f,𝒢_h_⋆(x,y)=1 implies h_⋆(x,y)=1.

Recall that ℳ_f,𝒢_h_⋆(x,y) =⋁_g∈𝒢_h_⋆ (f⊞ g)(x,y). If ℳ_f,𝒢_h_⋆(x,y)=1, there must be some g∈𝒢_h_⋆ such that (f⊞ g)(x,y) = 1. Furthermore, by assumption f⊞ g is simply  ⋀_i=1^2^α n
	h_g,i and h_⋆ =h_g,i for some i, thus  h_⋆(x,y) must be 1 as well. 

By  Fact <ref>,  given any x∈ X∖ K, for every y∈{0,1}^n, h_⋆^x(y) = 1 , in other words, h_⋆^x is a constant function and (h_⋆^x)=0. Now we are ready to up bound  μ(h_⋆) and have
	
    μ(h_⋆)   =∑_x L(h_⋆^x)=∑_x∈ K L(h_⋆^x)+∑_x∉ K L(h_⋆^x) 
       = ∑_x∈ K L(h_⋆^x)
       ≤ |K|·(h_⋆) 
       ≤ -4 ·logdensity(𝒢_h_⋆) ·(h_⋆).

	as required.

We want to point out the AND(∧) gate can be replaced with OR(∨) gate and since we use the counting argument to show there exists a hard function in the set ℋ, this result can be extended to the case of formula over full binary basis.





§ A NEARLY-4LOG N DEPTH LOWER BOUND FOR  FORMULAS WITH RESTRICTION ON TOP

We will prove a depth lower bound for a modified Andreev function defined in <cit.>.
The modified Andreev function 𝐀𝐧𝐝𝐫':{0,1}^n×{0,1}^nlog n×{0,1}^n× 2log n →{0,1} is defined as follows:
	
    𝐀𝐧𝐝𝐫'(𝚃𝚃_f,𝚃𝚃_g,x_1,…, x_2log n) =(f⊞ g)(⊕(x_1),…, ⊕(x_2log n))

where  𝚃𝚃_f is a truth table of some function f from {0,1}^log n→{0,1},𝚃𝚃_g is a truth table of some function g from {0,1}^log n→{0,1}^log n, for every i∈ [2log n], x_i is a binary string of length n and ⊕(·) is the parity function.

There exist two parameters γ =o(1),ϵ=o(1),  for every constant α such that 0<α < 2-γ, the modified Andreev function 𝐀𝐧𝐝𝐫' is not computable by an AND of n^α formulas of size at most n^3-α/2-ϵ.
	
In terms of depth lower bound, the modified Andreev function 𝐀𝐧𝐝𝐫' is not computable by any circuit of depth (3+α/2-ϵ)log n with the restriction that top α layers only consist of AND gates where 0<α < 2-γ. Choose α =2-o(1) properly, Theorem <ref> follows.


	Note that the input length of the modified Andreev function 𝐀𝐧𝐝𝐫' is n'=(3log n +1)n,  writing the results in terms of n^' doesn't change them essentially. For example,  (4-o(1))log n > (4-o(1))logn'/4log n > (4-o(1))logn'/4log n'=(4-o(1)-loglog  n'+2/log n')logn' =(4-o(1))logn'. Similarly, in the restriction for top gates, AND could be replaced by OR. 
	

Theorem <ref> is proved via the same idea from <cit.>, the only differences here are  details of  parameters. For completeness of this paper, we present the proof here. At first, we recall the standard notion of random restriction.
Given a Boolean function f : {0,1}^n →{0,1}, a restriction ρ∈{0,1,∗}^n to function f is a vector of length n and for every i∈[n], ρ_i is an element from {0,1,∗}.  Define f|_ρ to be  the function restricted according to ρ as follows:
if ρ_i is ∗  then the i-th input bit of f is unfixed thus free to be 0 or 1; otherwise the i-th input bit of f is fixed to be ρ_i.

Given 0<p<1, the random restriction R_p  randomly samples restrictions as follows: every ρ_i is sampled independently such that [ρ_i=∗]=p and [ρ_i=1]=[ρ_i=0]=1-p/2.

In the rest of this section, we will set p=2lnlog n/n.  Mihajlin and Sofronova  proved following useful two lemmas about random restriction of the modified Andreev function implicitly in <cit.>.

Let 𝐀𝐧𝐝𝐫'_f,g be the 𝐀𝐧𝐝𝐫' function hardwired with two fixed functions f,g. Then with probability 1-o(1), the random restriction R_p will turn 𝐀𝐧𝐝𝐫'_f,g into f⊞ g.


Let α,β be two parameters such that 0<α <2, 2<β<3. Let  ϕ  be a formula of form ⋀_i=1^n^αϕ_i where the size of each ϕ_i is at most n^β. Then with probability 1-o(1), the random restriction R_p will turn ϕ into a formula ϕ'  of form ⋀_i=1^n^αϕ_i^' where the size of each ϕ_i^' is at most n^β -2+δ  for some  δ=o(1).

Now we show how to prove Theorem <ref> with above two lemmas.
At first choose some function f from {0,1}^log n→{0,1}  and make sure that f is  the function with maximum protocol size and |f^-1(1)|/n≥1/4. By Fact <ref> and <ref>, we have (f)≥log((1-o(1))2^2^log n) /(loglog n+4) ≥ n/2loglog n when n is large enough. By Theorem <ref>, we have following fact.
Let f be the function chosen above, there exists a function g : {0, 1}^log n→{0, 1}^log n, such that f⊞ g is not computable by an AND of n^α formulas of size at most  n^1-α/2-2logloglog n/log n for any 0<α < 2-4logloglog n/log n when n is large enough.

Let δ be the same parameter from Lemma <ref>, γ=4logloglog n/log n  and ϵ=δ+γ/2. Choose some  α such that 0<α <2-γ and set β=3-α/2-ϵ. Now assume  Theorem <ref> is false, that is  𝐀𝐧𝐝𝐫' is computable by formula ϕ  of form ⋀_i=1^n^αϕ_i where the size of each ϕ_i is at most n^β, and so is 𝐀𝐧𝐝𝐫'_f,g. By Lemma <ref> and  <ref>, f⊞ g is computable by a formula ϕ'  of form ⋀_i=1^n^βϕ_i^' where the size of each ϕ_i^' is at most 
    n^β -2+δ =n^1-α/2-ϵ+δ=n^1-α/2-2logloglog n/log n

which contradicts Fact <ref>.







§ CONCLUSION AND DISCUSSION

In this paper, we obtain a nearly-tight XOR composition theorem for formulas with restriction on top and with this composition theorem we have a nearly-4log n depth lower bound for formulas with restriction on top. Intuitively, in such the depth lower bound,  we trade one unrestricted layer to nearly two layers of AND gates on top of the circuit and our trade-off is nearly optimal.

The next nature question as pointed out by Mihajlin and Sofronova <cit.> is to prove the case with 𝐀𝐂^0 formula on top. But it turns out even to prove the case of depth-2 formula  with unbounded fan-in is difficult.  The obstacle to extending current approach to the case of depth-2 formula on top is that we don't know how to  find the sub-formula h_⋆ such that the measure μ(h_⋆) is large enough meanwhile h_⋆ is correlated with f⊞ g  properly like that in Fact <ref>. This difficulty  also appears in the approach via communication complexity <cit.>, since such result  shares the same feature with a composition theorem of a depth-2 formula and a De Morgan formula, but we don't even know how to prove a composition theorem of two depth-2 formulas in general. New ideas are needed, maybe we should try to prove a general composition theorem of two depth-2 formulas in the first place.
 

§ ACKNOWLEDGMENTS

The author would like to thank Or Meir for sharing the idea about how to prove results similar to Mihajlin and Sofronova's work via techniques from communication complexity and other helpful discussions. The author would  also like to thank Pei Wu for suggesting the question of the composition of two depth-2 formulas and other helpful discussions.











alpha





