Change search
ReferencesLink to record
Permanent link

Direct link
Randomly supported independence and resistance
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Univ Toronto, Dept Comp Sci.ORCID iD: 0000-0001-8217-0158
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2011 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 1, 1-27 p.Article in journal (Refereed) Published
Abstract [en]

We prove that for any positive integers q and k there is a constant c(q,k) such that a uniformly random set of c(q,k)n(k) log n vectors in [q](n) with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument gives the stronger bound, c(q,k)n(k). Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting c(q,2)t(2) input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c'(q,k), such that a randomly selected set of cardinality c'(q,k)n(k) points is unlikely to support a balanced k-wise independent distribution and, for some c > 0, a random predicate accepting ct(2)/logt input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least (32/33).2(t) inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.

Place, publisher, year, edition, pages
2011. Vol. 40, no 1, 1-27 p.
Keyword [en]
k-wise independence, constraint satisfaction, approximation resistance
National Category
Computer Science
URN: urn:nbn:se:kth:diva-31300DOI: 10.1137/100783534ISI: 000287697400001ScopusID: 2-s2.0-79952948997OAI: diva2:405153
Swedish Research Council, 50394001

QC 20150629

Available from: 2011-03-21 Created: 2011-03-14 Last updated: 2015-06-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, PerHåstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
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

Altmetric score

Total: 69 hits
ReferencesLink to record
Permanent link

Direct link