Andrej Bogdanov

Prashant Nalini Vasudevan

Rohit Chatterjee

Yunqi Li

IACR Cryptol. ePrint Arch., 2025

Are Neural Networks Collision Resistant?

[BibT_eX]

[DOI]

Nikolaj I. Schwartzbach

Riccardo Zecchina

IACR Cryptol. ePrint Arch., 2025

Estimating Euclidean Distance to Linearity.

[BibT_eX]

[DOI]

Lorenzo Taschin

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Sample Efficient Search to Decision for kLIN.

[BibT_eX]

[DOI]

Kel Zin Tan

Proceedings of the Advances in Cryptology - CRYPTO 2025, 2025

2024

Low-Degree Security of the Planted Random Subgraph Problem.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 22nd International Conference, 2024

Towards a Scalable Reference-Free Evaluation of Generative Models.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

CDS Composition of Multi-round Protocols.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2024, 2024

2023

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Proceedings of the Theory of Cryptography - 21st International Conference, 2023

Nondeterministic Interactive Refutations for Nearest Boolean Vector.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Bounded Simultaneous Messages.

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Csirmaz's Duality Conjecture and Threshold Secret Sharing.

[BibT_eX]

[DOI]

Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

Classical Simulation of One-Query Quantum Distinguishers.

[BibT_eX]

[DOI]

Tsun Ming Cheung

John C. S. Lui

Proceedings of the Approximation, 2023

2022

Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage.

[BibT_eX]

[DOI]

Akshayaram Srinivasan

J. Cryptol., 2022

Public-Key Encryption from Continuous LWE.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Public-Key Encryption from Homogeneous CLWE.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

Bounded Indistinguishability for Simple Sources.

[BibT_eX]

[DOI]

Yuval Filmus

Avi Kaplan

Akshayaram Srinivasan

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Hitting Sets for Regular Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

On quantum versus classical query complexity.

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

Tsun Ming Cheung

Electron. Colloquium Comput. Complex., 2021

Acyclicity Programming for Sigma-Protocols.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 19th International Conference, 2021

A Gentle Introduction to Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the ICT Innovations 2021. Digital Transformation, 2021

Direct Sum and Partitionability Testing over General Groups.

[BibT_eX]

[DOI]

Gautam Prakriya

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Learning and Testing Variable Partitions.

[BibT_eX]

[DOI]

Baoxiang Wang

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Non-interactive Composition of Sigma-Protocols via Share-then-Hash.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - ASIACRYPT 2020, 2020

2019

XOR Codes and Sparse Learning Parity with Noise.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Manuel Sabin

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

When are large codes possible for AVCs?

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

Unconditionally Secure Computation Against Low-Complexity Leakage.

[BibT_eX]

[DOI]

Akshayaram Srinivasan

Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

Approximate Degree, Secret Sharing, and Concentration Phenomena.

[BibT_eX]

[DOI]

Nikhil S. Mande

Justin Thaler

Christopher Williamson

Proceedings of the Approximation, 2019

2018

XOR Codes and Sparse Random Linear Equations with Noise.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Manuel Sabin

Electron. Colloquium Comput. Complex., 2018

Approximate degree of AND via Fourier analysis.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Small Bias Requires Large Formulas.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Pseudorandom Functions: Three Decades Later.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Complete Classi fication of Generalized Santha-Vazirani Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Complete Classification of Generalized Santha-Vazirani Sources.

[BibT_eX]

[DOI]

CoRR, 2017

Approximate Bounded Indistinguishability.

[BibT_eX]

[DOI]

Christopher Williamson

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Pseudorandom Functions: Three Decades Later.

[BibT_eX]

[DOI]

Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016

Homomorphic Evaluation Requires Depth.

[BibT_eX]

[DOI]

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

On the Hardness of Learning with Rounding over Small Modulus.

[BibT_eX]

[DOI]

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

Threshold Secret Sharing Requires a Linear Size Alphabet.

[BibT_eX]

[DOI]

Siyao Guo

Ilan Komargodski

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

Bounded Indistinguishability and the Complexity of Recovering Secrets.

[BibT_eX]

[DOI]

Emanuele Viola

Christopher Williamson

Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

2015

On Basing Size-Verifiable One-Way Functions on NP-Hardness.

[BibT_eX]

[DOI]

Christina Brzuska

Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

2014

Candidate weak pseudorandom functions in AC<sup>0</sup> ○ MOD<sub>2</sub>.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Sparse extractor families for all the entropy.

[BibT_eX]

[DOI]

Siyao Guo

Proceedings of the Innovations in Theoretical Computer Science, 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

A Dichotomy for Local Small-Bias Generators.

[BibT_eX]

[DOI]

Benny Applebaum

Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Pseudorandomness for Linear Length Branching Programs and Stack Machines.

[BibT_eX]

[DOI]

Periklis A. Papakonstantinou

Andrew Wan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On Extracting Common Random Bits From Correlated Sources.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Homomorphic encryption from codes.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2011

Input Locality and Hardness Amplification.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

Hard Functions for Low-Degree Polynomials over Prime Fields.

[BibT_eX]

[DOI]

Akinori Kawachi

Hidetoki Tanaka

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Pseudorandomness for Read-Once Formulas.

[BibT_eX]

[DOI]

Periklis A. Papakonstantinou

Andrew Wan

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Computational Complexity of Estimating MCMC Convergence Time.

[BibT_eX]

[DOI]

Nayantara Bhatnagar

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A better tester for bipartiteness?

[BibT_eX]

[DOI]

Fan Li

CoRR, 2010

The Computational Complexity of Estimating Convergence Time

[BibT_eX]

[DOI]

Nayantara Bhatnagar

CoRR, 2010

Hard Instances for Satisfiability and Quasi-one-way Functions.

[BibT_eX]

[DOI]

Kunal Talwar

Andrew Wan

Proceedings of the Innovations in Computer Science, 2010

2009

Pseudorandomness for Width 2 Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

On the Security of Goldreich's One-Way Function.

[BibT_eX]

[DOI]

Youming Qiao

Proceedings of the Approximation, 2009

2008

The Complexity of Distinguishing Markov Random Fields.

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the Approximation, 2008

2007

Pseudorandom Bits for Polynomials.

[BibT_eX]

[DOI]

Emanuele Viola

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Hardness Amplification for Errorless Heuristics.

[BibT_eX]

[DOI]

Muli Safra

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Average-Case Complexity.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2006

2005

Pseudorandom generators for low degree polynomials.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

More on Noncommutative Polynomial Identity Testing.

[BibT_eX]

[DOI]

Hoeteck Wee

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Power-aware base station positioning for sensor networks.

[BibT_eX]

[DOI]

Elitza N. Maneva

Samantha J. Riesenfeld

Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

Lower Bounds for Testing Bipartiteness in Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes.

[BibT_eX]

[DOI]

Hoeteck Wee

Proceedings of the Approximation, 2004

2003

On Worst-Case to Average-Case Reductions for NP Problems.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

2002

Mechanical Translation of I/O Automaton Specifications into First-Order Logic.

[BibT_eX]

[DOI]

Stephen J. Garland

Nancy A. Lynch

Proceedings of the Formal Techniques for Networked and Distributed Systems, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Kenji Obata