Show simple item record

dc.contributor.author
Barak, Boaz
dc.contributor.author
Hardt, Moritz
dc.contributor.author
Holenstein, Thomas
dc.contributor.author
Steurer, David
dc.date.accessioned
2020-09-28T08:26:54Z
dc.date.available
2017-06-09T09:16:06Z
dc.date.available
2020-09-28T08:26:54Z
dc.date.issued
2010-11-29
dc.identifier.uri
http://hdl.handle.net/20.500.11850/29906
dc.description.abstract
We initiate a study of when the value of mathematical relaxations such as linear and semidefinite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let $C$ be a family of CSPs such as 3SAT, Max-Cut, etc., and let $\Pi$ be a relaxation for $C$, in the sense that for every instance $P\in C$, $\Pi(P)$ is an upper bound the maximum fraction of satisfiable constraints of $P$. Loosely speaking, we say that subsampling holds for $C$ and $\Pi$ if for every sufficiently dense instance $P \in C$ and every $\epsilon>0$, if we let $P'$ be the instance obtained by restricting $P$ to a sufficiently large constant number of variables, then $\Pi(P') \in (1\pm \epsilon)\Pi(P)$. We say that weak subsampling holds if the above guarantee is replaced with $\Pi(P')=1-\Theta(\gamma)$ whenever $\Pi(P)=1-\gamma$. We show: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the relaxation considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every CSP under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semidefinite programs. Also there are unique CSPs for which subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semidefinite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value $1-\gamma$ have a cut value at most $1-\gamma/10$.
en_US
dc.language.iso
en
en_US
dc.publisher
Cornell University
en_US
dc.title
Subsampling Mathematical Relaxations and Average-case Complexity
en_US
dc.type
Working Paper
ethz.journal.title
arXiv
ethz.pages.start
0911.5526
en_US
ethz.size
36 p.
en_US
ethz.identifier.arxiv
0911.5526
ethz.publication.place
Ithaca, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
03841 - Holenstein, Thomas
en_US
ethz.leitzahl.certified
03841 - Holenstein, Thomas
ethz.date.deposited
2017-06-09T09:16:09Z
ethz.source
ECIT
ethz.identifier.importid
imp59364da0a083a76044
ethz.ecitpid
pub:49408
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-13T08:40:25Z
ethz.rosetta.lastUpdated
2021-02-15T17:36:37Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Subsampling%20Mathematical%20Relaxations%20and%20Average-case%20Complexity&rft.jtitle=arXiv&rft.date=2010-11-29&rft.spage=0911.5526&rft.au=Barak,%20Boaz&Hardt,%20Moritz&Holenstein,%20Thomas&Steurer,%20David&rft.genre=preprint&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record