A birthday repetition theorem and complexity of approximating dense CSPs

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)

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 DE number 6381632

Cited in

(30)

A PTAS framework for clustering problems in doubling metrics
Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all $\ell_{p}$ norms
Improved parameterized approximation for balanced $k$-median
To close is easier than to open: dual parameterization to $k$-median
Approximation schemes for $k$-facility location
New tools and connections for exponential-time approximation
Short Proofs Are Hard to Find
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
Integrality gaps for colorful matchings
scientific article; zbMATH DE number 7650083 (Why is no real title available?)
Lower tails via relative entropy
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
Parameterized approximation algorithms for bidirected Steiner network problems
Lossy kernelization of same-size clustering
On Geometric Set Cover for Orthants
A note on the concrete hardness of the shortest independent vector in lattices
Lossy kernelization of same-size clustering
Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
Complexity of minimum-size arc-inconsistency explanations
Refinements of the k-tree Algorithm for the Generalized Birthday Problem
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Inapproximability of maximum biclique problems, minimum $ k$-cut and densest at-least-$ k$-subgraph from the small set expansion hypothesis
Improved FPT approximation scheme and approximate kernel for biclique-free max $k$-weight SAT: greedy strikes back
Approximation and hardness of shift-bribery
On parameterized approximation algorithms for balanced clustering
Imperfect gaps in Gap-ETH and PCPs
scientific article; zbMATH DE number 7561535 (Why is no real title available?)
A tight lower bound for planar Steiner orientation

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)