## Chin Ho Lee

Email: chlee (at) seas.harvard.edu

I am a postdoc at the Computer Science Department of Harvard University, hosted by Salil Vadhan.

I do research in theoretical computer science. My main research interest is to understand the role of randomness in computation. Specifically, I am interested in pseudorandomness, and its applications to other areas such as the analysis of Boolean functions, coding theory and foundations of cryptography. I also like to work on statistical reconstruction problems such as trace reconstruction.

Previously I was a postdoc at Columbia University, hosted by Rocco Servedio. I completed my PhD at Northeastern University under the guidance of Emanuele Viola. I did my Master's in Computer Science and Engineering (advised by Andrej Bogdanov) and Bachelor's in Mathematics at the Chinese University of Hong Kong. During my PhD, I visited Amnon Ta-Shma at Tel Aviv University in Summer and Fall of 2018. I was also a visiting graduate student at the Simons Institute in UC Berkeley in 2015 Fall, and Harvard University during the year of 2014-2015.

### Publications

• Fourier Growth of Regular Branching Programs
Chin Ho Lee, Edward Pyne, Salil Vadhan
RANDOM 2022
[ECCC]
• Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
SODA 2022
[arXiv]
• Fourier growth of structured $$\mathbb{F}_2$$-polynomials and applications
Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
RANDOM 2021 (Invited to Special Issue)
[arXiv]
• Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty
CCC 2021
[arXiv]
• Polynomial-time trace reconstruction in the low deletion rate regime
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
ITCS 2021
[arXiv]
• Polynomial-time trace reconstruction in the smoothed complexity model
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
SODA 2021 (Invited to Special Issue)
[arXiv]
• More on bounded independence plus noise: Pseudorandom generators for read-once polynomials
Chin Ho Lee and Emanuele Viola
Theory of Computing, Volume 16 (7), 2020
[Journal]
• Fourier bounds and pseudorandom generators for product tests
Chin Ho Lee
CCC 2019
[ECCC]
• Bounded Independence versus Symmetric Tests
Ravi Boppana, Johan Håstad, Chin Ho Lee and Emanuele Viola
Transactions on Computation Theory, Volume 11 Issue 4, 2019
(A preliminary version using different techniques appeared in RANDOM 2016)
[Journal]
• The coin problem for product tests
Chin Ho Lee and Emanuele Viola
Transactions on Computation Theory, Volume 10, Issue 3, 2018
[Journal]
• Bounded independence plus noise fools products
Elad Haramaty, Chin Ho Lee and Emanuele Viola
CCC 2017
SIAM Journal on Computing, Volume 47, Issue 2, 2018
[Journal], [ECCC]
• Some Limitations of the Sum of Small-bias Distributions
Chin Ho Lee and Emanuele Viola
Theory of Computing, Volume 13 (16), 2017
[Journal]
• Homomorphic evaluation requires depth
Andrej Bogdanov and Chin Ho Lee
TCC 2016A
[ECCC]
• Limits of provable security for homomorphic encryption
Andrej Bogdanov and Chin Ho Lee
CRYPTO 2013
[ECCC]