Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
From MaRDI portal
Publication:5454254
DOI10.1137/S0097539705447372zbMath1135.68019DBLPjournals/siamcomp/KhotKMO07WikidataQ29030121 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 (only showing first 100 items - show all)
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 ⋮ Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction ⋮ The power of unentangled quantum proofs with non-negative amplitudes ⋮ Searching for (sharp) thresholds in random structures: where are we now? ⋮ Twenty-two new approximate proof labeling schemes ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ A review on quantum approximate optimization algorithm and its variants ⋮ Total completion time scheduling under scenarios ⋮ An experimental evaluation of semidefinite programming and spectral algorithms for max cut ⋮ Lower bounds of functions on finite abelian groups ⋮ Dimension-free discretizations of the uniform norm by small product sets ⋮ Fitting metrics and ultrametrics with minimum disagreements ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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
Uses Software
This page was built for publication: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
