Chin Ho Lee

Email: chinho.lee@ncsu.edu
Office: EBII 3292

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 doing research in theoretical computer science with me, feel free to email me.

---

Teaching

• CSC 707: Computational Complexity (Spring 2024)
• CSC 791/591: CS Theory Toolkit (Fall 2023)
• CS 229BR: Analysis of Boolean Functions (Fall 2022) [Notes]

---

Publications

• 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]