NDLI: Explicit Optimal Hardness via Gaussian Stability Results

Please wait, while we are loading the content...

Explicit Optimal Hardness via Gaussian Stability Results

Content Provider	ACM Digital Library
Author	De, Anindya Mossel, Elchanan
Copyright Year	2013
Abstract	The results of Raghavendra [2008] show that assuming Khot’s Unique Games Conjecture [2002], for every constraint satisfaction problem there exists a generic semidefinite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate exactly the Unique Games hardness of the problem. Obtaining an explicit optimal approximation scheme and the corresponding approximation factor is a difficult challenge for each specific approximation problem. Khot et al. [2004] established a general approach for determining the exact approximation factor and the corresponding optimal rounding algorithm for any given constraint satisfaction problem. However, this approach crucially relies on results explicitly proving optimal partitions in the Gaussian space. Until recently, Borell’s result [1985] was the only nontrivial Gaussian partition result known. In this article we derive the first explicit optimal approximation algorithm and the corresponding approximation factor using a new result on Gaussian partitions due to Isaksson and Mossel [2012]. This Gaussian result allows us to determine the exact Unique Games Hardness of MAX-3-EQUAL. In particular, our results show that Zwick’s algorithm for this problem achieves the optimal approximation factor and prove that the approximation achieved by the algorithm is ≈ 0.796 as conjectured by Zwick [1998]. We further use the previously known optimal Gaussian partitions results to obtain a new Unique Games Hardness factor for MAX-k-CSP: Using the well-known fact that jointly normal pairwise independent random variables are fully independent, we show that the UGC hardness of Max-k-CSP is $⌈(\textit{k}+1)/2⌉$ $2^{k™1},$ improving on results of Austrin and Mossel [2009].
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2505766
Volume Number	5
Issue Number	4
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-11-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Gaussian stability Dictatorship test Unique games conjecture
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Explicit Optimal Hardness via Gaussian stability results

Explicit optimal hardness via gaussian stability results (1202).

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

On the usefulness of predicates

Complexity theoretic hardness results for query learning

Complexity of Approximating CSP with Balance / Hard Constraints

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Spectral Algorithms for Unique Games

Explicit Optimal Hardness via Gaussian Stability Results

Similar Documents

Explicit Optimal Hardness via Gaussian stability results

Explicit optimal hardness via gaussian stability results (1202).

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

On the usefulness of predicates

Complexity theoretic hardness results for query learning

Complexity of Approximating CSP with Balance / Hard Constraints

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Spectral Algorithms for Unique Games

Explicit Optimal Hardness via Gaussian Stability Results