Monotone Circuit Lower Bounds from Resolution

Computer Science/Discrete Mathematics Seminar II
Topic:Monotone Circuit Lower Bounds from Resolution
Speaker:Mika Goos
Affiliation:Member, School of Mathematics
Date:Tuesday, November 27
Time/Room:10:30am - 12:30pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2018/1127-MikaGoos

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. As an application, we show that a monotone variant of XOR-SAT has exponential monotone circuit complexity, which improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988).