Approximation Resistant Predicates from Pairwise Independence

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Per Austrin Articles by Elchanan Mossel

2008 IEEE 23rd Annual Conference on Computational Complexity

June 22-June 26

ISBN: 978-0-7695-3169-4

	ASCII Text	x
	Per Austrin, Elchanan Mossel, "Approximation Resistant Predicates from Pairwise Independence," Computational Complexity, Annual IEEE Conference on, pp. 249-258, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008.

	BibTex	x
	@article{ 10.1109/CCC.2008.20, author = {Per Austrin and Elchanan Mossel}, title = {Approximation Resistant Predicates from Pairwise Independence}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2008}, issn = {1093-0159}, pages = {249-258}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2008.20}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Approximation Resistant Predicates from Pairwise Independence SN - 1093-0159 SP249 EP258 A1 - Per Austrin, A1 - Elchanan Mossel, PY - 2008 KW - Max k-CSP KW - Unique Games Conjecture KW - Approximation Resistance KW - Pairwise Independence VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Per Austrin

Elchanan Mossel

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.20

We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate P is approximation resistant if there exists a balanced pairwise independent distribution over [q]^k whose support is contained in the set of satisfying assignments to P.

Index Terms:

Max k-CSP, Unique Games Conjecture, Approximation Resistance, Pairwise Independence

Citation:

Per Austrin, Elchanan Mossel, "Approximation Resistant Predicates from Pairwise Independence," ccc, pp.249-258, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.