Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable

Channel:
Microsoft Research
Subscribers:
343,000
Published on ● Video Link: https://www.youtube.com/watch?v=s44Ii8Lskd0


Duration: 54:08
113 views
2

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.



Other Videos By Microsoft Research


2016-06-22Welcome and Keynote - Geoff Bilder, Director of Strategic Initiatives at CrossRef
2016-06-22Symposium: Brains, Minds and Machines - Surya Ganguli
2016-06-22Symposium: Deep Learning - Xiaogang Wang
2016-06-22Oral Session: Interactive Control of Diverse Complex Characters with Neural Networks
2016-06-22Oral Session: Solving Random Quadratic Systems of Equations-Nearly as Easy as Solving Linear Systems
2016-06-22Towards Understandable Neural Networks for High Level AI Tasks - Part 7
2016-06-22The Once and Future Internet
2016-06-22The First Order World of Galton-Watson Trees
2016-06-22Verasco, a formally verified C static analyzer
2016-06-22Symposium: Deep Learning - Max Jaderberg
2016-06-22Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable
2016-06-22Symposium: Deep Learning - Harri Valpola
2016-06-22Machine Learning as Creative Tool for Designing Real-Time Expressive Interactions
2016-06-22Symposium: Deep Learning - Sergey Ioffe
2016-06-22Multi-rate neural networks for efficient acoustic modeling
2016-06-22Robust Spectral Inference for Joint Stochastic Matrix Factorization and Topic Modeling
2016-06-22Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
2016-06-22Extreme Classification: A New Paradigm for Ranking & Recommendation
2016-06-22A Lasserre-Based (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints
2016-06-22Oral Session: Learning Theory and Algorithms for Forecasting Non-stationary Time Series
2016-06-22Recent Developments in Combinatorial Optimization


Tags:
microsoft research
algorithms