5 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…
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…
Resilient functions: Optimized, simplified, and generalized
Peter Ivanov, Emanuele Viola
An -bit boolean function is resilient to coalitions of size if any fixed set of bits is unlikely to influence the function when the other bits are chosen uniformly…
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…