On the power of unique 2-prover 1-round games
From MaRDI portal
Publication:3579218
DOI10.1145/509907.510017zbMath1192.68367OpenAlexW2120358419WikidataQ57568008 ScholiaQ57568008MaRDI QIDQ3579218
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.510017
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Is constraint satisfaction over two variables always easy?, CLAP: A New Algorithm for Promise CSPs, Topology and Adjunction in Promise Constraint Satisfaction, Tight Approximation Bounds for Maximum Multi-coverage, Improved Parameterized Algorithms for above Average Constraint Satisfaction, On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time, Simultaneous Approximation of Constraint Satisfaction Problems, Approximating CSPs Using LP Relaxation, Approximation Limits of Linear Programs (Beyond Hierarchies), Making the Long Code Shorter, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Generalized XOR non-locality games with graph description on a square lattice, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, Designing FPT Algorithms for Cut Problems Using Randomized Contractions, Anchored Parallel Repetition for Nonlocal Games, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, Unnamed Item, Unnamed Item, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Nonlocal Games with Noisy Maximally Entangled States are Decidable, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Inapproximability of $H$-Transversal/Packing, On the complexity of the cable-trench problem, An Exact Method for the Minimum Feedback Arc Set Problem, Approximating power node-deletion problems, Unnamed Item, A modeling and computational study of the frustration index in signed networks, PTAS for Sparse General-valued CSPs, Linear‐time algorithms for eliminating claws in graphs, FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms, Recognizing when a preference system is close to admitting a master list, Pseudorandom sets in Grassmann graph have near-perfect expansion, Recognizing when a preference system is close to admitting a master list, Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Unnamed Item, Unnamed Item, Unnamed Item, Complexity of maximum cut on interval graphs, $(2+\varepsilon)$-Sat Is NP-hard, Amplification and Derandomization without Slowdown, Parallel Repetition of Two-Prover One-Round Games: An Exposition, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Approximating Single Machine Scheduling with Scenarios, Approximation Algorithms for CSPs, Approximating Unique Games Using Low Diameter Graph Decomposition, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Vertex Cover in Graphs with Locally Few Colors, Cones of multipowers and combinatorial optimization problems, Unnamed Item, Query-Efficient Dictatorship Testing with Perfect Completeness, Hardness of robust network design, Computational topology and the Unique Games Conjecture, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, An improved derandomized approximation algorithm for the max-controlled set problem, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, Dimension-free L2 maximal inequality for spherical means in the hypercube, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity, Stabilizing Weighted Graphs, Approximability Distance in the Space of H-Colourability Problems, Unnamed Item, UG-hardness to NP-hardness by losing half, Imperfect gaps in Gap-ETH and PCPs, Unnamed Item, Simultaneous max-cut is harder to approximate than max-cut, Generalized network design polyhedra, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses, On Khot’s unique games conjecture, Pointer chasing via triangular discrimination, A Linear-Time Parameterized Algorithm for Node Unique Label Cover, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, Non-unique games over compact groups and orientation estimation in cryo-EM, The Quest for Strong Inapproximability Results with Perfect Completeness, Nearly Optimal NP-Hardness of Unique Coverage, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal and Explicit Bell Inequality Violations, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs, Hardness of Rainbow Coloring Hypergraphs, An Improved Dictatorship Test with Perfect Completeness, On the complexity of binary polynomial optimization over acyclic hypergraphs, Online and Approximate Network Construction from Bounded Connectivity Constraints, Hypercontractivity on the symmetric group, Interactions of computational complexity theory and mathematics, Unnamed Item, Unnamed Item, Siting renewable power generation assets with combinatorial optimisation, On regularity of Max-CSPs and Min-CSPs, On the complexity of minimum \(q\)-domination partization problems, Bounds on 2-query locally testable codes with affine tests, An edge-reduction algorithm for the vertex cover problem, Beyond Moulin mechanisms, Complexity and approximation of the minimum recombinant haplotype configuration problem, Hard constraint satisfaction problems have hard gaps at location 1, Logic minimization techniques with applications to cryptology, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, A note on unique games, Gaussian bounds for noise correlation of functions, Complexity of approximating CSP with balance/hard constraints, Pricing loss leaders can be hard, Column subset selection problem is UG-hard, Vertical perimeter versus horizontal perimeter, Cryptographic hardness of random local functions. Survey, Gaussian noise sensitivity and Fourier tails, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Exact and approximate algorithms for movement problems on (special classes of) graphs, Sparse approximation is provably hard under coherent dictionaries, Partial multicuts in trees, Approximation and hardness results for the maximum edge \(q\)-coloring problem, Solution of the propeller conjecture in \(\mathbb R^3\), Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem, On the approximability of digraph ordering, Tight approximation bounds for dominating set on graphs of bounded arboricity, On the complexity of trial and error for constraint satisfaction problems, The multi-multiway cut problem, Inapproximability ratios for crossing number, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), Minimizing the sum of weighted completion times in a concurrent open shop, Parameterized complexity of MaxSat above average, Separator-based data reduction for signed graph balancing, Angular synchronization by eigenvectors and semidefinite programming, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Tight size-degree bounds for sums-of-squares proofs, Sum-of-squares hierarchy lower bounds for symmetric formulations, Finding small stabilizers for unstable graphs, On the approximability and hardness of minimum topic connected overlay and its special instances, Drawing (complete) binary tanglegrams, Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs, Noise correlation bounds for uniform low degree functions, A unified approach to approximating partial covering problems, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Minimizing worst-case and average-case makespan over scenarios, Extended formulation for CSP that is compact for instances of bounded treewidth, Pareto robust optimization on Euclidean vector spaces, Spectral algorithms for unique games, Approximating vertex cover in dense hypergraphs, On the robust hardness of Gröbner basis computation, FPT algorithms for path-transversal and cycle-transversal problems, The complexity of König subgraph problems and above-guarantee vertex cover, On the maximum acyclic subgraph problem under disjunctive constraints, Notes on computational-to-statistical gaps: predictions using statistical physics, Unnamed Item, Limitations of semidefinite programs for separable states and entangled games, Column subset selection is NP-complete, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Target set selection for conservative populations, Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem, On optimal approximability results for computing the strong metric dimension, Improved approximation algorithms for projection games, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Random Laplacian matrices and convex relaxations, The envy-free pricing problem, unit-demand markets and connections with the network pricing problem, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Network pollution games, Efficient stabilization of cooperative matching games, On the complexity of the highway problem, Approximating maximum satisfiable subsystems of linear equations of bounded width, Maximally stable Gaussian partitions with discrete applications, Metrical service systems with multiple servers, Improved approximation algorithms for path vertex covers in regular graphs, Noise stability of functions with low influences: invariance and optimality, The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\), Large violation of Bell inequalities with low entanglement, Constant ratio fixed-parameter approximation of the edge multicut problem, The ordered covering problem, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Convex Relaxations and Integrality Gaps, Quasimetric embeddings and their applications, On non-optimally expanding sets in Grassmann graphs, Perspectives on CUR decompositions, Half-integrality, LP-branching, and FPT Algorithms, Gaussian bounds for noise correlation of resilient functions, Robustly Solvable Constraint Satisfaction Problems, Path hitting in acyclic graphs, Makespan minimization with OR-precedence constraints, On the complexity of fair house allocation, Quantum XOR Games, Approximating edge dominating set in dense graphs, Strong and weak edges of a graph and linkages with the vertex cover problem, Beating the 2-approximation factor for global bicut, Priority algorithms for graph optimization problems, Tight inapproximability of minimum maximal matching on bipartite graphs and related problems, Clustering with qualitative information, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), Tight approximation bounds for maximum multi-coverage
