Chin Ho Lee

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Pseudorandomness, Symmetry, Smoothing: I.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

Trace Reconstruction from Local Statistical Queries.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

On the Power of Regular and Permutation Branching Programs.

[BibT_eX]

[DOI]

Edward Pyne

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2023

Approximate Trace Reconstruction from a Single Trace.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Fourier Growth of Regular Branching Programs.

[BibT_eX]

[DOI]

Edward Pyne

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2022

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Fourier growth of structured 𝔽<sub>2</sub>-polynomials and applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications.

[BibT_eX]

[DOI]

CoRR, 2021

Polynomial-time trace reconstruction in the smoothed complexity model.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Fractional Pseudorandom Generators from Any Fourier Level.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2019

Bounded Independence versus Symmetric Tests.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Fourier bounds and pseudorandom generators for product tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

Bounded Independence Plus Noise Fools Products.

[BibT_eX]

[DOI]

Elad Haramaty

SIAM J. Comput., 2018

2017

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

The coin problem for product tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

2016

Bounded independence vs. moduli.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

Homomorphic evaluation requires depth.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2015

Some limitations of the sum of small-bias distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2012

On the depth complexity of homomorphic encryption schemes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Limits of provable security for homomorphic encryption.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

Homomorphic encryption from codes.

[BibT_eX]

[DOI]