Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
Dieter van Melkebeek
Thursday, October 29, 2009
4:00 PM, 3310 CS
This is the continuation of a talk on September 28. We'll review the setting and the results and then go into some of the proofs. We'll see how additive combinatorics comes in -- in particular the existence of high-density subsets of the integers without nontrivial arithmetic progressions of length three. Below is the abstract of the earlier talk.
Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player.
For any integer d>=3 and positive real epsilon we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n^{d-\epsilon}) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to the third level. The result even holds for conondeterministic protocols, and is tight as there exists a trivial deterministic protocol for epsilon = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, including sparsification, probabilistically checkable proofs, lossy compression, and kernelization in parameterized complexity.
Joint work with H. Dell.
Additional CS events.
|
