6 papers
Pseudorandom bits for non-commutative programs
Chin Ho Lee, Emanuele Viola
We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1. We consider read-once group-products over a fi…
Fourier growth of structured -polynomials and applications
JarosÅaw BÅasiok, Peter Ivanov, Yaonan Jin +3
We analyze the Fourier growth, i.e. the Fourier weight at level (denoted ), of various well-studied classes of "structured" -polynomials. This stud…
Boosting uniformity in quasirandom groups: fast and simple
Harm Derksen, Chin Ho Lee, Emanuele Viola
We study the communication complexity of multiplying elements from the group in the number-on-forehead model with parties. We prove a lower bound…
Pseudorandomness, symmetry, smoothing: II
Harm Derksen, Peter Ivanov, Chin Ho Lee +1
We prove several new results on the Hamming weight of bounded uniform and small-bias distributions. We exhibit bounded-uniform distributions whose weight is anti-concentrated, matc…
Trace reconstruction from local statistical queries
Xi Chen, Anindya De, Chin Ho Lee +1
The goal of trace reconstruction is to reconstruct an unknown -bit string given only independent random traces of , where a random trace of is obtained by passing …
Pseudorandomness, symmetry, smoothing: I
Harm Derksen, Peter Ivanov, Chin Ho Lee +1
We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tes…