3 papers
cs.CC2025
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…
cs.CC2024
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…
cs.DS2024
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 …