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 twoprover 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 finegrained inapproximability results for dense CSPs. Specifically, we establish a tight tradeoff 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 kCSPs with alphabet size q via O_k(i)level of SheraliAdams 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 fullydense Max kCSP.
 Assuming that there is a constant epsilon > 0 such that Max 3SAT cannot be approximated to within (1  epsilon) of the optimal in subexponential time, our birthday repetition theorem implies that any algorithm that approximates fullydense Max kCSP 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 kCSP, we give a new approximation algorithm for Densest kSubhypergraph, a generalization of Densest kSubgraph to hypergraphs. When the input hypergraph is O(1)uniform and the optimal ksubhypergraph has constant density, our algorithm finds a ksubhypergraph 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:178:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7463},
URN = {urn:nbn:de:0030drops74638},
doi = {10.4230/LIPIcs.ICALP.2017.78},
annote = {Keywords: Birthday Repetition, Constraint Satisfaction Problems, Linear Program}
}
07.07.2017
Keywords: 

Birthday Repetition, Constraint Satisfaction Problems, Linear Program 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 