Justin Thaler

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

Field-Agnostic SNARKs from Expand-Accumulate Codes.

[BibT_eX]

[DOI]

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

2023

Unlocking the lookup singularity with Lasso.

[BibT_eX]

[DOI]

Riad S. Wahby

IACR Cryptol. ePrint Arch., 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

Fiat-Shamir Security of FRI and Related SNARKs.

[BibT_eX]

[DOI]

Pratyush Ranjan Tiwari

Michal Zajac

IACR Cryptol. ePrint Arch., 2023

Jolt: SNARKs for Virtual Machines via Lookups.

[BibT_eX]

[DOI]

Arasu Arun

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

2022

Quantum Proofs of Proximity.

[BibT_eX]

[DOI]

Quantum, September, 2022

Relative Error Streaming Quantiles.

[BibT_eX]

[DOI]

SIGMOD Rec., 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

Daniel Ting

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

2021

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

[BibT_eX]

[DOI]

Robin Kothari

Quantum, 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

2020

Guest Column: Approximate Degree in Classical and Quantum Computing.

[BibT_eX]

[DOI]

SIGACT News, 2020

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

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

SIAM J. Comput., 2020

On the Power of Statistical Zero Knowledge.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Improved Approximate Degree Bounds For $k$-distinctness.

[BibT_eX]

[DOI]

Nikhil S. Mande

Shuchen Zhu

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Amit Chakrabarti

Prantar Ghosh

Suresh Venkatasubramanian

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

2019

Verifiable Stream Computation and Arthur-Merlin Communication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Ad Hoc Multi-Input Functional Encryption.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2019

Vanishing-Error Approximate Degree and QMA Complexity.

[BibT_eX]

[DOI]

Alexander A. Sherstov

Electron. Colloquium Comput. Complex., 2019

Sign-Rank Can Increase Under Intersection.

[BibT_eX]

[DOI]

Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2019

Approximate degree, secret sharing, and concentration phenomena.

[BibT_eX]

[DOI]

Andrej Bogdanov

Nikhil S. Mande

Christopher Williamson

Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

The Large-Error Approximate Degree of AC0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

2017

Doubly-efficient zkSNARKs without trusted setup.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

Full accounting for verifiable outsourcing.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.

[BibT_eX]

[DOI]

Robin Kothari

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Proceedings of the 2017 Internet Measurement Conference, 2017

Reliably Learning the ReLU in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 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

Parallel Peeling Algorithms.

[BibT_eX]

[DOI]

Jiayang Jiang

ACM Trans. Parallel Comput., 2016

Approximate Degree and the Complexity of Depth Three Circuits.

[BibT_eX]

[DOI]

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

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

Variable Selection is Hard.

[BibT_eX]

[DOI]

Dean P. Foster

Howard J. Karloff

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Verifiable computation using multiple provers.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Semi-Streaming Algorithms for Annotated Graph Streams.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Space Lower Bounds for Itemset Frequency Sketches.

[BibT_eX]

[DOI]

Edo Liberty

Karthekeyan Chandrasekaran

CoRR, 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

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Time-Optimal Interactive Proofs for Circuit Evaluation.

[BibT_eX]

[DOI]

Suresh Venkatasubramanian

IACR Cryptol. ePrint Arch., 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

External-Memory Multimaps.

[BibT_eX]

[DOI]

Algorithmica, 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

Annotations in Data Streams.

[BibT_eX]

[DOI]

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

Streaming Graph Computations with a Helpful Advisor.

[BibT_eX]

[DOI]

Graham Cormode

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

2010

Verifying Computations with Streaming Interactive Proofs.

[BibT_eX]

[DOI]

Graham Cormode

Ke Yi

Electron. Colloquium Comput. Complex., 2010

2009

Graph covers and quadratic minimization.

[BibT_eX]

[DOI]

Nicholas Ruozzi