A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates


Anastasia Sofronova Septmber 23,2022.


The talk is about a weak variant of Karchmer-Raz-Wigderson conjecture. This is a joint work with Ivan Mihajlin.

We prove the existence of two functions f: {0,1}^n → {0,1} and g: {0,1}^n → {0,1}^n such that f(g(x)⊕y) is not computable by depth (1 + α − ε)n formulas with (2α − ε)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. As an application of the result, we immediately get a simple lower bound on a modified Andreev’s function.

Our technical contribution includes combinatorial insights into structure of composition with random boolean function and 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.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube
  • The Composition Complexity of Majority
  • On the Probabilistic Degree of an n-variate Boolean Function
  • Criticality of AC0-formulae
  • Hardness Condensation and Log Approximate Rank Conjecture