Justin Thaler

IACR Cryptol. ePrint Arch., 2025

Proving CPU Executions in Small Space.

[BibT_eX]

[DOI]

Vineet Nair

Michael Zhu

IACR Cryptol. ePrint Arch., 2025

SNARK Lower Bounds via Communication Complexity.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2025

Speeding Up Sum-Check Proving.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2025

2024

Verifying Jolt zkVM Lookup Semantics.

[BibT_eX]

[DOI]

Carl Kwan

Quang Dao

IACR Cryptol. ePrint Arch., 2024

More Optimizations to Sum-Check Proving.

[BibT_eX]

[DOI]

Quang Dao

IACR Cryptol. ePrint Arch., 2024

Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields.

[BibT_eX]

[DOI]

Quang Dao

IACR Cryptol. ePrint Arch., 2024

The Sum-Check Protocol over Fields of Small Characteristic.

[BibT_eX]

[DOI]

Suyash Bagad

Yuval Domb

IACR Cryptol. ePrint Arch., 2024

Unlocking the Lookup Singularity with Lasso.

[BibT_eX]

[DOI]

Riad S. Wahby

Proceedings of the Advances in Cryptology - EUROCRYPT 2024, 2024

Jolt: SNARKs for Virtual Machines via Lookups.

[BibT_eX]

[DOI]

Arasu Arun

Proceedings of the Advances in Cryptology - EUROCRYPT 2024, 2024

Field-Agnostic SNARKs from Expand-Accumulate Codes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2024, 2024

2023

Customizable constraint systems for succinct arguments.

[BibT_eX]

[DOI]

Riad S. Wahby

IACR Cryptol. ePrint Arch., 2023

BabySpartan: Lasso-based SNARK for non-uniform computation.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2023

Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2023

sfTestudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup.

[BibT_eX]

[DOI]

Proceedings of the Progress in Cryptology - LATINCRYPT 2023, 2023

Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

Fiat-Shamir Security of FRI and Related SNARKs.

[BibT_eX]

[DOI]

Pratyush Ranjan Tiwari

Michal Zajac

Proceedings of the Advances in Cryptology - ASIACRYPT 2023, 2023

2022

Approximate Degree in Classical and Quantum Computing.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2022

Proofs, Arguments, and Zero-Knowledge.

[BibT_eX]

[DOI]

Found. Trends Priv. Secur., 2022

(Nearly) All Cardinality Estimators Are Differentially Private.

[BibT_eX]

[DOI]

Charlie Dickens

Daniel Ting

CoRR, 2022

Order-Invariant Cardinality Estimators Are Differentially Private.

[BibT_eX]

[DOI]

Charlie Dickens

Marcel de Sena Dall'Agnol

Daniel Ting

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Linear-time zero-knowledge SNARKs for R1CS.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2021

Brakedown: Linear-time and post-quantum SNARKs for R1CS.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2021

Quantum Proofs of Proximity.

[BibT_eX]

[DOI]

Tom Gur

Subhayan Roy Moulik

Electron. Colloquium Comput. Complex., 2021

Relative Error Streaming Quantiles.

[BibT_eX]

[DOI]

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

2020

Guest Column: Approximate Degree in Classical and Quantum Computing.

[BibT_eX]

[DOI]

SIGACT News, 2020

Improved Approximate Degree Bounds for k-Distinctness.

[BibT_eX]

[DOI]

Nikhil S. Mande

Shuchen Zhu

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Ad Hoc Multi-Input Functional Encryption.

[BibT_eX]

[DOI]

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

Hybrid Approach to HPC Cluster Telemetry and Hardware Log Analytics.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE High Performance Extreme Computing Conference, 2020

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches.

[BibT_eX]

[DOI]

Amit Chakrabarti

Prantar Ghosh

Proceedings of the Approximation, 2020

2019

Vanishing-Error Approximate Degree and QMA Complexity.

[BibT_eX]

[DOI]

Alexander A. Sherstov

Electron. Colloquium Comput. Complex., 2019

Quantum algorithms and approximating polynomials for composed functions with shared inputs.

[BibT_eX]

[DOI]

Robin Kothari

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

Sign-Rank Can Increase Under Intersection.

[BibT_eX]

[DOI]

Nikhil S. Mande

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The Large-Error Approximate Degree of AC0.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

Approximate Degree, Secret Sharing, and Concentration Phenomena.

[BibT_eX]

[DOI]

Andrej Bogdanov

Nikhil S. Mande

Christopher Williamson

Proceedings of the Approximation, 2019

2018

The polynomial method strikes back: tight quantum query bounds via dual polynomials.

[BibT_eX]

[DOI]

Robin Kothari

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Doubly-Efficient zkSNARKs Without Trusted Setup.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE Symposium on Security and Privacy, 2018

Approximate Degree and the Complexity of Depth Three Circuits.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

A high-performance algorithm for identifying frequent items in data streams.

[BibT_eX]

[DOI]

Proceedings of the 2017 Internet Measurement Conference, 2017

A Nearly Optimal Lower Bound on the Approximate Degree of AC0.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

On the Power of Statistical Zero Knowledge.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Reliably Learning the ReLU in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

Full Accounting for Verifiable Outsourcing.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017

Determining Tournament Payout Structures for Daily Fantasy Sports.

[BibT_eX]

[DOI]

Christopher Musco

Maxim Sviridenko

Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016

Data Stream Verification.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Improved Bounds on the Sign-Rank of AC0.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Electron. Colloquium Comput. Complex., 2016

On SZK and PP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Technical Perspective: Catching lies (and mistakes) in offloaded computation.

[BibT_eX]

[DOI]

Commun. ACM, 2016

Space Lower Bounds for Itemset Frequency Sketches.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

A Framework for Estimating Stream Expression Cardinalities.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Database Theory, 2016

Semi-Streaming Algorithms for Annotated Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Lower Bounds for the Approximate Degree of Block-Composed Functions.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Improved Bounds on the Sign-Rank of AC^0.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Dual Polynomials for Collision and Element Distinctness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Stream Verification.

[BibT_eX]

[DOI]

CoRR, 2015

Streaming Verification in Data Analysis.

[BibT_eX]

[DOI]

Samira Daruki

Suresh Venkatasubramanian

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Variable Selection is Hard.

[BibT_eX]

[DOI]

Dean P. Foster

Howard J. Karloff

Suresh Venkatasubramanian

Proceedings of The 28th Conference on Learning Theory, 2015

Verifiable Stream Computation and Arthur-Merlin Communication.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Annotations in Data Streams.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Verifiable computation using multiple provers.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2014

Space Lower Bounds for Itemset Frequency Sketches.

[BibT_eX]

[DOI]

Edo Liberty

CoRR, 2014

Parallel peeling algorithms.

[BibT_eX]

[DOI]

Jiayang Jiang

Karthekeyan Chandrasekaran

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Annotations for Sparse Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Faster private release of marginals on small databases.

[BibT_eX]

[DOI]

Jonathan R. Ullman

Andrew Wan

Proceedings of the Innovations in Theoretical Computer Science, 2014

Distribution-independent Reliable Learning.

[BibT_eX]

[DOI]

Varun Kanade

Suresh Venkatasubramanian

Proceedings of The 27th Conference on Learning Theory, 2014

2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Time-Optimal Interactive Proofs for Circuit Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Rocco A. Servedio

Li-Yang Tan

Electron. Colloquium Comput. Complex., 2012

Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability.

[BibT_eX]

[DOI]

Proceedings of the Design and Analysis of Algorithms, 2012

Continuous time channels with interference.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

Practical verified computation with streaming interactive proofs.

[BibT_eX]

[DOI]

Graham Cormode

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Faster Algorithms for Privately Releasing Marginals.

[BibT_eX]

[DOI]

Jonathan R. Ullman

Salil P. Vadhan

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Verifiable Computation with Massively Parallel Interactive Proofs.

[BibT_eX]

[DOI]

Proceedings of the 4th USENIX Workshop on Hot Topics in Cloud Computing, 2012

Peeling arguments and double hashing.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual Allerton Conference on Communication, 2012

Hierarchical Heavy Hitters with the Space Saving Algorithm.

[BibT_eX]

[DOI]

Thomas Steinke

Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011

Verifying Computations with Streaming Interactive Proofs.

[BibT_eX]

[DOI]

Graham Cormode

Ke Yi

Proc. VLDB Endow., 2011

Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps

[BibT_eX]

[DOI]

CoRR, 2011

On the zero-error capacity threshold for deletion channels.

[BibT_eX]

[DOI]

Proceedings of the Information Theory and Applications Workshop, 2011

External-Memory Multimaps.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

2010

Streaming Graph Computations with a Helpful Advisor.

[BibT_eX]

[DOI]

Graham Cormode

Proceedings of the Algorithms, 2010

2009

Graph covers and quadratic minimization.

[BibT_eX]

[DOI]

Nicholas Ruozzi