Friday, June 26, 2015 - 1:15pm to 4:15pm

Refreshments:

Pizza at 1:00pm

Location:

MSR (Barton room on the first floor of 1 Memorial Drive)

Speaker:

Ben Rossman

Seminar group:

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 NC1 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.