Chin Ho Lee

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

2020

More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials.

[BibT_eX]

[DOI]

Theory Comput., 2020

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

2017

Some Limitations of the Sum of Small-Bias Distributions.

[BibT_eX]

[DOI]

Theory Comput., 2017

The coin problem for product tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

2016

Bounded independence plus noise fools products.

[BibT_eX]

[DOI]

Elad Haramaty

Electron. Colloquium Comput. Complex., 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

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]