Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Wednesday April 25th, 2012 Time: 1:30pm Place: MC5158 (note unusual room)         Title: Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses Speaker: Dieter van Melkebeek, University of Wisconsin Abstract:   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 the polynomial-time hierarchy collapses. The result is tight as there exists a trivial protocol for epsilon = 0. Under the standard complexity-theoretic hypothesis that the polynomial-time hierarchy does not collapse, the result implies tight lower bounds for parameters of interest in several areas, including sparsification, probabilistically checkable proofs, instance compression, and kernelization in parameterized complexity. By reduction similar results hold for other NP-complete problems. For the vertex cover problem on n-vertex d-uniform hypergraphs, the above statement holds for any integer d >= 2. The case d=2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k^{2-epsilon}) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion. The proofs hinge on the existence of high-density subsets of the integers without nontrivial arithmetic progressions of length three. Joint work with Holger Dell.