Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable

We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k = 2 and k = 3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear equations. To obtain our results, we prove a new Bonami-type inequality for the Efron-Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.

Joint work with Konstantin Makarychev and Yuan Zhou.

Speaker Details

Yury Makarychev is an Associate Professor at the Toyota Technological Institute at Chicago. Yury received his undergraduate degree in Mathematics from Moscow State University and PhD in Computer Science from Princeton University. Before joining TTIC, he spent two years at Microsoft Research as a postdoctoral fellow. His research interests include combinatorial optimization, approximation algorithms, and metric geometry.

Series:
Microsoft Research Talks
Date:
Speakers:
Yury Makarychev
Affiliation:
Toyota Technological Institute at Chicago

    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Yury Makarychev

      Yury Makarychev

Series: Microsoft Research Talks