Speaker: Ben Rossman, Computer Science, University of Toronto

Title: Correlation Bounds Against Monotone NC^{^1}

Abstract:

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^{^1}) 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.

This talk will focus on background and motivation and only attempt to give a high-level overview of the proof technique.