Ben Rossman: Correlation Bounds Against Monotone NC^1

Product distribution are conjectured to be a source of hard instances for important monotone problems like SAT and CLIQUE.  Yet despite a long history of lower bounds in monotone models of computation, average-case lower bounds under product distributions have been an elusive goal.  In recent work, we obtained the first results in this setting: correlation bounds against the class Monotone NC^1 of polynomial-size log-depth monotone circuits.

Our main theorem is a lower bound for the average-case k-CYCLE problem on G(n,p).  The proof technique combines the “pathset complexity” framework of [R.14] with a new notion of “persistent minterms” of a monotone function under evolving monotone noise.  Using O’Donnell’s hardness amplification theorem, we then obtain an optimal 1/2 + n^{-1/2+o(1)} correlation bound for an explicit n-variable monotone function under the uniform distribution.  Finally, we extend this result to the negation-limited setting, achieving a lower bound against NC^1 circuits with (1/2 - o(1))*log(n) negation gates.  (This is half optimal, since log(n) negations are sufficient in general for any function in NC^1.)

This talk will begin with an overview of the history and challenges of proving monotone circuit lower bounds.  I will give an overview of the pathset complexity framework and then mainly discuss the new contributions of the CCC’15 paper.