Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
From MaRDI portal
Publication:5454254
DOI10.1137/S0097539705447372zbMath1135.68019WikidataQ29030121 ScholiaQ29030121MaRDI QIDQ5454254
Guy Kindler, Subhash A. Khot, Elchanan Mossel, Ryan O'Donnell
Publication date: 28 March 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, Boolean functions: influence, threshold and noise, Bounds on 2-query locally testable codes with affine tests, Grothendieck-Type Inequalities in Combinatorial Optimization, Hard constraint satisfaction problems have hard gaps at location 1, Approximating CSPs Using LP Relaxation, Approximation Limits of Linear Programs (Beyond Hierarchies), Making the Long Code Shorter, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Disordered systems insights on computational hardness, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Fast Distributed Approximation for Max-Cut, Gaussian bounds for noise correlation of functions, Standard simplices and pluralities are not the most noise stable, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Complexity of approximating CSP with balance/hard constraints, Pricing loss leaders can be hard, Column subset selection problem is UG-hard, Max-Cut Under Graph Constraints, Gaussian noise sensitivity and Fourier tails, Sparse approximation is provably hard under coherent dictionaries, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, Probabilistic view of voting, paradoxes, and manipulation, Solution of the propeller conjecture in \(\mathbb R^3\), Towards a characterization of constant-factor approximable finite-valued CSPs, Computing the largest bond and the maximum connected cut of a graph, Low correlation noise stability of symmetric sets, On the approximability of digraph ordering, Large cuts with local algorithms on triangle-free graphs, Inapproximability ratios for crossing number, Angular synchronization by eigenvectors and semidefinite programming, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, On judicious bisections of graphs, Half-Spaces with Influential Variable, Constrained Submodular Maximization via a Nonsymmetric Technique, Noise correlation bounds for uniform low degree functions, Minimizing worst-case and average-case makespan over scenarios, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hypercontractivity via tensor calculus, The maximum cut problem on blow-ups of multiprojective spaces, A priori TSP in the Scenario Model, A tight \(\sqrt{2} \)-approximation for linear 3-cut, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions, Proof Complexity Meets Algebra, Affine reductions for LPs and SDPs, Towards a proof of the Fourier-entropy conjecture?, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Approximation Algorithms for CSPs, Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound, Approximating Unique Games Using Low Diameter Graph Decomposition, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Simple approximation algorithms for balanced MAX~2SAT, Parameterized Complexity of Multi-Node Hubs, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Maximally stable Gaussian partitions with discrete applications, Noise stability of functions with low influences: invariance and optimality, Unnamed Item, Query-Efficient Dictatorship Testing with Perfect Completeness, Computational topology and the Unique Games Conjecture, Unnamed Item, Unnamed Item, Complexity and approximation of finding the longest vector sum, Dimension Reduction for Polynomials over Gaussian Space and Applications, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Relaxations of Combinatorial Problems Via Association Schemes, Approximation algorithms for balancing signed graphs, \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel, Approximating graph-constrained max-cut, A priori TSP in the scenario model, Approximating max-cut under graph-MSO constraints, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, The structure of Gaussian minimal bubbles, Gaussian bounds for noise correlation of resilient functions, Robustly Solvable Constraint Satisfaction Problems, Online Submodular Maximization with Preemption, Approximation algorithms for connected maximum cut and related problems, Approximability Distance in the Space of H-Colourability Problems, UG-hardness to NP-hardness by losing half, Complexity results on planar multifacility location problems with forbidden regions, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Simultaneous max-cut is harder to approximate than max-cut, Approximate Kernel Clustering, On Khot’s unique games conjecture, Hypergraph cuts above the average, Parameterized complexity of multi-node hubs, Fundamental Domains for Symmetric Optimization: Construction and Search, The Quest for Strong Inapproximability Results with Perfect Completeness, Classical symmetries and the quantum approximate optimization algorithm, Empirical performance bounds for quantum approximate optimization, Minimum Cell Connection in Line Segment Arrangements, Oblivious algorithms for the maximum directed cut problem, Some applications of hypercontractive inequalities in quantum information theory, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, Speeding up a memetic algorithm for the max-bisection problem, Improved approximation for orienting mixed graphs, Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Pseudorandom sets in Grassmann graph have near-perfect expansion, Max-Cut via Kuramoto-Type Oscillators, Unnamed Item, On the complexity of binary polynomial optimization over acyclic hypergraphs, Mathematics of computation through the lens of linear equations and lattices, Interactions of computational complexity theory and mathematics, Unnamed Item, Recent Theoretical Advances in Non-Convex Optimization, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Approximating the Noise Sensitivity of a Monotone Boolean Function, THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND, Three candidate plurality is stablest for small correlations, Cones of multipowers and combinatorial optimization problems, Coreness of cooperative games with truncated submodular profit functions, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Unnamed Item, Unnamed Item, Unnamed Item
Uses Software
