On the usefulness of predicates

DOI10.1145/2462896.2462897zbMATH Open1322.68093DBLPjournals/toct/AustrinH13arXiv1204.5662OpenAlexW2169488047WikidataQ56958773 ScholiaQ56958773MaRDI QIDQ2947573FDOQ2947573

Authors: Per Austrin, Johan Hastad 

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate $P$ being emph{useful} for a (real-valued) objective $Q$: given an almost satisfiable Max-$P$ instance, there is an algorithm that beats a random assignment on the corresponding Max-$Q$ instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for $P$ itself. We say that $P$ is useless if it is not useful for any $Q$. This turns out to be equivalent to the following pseudo-randomness property: given an almost satisfiable instance of Max-$P$ it is hard to find an assignment such that the induced distribution on $k$-bit strings defined by the instance is not essentially uniform. Under the Unique Games Conjecture, we give a complete and simple characterization of useful Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pairwise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.

Full work available at URL: https://arxiv.org/abs/1204.5662

Recommendations

• Approximation resistant predicates from pairwise independence
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Parity is positively useless
• On quadratic threshold CSPs
• SDP gaps from pairwise independence

zbMATH Keywords

constraint satisfaction problemunique games conjectureapproximation resistanceusefulness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (8)

• Title not available (Why is that?)
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Parity is positively useless
• Predicate invention and utilization
• On the Approximability of Presidential Type Predicates
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• \((2+\varepsilon)\)-Sat is NP-hard
• Robust algorithms with polynomial loss for near-unanimity CSPs

This page was built for publication: On the usefulness of predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947573)