Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INDEPENDENCE:
Reports tagged with independence:
TR09-011 | 31st January 2009
Mark Braverman

#### Poly-logarithmic independence fools AC0 circuits

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

TR16-102 | 4th July 2016
Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

#### Bounded independence vs. moduli

Revisions: 1

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ... more >>> TR17-167 | 3rd November 2017 Chin Ho Lee, Emanuele Viola #### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials Revisions: 1 We construct pseudorandom generators with improved seed length for several classes of tests. First we consider the class of read-once polynomials over GF(2) in$m$variables. For error$\e$we obtain seed length$\tilde O (\log(m/\e)) \log(1/\e)$, where$\tilde O\$ hides lower-order
terms. This is optimal up to the factor ... more >>>

ISSN 1433-8092 | Imprint