Andrej Bogdanov

Pravesh Kothari

Electron. Colloquium Comput. Complex., 2023

Classical simulation of one-query quantum distinguishers.

[BibT_eX]

[DOI]

TsunMing Cheung

John C. S. Lui

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

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

Hitting Sets for Regular Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Unconditionally Secure Computation Against Low-Complexity Leakage.

[BibT_eX]

[DOI]

Akshayaram Srinivasan

J. Cryptol., 2021

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

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2021

Acyclicity Programming for Sigma-Protocols.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2021

Bounded Indistinguishability for Simple Sources.

[BibT_eX]

[DOI]

Yuval Filmus

Avi Kaplan

Akshayaram Srinivasan

Electron. Colloquium Comput. Complex., 2021

On quantum versus classical query complexity.

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

Tsun Ming Cheung

Electron. Colloquium Comput. Complex., 2021

A Gentle Introduction to Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the ICT Innovations 2021. Digital Transformation, 2021

2020

Direct Sum and Partitionability Testing over General Groups.

[BibT_eX]

[DOI]

Gautam Prakriya

Electron. Colloquium Comput. Complex., 2020

Learning and Testing Variable Partitions.

[BibT_eX]

[DOI]

Baoxiang Wang

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

2019

Approximate degree, secret sharing, and concentration phenomena.

[BibT_eX]

[DOI]

Nikhil S. Mande

Justin Thaler

Christopher Williamson

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

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

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

Small bias requires large formulas.

[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

Threshold Secret Sharing Requires a Linear Size Alphabet.

[BibT_eX]

[DOI]

Siyao Guo

Ilan Komargodski

Electron. Colloquium Comput. Complex., 2016

2015

Homomorphic evaluation requires depth.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2015

On the Hardness of Learning with Rounding over Small Modulus.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2015

Bounded Indistinguishability and the Complexity of Recovering Secrets.

[BibT_eX]

[DOI]

Emanuele Viola

Christopher Williamson

Electron. Colloquium Comput. Complex., 2015

2014

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

[BibT_eX]

[DOI]

Christina Brzuska

Electron. Colloquium Comput. Complex., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Hard Functions for Low-Degree Polynomials over Prime Fields.

[BibT_eX]

[DOI]

Akinori Kawachi

Hidetoki Tanaka

ACM Trans. Comput. Theory, 2013

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

Sparse extractor families for all the entropy.

[BibT_eX]

[DOI]

Siyao Guo

Electron. Colloquium Comput. Complex., 2012

On the security of Goldreich's one-way function.

[BibT_eX]

[DOI]

Youming Qiao

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

Electron. Colloquium Comput. Complex., 2011

Pseudorandomness for read-once formulas.

[BibT_eX]

[DOI]

Periklis A. Papakonstantinou

Andrew Wan

Electron. Colloquium Comput. Complex., 2011

A Dichotomy for Local Small-Bias Generators.

[BibT_eX]

[DOI]

Benny Applebaum

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

Pseudorandom Bits for Polynomials.

[BibT_eX]

[DOI]

Emanuele Viola

SIAM J. Comput., 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

2008

The Complexity of Distinguishing Markov Random Fields.

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the Approximation, 2008

2007

Hardness amplification for errorless heuristics.

[BibT_eX]

[DOI]

Muli Safra

Electron. Colloquium Comput. Complex., 2007

2006

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Average-Case Complexity.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Hoeteck Wee

Proceedings of the Approximation, 2004

2002

Lower Bounds for Testing Bipartiteness in Dense Graphs

[BibT_eX]

[DOI]

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