Chin Ho Lee

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Boosting Uniformity in Quasirandom Groups: Fast and Simple.

[BibT_eX]

[DOI]

Harm Derksen

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

Approximate Trace Reconstruction from a Single Trace.

[BibT_eX]

[DOI]

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

On the Power of Regular and Permutation Branching Programs.

[BibT_eX]

[DOI]

Edward Pyne

Salil P. Vadhan

Proceedings of the Approximation, 2023

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

Fourier Growth of Regular Branching Programs.

[BibT_eX]

[DOI]

Edward Pyne

Salil P. Vadhan

Proceedings of the Approximation, 2022

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

Fourier Growth of Structured 𝔽<sub>2</sub>-Polynomials and Applications.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 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]

Proceedings of the 34th Computational Complexity Conference, 2019

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

Bounded Independence Plus Noise Fools Products.

[BibT_eX]

[DOI]

Elad Haramaty

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Homomorphic Evaluation Requires Depth.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 13th International Conference, 2016

Bounded Independence vs. Moduli.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Some limitations of the sum of small-bias distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2013

Limits of Provable Security for Homomorphic Encryption.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

On the depth complexity of homomorphic encryption schemes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

Homomorphic encryption from codes.

[BibT_eX]

[DOI]