Speaker: Ben Rossman, Computer Science, University of Toronto
Title: Correlation Bounds Against Monotone NC1
Super-polynomial lower bounds against *monotone circuits* have been known since the 1980s. Why haven’t these techniques extended to non-monotone boolean circuits? One explanation lies in the “Hamming weight gap”: the fact that the YES-instances in these lower bounds (e.g. k-cliques, st-paths) have lower Hamming weight than the NO-instances (e.g. complete (k-1)-partite graphs, st-cuts). This can be seen as a barrier (akin to natural proofs), since lower bound techniques with this property cannot extend to small non-monotone classes like TC. 0
In recent work, we obtain the first super-polynomial lower bound against monotone formulas (a.k.a. the class Monotone NC) which is not subject to the Hamming weight gap. Moreover, our result is the first average-case lower bound under the uniform distribution (a.k.a. correlation bound) in the monotone setting. This has some interesting corollaries, including lower bounds against non-monotone NC 1 circuits with (1/2 - o(1))*log(n) negations (which is half the number required to compute any function in NC 1). The proof technique introduces a new notion of “persistent minterms”, which might be of independent interest. 1
This talk will focus on background and motivation and only attempt to give a high-level overview of the proof technique.