License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.78
URN: urn:nbn:de:0030-drops-74638
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7463/
Manurangsi, Pasin ;
Raghavendra, Prasad
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Abstract
A (k x l)-birthday repetition G^{k x l} of a two-prover game G is a game in which the two provers are sent random sets of questions from G of sizes k and l respectively. These two sets are sampled independently uniformly among all sets of questions of those particular sizes. We prove the following birthday repetition theorem: when G satisfies some mild conditions, val(G^{k x l}) decreases exponentially in Omega(kl/n) where n is the total number of questions. Our result positively resolves an open question posted by Aaronson, Impagliazzo and Moshkovitz [Aaronson et al., CCC, 2014].
As an application of our birthday repetition theorem, we obtain new fine-grained inapproximability results for dense CSPs. Specifically, we establish a tight trade-off between running time and approximation ratio by showing conditional lower bounds, integrality gaps and approximation algorithms; in particular, for any sufficiently large i and for every k >= 2, we show the following:
- We exhibit an O(q^{1/i})-approximation algorithm for dense Max k-CSPs with alphabet size q via O_k(i)-level of Sherali-Adams relaxation.
- Through our birthday repetition theorem, we obtain an integrality gap of q^{1/i} for Omega_k(i / polylog i)-level Lasserre relaxation for fully-dense Max k-CSP.
- Assuming that there is a constant epsilon > 0 such that Max 3SAT cannot be approximated to within (1 - epsilon) of the optimal in sub-exponential time, our birthday repetition theorem implies that any algorithm that approximates fully-dense Max k-CSP to within a q^{1/i} factor takes (nq)^{Omega_k(i / polylog i)} time, almost tightly matching our algorithmic result.
As a corollary of our algorithm for dense Max k-CSP, we give a new approximation algorithm for Densest k-Subhypergraph, a generalization of Densest k-Subgraph to hypergraphs. When the input hypergraph is O(1)-uniform and the optimal k-subhypergraph has constant density, our algorithm finds a k-subhypergraph of density Omega(n^{−1/i}) in time n^{O(i)} for any integer i > 0.
BibTeX - Entry
@InProceedings{manurangsi_et_al:LIPIcs:2017:7463,
author = {Pasin Manurangsi and Prasad Raghavendra},
title = {{A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {78:1--78:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7463},
URN = {urn:nbn:de:0030-drops-74638},
doi = {10.4230/LIPIcs.ICALP.2017.78},
annote = {Keywords: Birthday Repetition, Constraint Satisfaction Problems, Linear Program}
}
|
Keywords: |
|
Birthday Repetition, Constraint Satisfaction Problems, Linear Program |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
