Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Conditional Inapproximability and Limited Independence
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
2008 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. These are problems in which we are given a set of constraints, each constraint acting on some k variables, and are asked to find an assignment to the variables satisfyingas many of the constraints as possible.

A predicate P : [q]ᵏ → {0, 1} is said to be approximation resistant if it is intractable to approximate the corresponding CSP problem to within a factor which is better than what is expected from a completely random assignment to the variables. We prove that if the Unique Games Conjecture is true, then a sufficient condition for a predicate P :[q]ᵏ → {0, 1} to be approximation resistant is that there exists a pairwise independent distribution over [q]ᵏ which is supported on the set of satisfying assignments Pˉ¹(1) of P.

We also study predicates P : {0, 1}² → {0, 1} on two boolean variables. The corresponding CSP problems include fundamental computational problems such as Max Cut and Max 2-Sat. For any P, we give an algorithm and a Unique Games-based hardness result. Under a certain geometric conjecture, the ratios of these two results are shown to match exactly. In addition, this result explains why additional constraints beyond the standard “triangle inequalities” do not appear to help when solving these problems. Furthermore,we are able to use the generic hardness result to obtain improved hardness for the special cases of Max 2-Sat and Max 2-And. For Max 2-Sat, we obtain a hardness of αLLZ + ε ≈ 0.94016, where αLLZ is the approximation ratio of the algorithm due to Lewin, Livnat and Zwick. For Max 2-And, we obtain a hardness of 0.87435. For both of these problems, our results surprisingly demonstrate that the special case of balanced instances (instances where every variable occurs positively and negatively equally often) is not the hardest. Furthermore, the result for Max 2-And also shows that Max Cut is not the hardest 2-CSP.

Motivated by the result for k-CSP problems, and their fundamental importance in computer science in general, we then study t-wise independent distributions with random support. We prove that, with high probability, poly(q) ・ n² random points in [q]ⁿ can support a pairwise independent distribution. Then, again with high probability, we show that (poly(q) ・n)ᵗ log(nᵗ) random points in [q]ⁿ can support a t-wise independent distribution. For constant t and q, we show that Ω(nᵗ) random points are necessary in order to be able to support a t-wise independent balanced distribution with non-negligible probability. Also, we show that every subset of [q]ⁿ with size at least qⁿ(1−poly(q)ˉᵗ) can support a t-wise independent distribution.

Finally, we prove a certain noise correlation bound for low-degree functions with small Fourier coefficients. This type of result is generally useful in hardness of approximation, derandomization, and additive combinatorics.

Place, publisher, year, edition, pages
Stockholm: KTH , 2008. , ix, 139 p.
Series
Trita-CSC-A, ISSN 1653-5723 ; 2008:18
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-9422ISBN: 978-91-7415-179-4 (print)OAI: oai:DiVA.org:kth-9420DiVA: diva2:114147
Public defence
2008-11-28, D3, KTH, Lindstedtsvägen 5, Stockholm, 13:00 (English)
Opponent
Supervisors
Note
QC 20100630Available from: 2008-11-11 Created: 2008-10-31 Last updated: 2010-07-01Bibliographically approved

Open Access in DiVA

Full Text(1126 kB)216 downloads
File information
File name FULLTEXT01.pdfFile size 1126 kBChecksum SHA-512
d1112df2bcab275e920e3bc4def4a518a4da73aaf31dd78a9e5530d543aab79c779c0b3a1e9b51aacefef9af7c7f104ff89003122fbae763d9777ab21663c557
Type fulltextMimetype application/pdf

Authority records BETA

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 216 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 303 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf