Monotone Circuit Lower Bounds from Resolution (Now with Applications!)
summary
Gives a lifting theorem that converts resolution refutation lower bounds into exponential monotone circuit lower bounds by composing hard CNF instances with a gadget. Constructs a specific monotone XOR-SAT function: an indicator for unsatisfiable sets of ternary XOR constraints (about n^3 possible constraints) and proves exponential size is required for monotone circuits while monotone span programs over GF(2) stay small, yielding an exponential separation. Method uses a PLS communication characterization of monotone circuits; current gadgets cost gives a cube‑root loss in parameters.
AI-written summary · about