Chin Ho Lee

Email: chinho.lee@ncsu.edu
Office: Engineering Building II (EB2), Room 3292
Address: 890 Oval Drive, Box 8206, Raleigh, NC 27695

I am an assistant professor at the Computer Science Department of North Carolina State University.

Before joining NCSU, I was a postdoc at Harvard University from 2021-2023 and Columbia University from 2019-2021. I received my PhD at Northeastern University, and my Masters and Bachelor at the Chinese University of Hong Kong (CUHK).

Research interests: Theoretical Computer Science: randomness in computation, pseudorandomness, Boolean functions, trace reconstruction.

If you are interested in my research, feel free to email me and I would be happy to chat with you more about it. If you would like to do theory research with me, you must be proficient in discrete math and basic probability.

Teaching

Preprints

Pseudorandomness, symmetry, smoothing: II
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
[arXiv]

Publications

Trace reconstruction from local statistical queries
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
RANDOM 2024
[arXiv]
Boosting uniformity in quasirandom groups: fast and simple
Harm Derksen, Chin Ho Lee, Emanuele Viola
FOCS 2024
[arXiv]
Pseudorandomness, symmetry, smoothing: I
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
CCC 2024
[arXiv]
On the Power of Regular and Permutation Branching Programs
Chin Ho Lee, Edward Pyne, Salil Vadhan
RANDOM 2023
[ECCC]
Approximate Trace Reconstruction from a Single Trace
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
SODA 2023
[arXiv]
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], [Journal]
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]