Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials This article analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of cnf-sat with d literals per clause to equivalent instances with  O(ndε ) bits for any ε > 0. For the Not-All-Equal sat problem, a compression to size (nd1) exists. We put these results in a common framework by analyzing the compressibility of CSPs with a binary domain. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to  n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with  O(n2ε ) bits for any  ε > 0, unless NP coNP/poly. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Download PDF
26 pages

Loading next page...
 
/lp/association-for-computing-machinery/optimal-sparsification-for-some-binary-csps-using-low-degree-Au0uQhFvNn
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3349618
Publisher site
See Article on Publisher Site

Abstract

This article analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of cnf-sat with d literals per clause to equivalent instances with  O(ndε ) bits for any ε > 0. For the Not-All-Equal sat problem, a compression to size (nd1) exists. We put these results in a common framework by analyzing the compressibility of CSPs with a binary domain. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to  n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with  O(n2ε ) bits for any  ε > 0, unless NP coNP/poly.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Aug 31, 2019

Keywords: Constraint satisfaction problem

References

  • Some problems involving Razborov-Smolensky polynomials
    Barrington, David A. Mix
  • Representing Boolean functions as polynomials modulo composite numbers
    Barrington, David A. Mix; Beigel, Richard; Rudich, Steven
  • The polynomial method in circuit complexity
    Beigel, Richard
  • Nonclassical polynomials as a barrier to polynomial lower bounds
    Bhowmick, Abhishek; Lovett, Shachar
  • Kernelization, exponential lower bounds
    Bodlaender, Hans L.
  • Kernelization lower bounds by cross-composition
    Bodlaender, Hans L.; Jansen, Bart M. P.; Kratsch, Stefan
  • Kernel bounds for disjoint cycles and disjoint paths
    Bodlaender, Hans L.; Thomassé, Stéphan; Yeo, Anders
  • Constraint satisfaction parameterized by solution size
    Bulatov, Andrei A.; Marx, Dániel
  • Best-case and worst-case sparsifiability of Boolean CSPs
    Chen, Hubie; Jansen, Bart M. P.; Pieterse, Astrid
  • Parameterized Algorithms
    Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
  • Complexity and approximability of parameterized MAX-CSPs
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias
  • Kernelization of packing problems
    Dell, Holger; Marx, Dániel
  • Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
    Dell, Holger; van Melkebeek, Dieter
  • Incompressibility through colors and IDs
    Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket
  • Kernelization lower bounds through colors and IDs
    Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket
  • Fundamentals of Parameterized Complexity
    Downey, Rodney G.; Fellows, Michael R.
  • Parameterized Complexity Theory
    Flum, J.; Grohe, M.
  • Infeasibility of instance compression and succinct PCPs for NP
    Fortnow, Lance; Santhanam, Rahul
  • The primes contain arbitrarily long arithmetic progressions
    Green, Ben; Tao, Terence
  • Kernelization: Constraint satisfaction problems parameterized above average
    Gutin, Gregory
  • Handbook of Linear Algebra, Second Edition
    Hogben, Leslie
  • Spans in the module (Zm)s
    Howell, John A.
  • Which problems have strongly exponential complexity? J
    Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
  • On sparsification for computing treewidth
    Jansen, Bart M. P.
  • Constrained bipartite vertex cover: The easy kernel is essentially tight
    Jansen, Bart M. P.
  • Sparsification upper and lower bounds for graph problems and not-all-equal SAT
    Jansen, Bart M. P.; Pieterse, Astrid
  • Optimal data reduction for graph coloring using low-degree polynomials
    Jansen, Bart M. P.; Pieterse, Astrid
  • Reducibility among combinatorial problems
    Karp, R. M.
  • Recent developments in kernelization: A survey
    Kratsch, Stefan
  • Parameterized complexity and kernelizability of max ones and exact ones problems
    Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
  • Preprocessing of min ones problems: A dichotomy
    Kratsch, Stefan; Wahlström, Magnus
  • Kernelization of constraint satisfaction problems: A study through universal algebra
    Lagerkvist, Victor; Wahlström, Magnus
  • Kernelization—Preprocessing with a guarantee
    Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket
  • Chromatic number of hypergraphs and linear algebra
    Lovász, Lásló
  • On the limits of sparsification
    Santhanam, Rahul; Srinivasan, Srikanth
  • The complexity of satisfiability problems
    Schaefer, Thomas J.
  • Fast Algorithms for Linear Algebra Modulo N
    Storjohann, Arne; Mulders, Thom
  • A lower bound on the mod 6 degree of the OR function
    Tardos, Gábor; Barrington, David A. Mix