A birthday repetition theorem and complexity of approximating dense CSPs

DOI10.4230/LIPICS.ICALP.2017.78zbMATH Open1441.68048arXiv1607.02986MaRDI QIDQ5111409FDOQ5111409

Prasad Raghavendra, Pasin Manurangsi

Publication date: 27 May 2020

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

Recommendations

• Approximating dense MAX 2-CSPs
• A counterexample to strong parallel repetition
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse
• scientific article

zbMATH Keywords

constraint satisfaction problemslinear programbirthday repetition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Cited In (30)

• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Imperfect gaps in Gap-ETH and PCPs
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• On parameterized approximation algorithms for balanced clustering
• To close is easier than to open: dual parameterization to \(k\)-median
• Complexity of minimum-size arc-inconsistency explanations
• A PTAS framework for clustering problems in doubling metrics
• Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
• Approximation and hardness of shift-Bribery
• Improved parameterized approximation for balanced \(k\)-median
• A note on the concrete hardness of the shortest independent vector in lattices
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation schemes for \(k\)-facility location
• Refinements of the k-tree Algorithm for the Generalized Birthday Problem
• Short Proofs Are Hard to Find
• On Geometric Set Cover for Orthants
• New tools and connections for exponential-time approximation
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_p\) norms
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• Lower tails via relative entropy
• A tight lower bound for planar Steiner orientation
• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
• Integrality gaps for colorful matchings
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Lossy kernelization of same-size clustering
• Lossy kernelization of same-size clustering

This page was built for publication: A birthday repetition theorem and complexity of approximating dense CSPs

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