Algorithms and Logic Group

Algebraic Sparsification for Decision and Maximization Constraint Satisfaction Problems

Speaker:

Bart Jansen(Eindhoven University of Technology)

Time:

  • 5:00 p.m., February 25, 2021(Time in Bergen, GMT+1)
  • 12:00 p.m., February 25, 2021(Time in Beijing, GMT+8)

Link:

Abstract:

We survey polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language), and how sparsification algorithms can be obtained by modeling constraints as low-degree polynomials. We also consider the corresponding problem for Maximum CSP problems, where the notion of characteristic polynomials turns out to characterize optimal compressibility.

,