19 citations · 22 across the 10 of their papers we have counts for
12 papers
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…
Approximate Trace Reconstruction from a Single Trace
Xi Chen, Anindya De, Chin Ho Lee +2
The well-known trace reconstruction problem is the problem of inferring an unknown source string from independent "traces", i.e. copies of that have been corr…
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen, Anindya De, Chin Ho Lee +2
In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string from independent "traces", which are cop…
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…
Polynomial-time trace reconstruction in the low deletion rate regime
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is transmitted through a probabilistic \emph{deletion channel} which independently deletes ea…
Polynomial-time trace reconstruction in the smoothed complexity model
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is sent through a probabilistic \emph{deletion channel} which independently deletes each bit…
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee +2
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit Fourier tail bounds for classes…
Fourier bounds and pseudorandom generators for product tests
Chin Ho Lee
We study the Fourier spectrum of functions which can be written as a product of Boolean functions on disjoint -bit inputs. We pro…
Homomorphic encryption from codes
Andrej Bogdanov, Chin Ho Lee
We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-ba…