Justin Thaler

Orcid: 0009-0009-2234-6225

According to our database1, Justin Thaler authored at least 79 papers between 2009 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
More Optimizations to Sum-Check Proving.
IACR Cryptol. ePrint Arch., 2024

Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields.
IACR Cryptol. ePrint Arch., 2024

The Sum-Check Protocol over Fields of Small Characteristic.
IACR Cryptol. ePrint Arch., 2024

Field-Agnostic SNARKs from Expand-Accumulate Codes.
Proceedings of the Advances in Cryptology - CRYPTO 2024, 2024

2023
Unlocking the lookup singularity with Lasso.
IACR Cryptol. ePrint Arch., 2023

Customizable constraint systems for succinct arguments.
IACR Cryptol. ePrint Arch., 2023

BabySpartan: Lasso-based SNARK for non-uniform computation.
IACR Cryptol. ePrint Arch., 2023

Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup.
IACR Cryptol. ePrint Arch., 2023

Fiat-Shamir Security of FRI and Related SNARKs.
IACR Cryptol. ePrint Arch., 2023

Jolt: SNARKs for Virtual Machines via Lookups.
IACR Cryptol. ePrint Arch., 2023

sfTestudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup.
Proceedings of the Progress in Cryptology - LATINCRYPT 2023, 2023

Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS.
Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

2022
Quantum Proofs of Proximity.
Quantum, September, 2022

Relative Error Streaming Quantiles.
SIGMOD Rec., 2022

Approximate Degree in Classical and Quantum Computing.
Found. Trends Theor. Comput. Sci., 2022

Proofs, Arguments, and Zero-Knowledge.
Found. Trends Priv. Secur., 2022

(Nearly) All Cardinality Estimators Are Differentially Private.
CoRR, 2022

Order-Invariant Cardinality Estimators Are Differentially Private.
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.
Quantum, 2021

Linear-time zero-knowledge SNARKs for R1CS.
IACR Cryptol. ePrint Arch., 2021

Brakedown: Linear-time and post-quantum SNARKs for R1CS.
IACR Cryptol. ePrint Arch., 2021

2020
Guest Column: Approximate Degree in Classical and Quantum Computing.
SIGACT News, 2020

A Nearly Optimal Lower Bound on the Approximate Degree of AC<sup>0</sup>.
SIAM J. Comput., 2020

On the Power of Statistical Zero Knowledge.
SIAM J. Comput., 2020

Improved Approximate Degree Bounds For $k$-distinctness.
Electron. Colloquium Comput. Complex., 2020

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches.
Electron. Colloquium Comput. Complex., 2020

Hybrid Approach to HPC Cluster Telemetry and Hardware Log Analytics.
Proceedings of the 2020 IEEE High Performance Extreme Computing Conference, 2020

2019
Verifiable Stream Computation and Arthur-Merlin Communication.
SIAM J. Comput., 2019

Ad Hoc Multi-Input Functional Encryption.
IACR Cryptol. ePrint Arch., 2019

Vanishing-Error Approximate Degree and QMA Complexity.
Electron. Colloquium Comput. Complex., 2019

Sign-Rank Can Increase Under Intersection.
Electron. Colloquium Comput. Complex., 2019

Approximate degree, secret sharing, and concentration phenomena.
Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.
Electron. Colloquium Comput. Complex., 2019

2018
The Large-Error Approximate Degree of AC<sup>0</sup>.
Electron. Colloquium Comput. Complex., 2018

2017
Doubly-efficient zkSNARKs without trusted setup.
IACR Cryptol. ePrint Arch., 2017

Full accounting for verifiable outsourcing.
IACR Cryptol. ePrint Arch., 2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.
Electron. Colloquium Comput. Complex., 2017

A high-performance algorithm for identifying frequent items in data streams.
Proceedings of the 2017 Internet Measurement Conference, 2017

Reliably Learning the ReLU in Polynomial Time.
Proceedings of the 30th Conference on Learning Theory, 2017

Determining Tournament Payout Structures for Daily Fantasy Sports.
Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016
Data Stream Verification.
Encyclopedia of Algorithms, 2016

Parallel Peeling Algorithms.
ACM Trans. Parallel Comput., 2016

Approximate Degree and the Complexity of Depth Three Circuits.
Electron. Colloquium Comput. Complex., 2016

Improved Bounds on the Sign-Rank of AC<sup>0</sup>.
Electron. Colloquium Comput. Complex., 2016

On SZK and PP.
Electron. Colloquium Comput. Complex., 2016

Technical Perspective: Catching lies (and mistakes) in offloaded computation.
Commun. ACM, 2016

Space Lower Bounds for Itemset Frequency Sketches.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

A Framework for Estimating Stream Expression Cardinalities.
Proceedings of the 19th International Conference on Database Theory, 2016

Improved Bounds on the Sign-Rank of AC^0.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Dual Polynomials for Collision and Element Distinctness.
Electron. Colloquium Comput. Complex., 2015

Stream Verification.
CoRR, 2015

Streaming Verification in Data Analysis.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Variable Selection is Hard.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Verifiable computation using multiple provers.
IACR Cryptol. ePrint Arch., 2014

Lower Bounds for the Approximate Degree of Block-Composed Functions.
Electron. Colloquium Comput. Complex., 2014

Semi-Streaming Algorithms for Annotated Graph Streams.
Electron. Colloquium Comput. Complex., 2014

Space Lower Bounds for Itemset Frequency Sketches.
CoRR, 2014

Annotations for Sparse Data Streams.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Faster private release of marginals on small databases.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Distribution-independent Reliable Learning.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Time-Optimal Interactive Proofs for Circuit Evaluation.
IACR Cryptol. ePrint Arch., 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.
Electron. Colloquium Comput. Complex., 2013

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.
Electron. Colloquium Comput. Complex., 2013

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.
Electron. Colloquium Comput. Complex., 2013

External-Memory Multimaps.
Algorithmica, 2013

2012
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
Electron. Colloquium Comput. Complex., 2012

Annotations in Data Streams.
Electron. Colloquium Comput. Complex., 2012

Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability.
Proceedings of the Design and Analysis of Algorithms, 2012

Continuous time channels with interference.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

Practical verified computation with streaming interactive proofs.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Faster Algorithms for Privately Releasing Marginals.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Verifiable Computation with Massively Parallel Interactive Proofs.
Proceedings of the 4th USENIX Workshop on Hot Topics in Cloud Computing, 2012

Peeling arguments and double hashing.
Proceedings of the 50th Annual Allerton Conference on Communication, 2012

Hierarchical Heavy Hitters with the Space Saving Algorithm.
Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011
Streaming Graph Computations with a Helpful Advisor.
Electron. Colloquium Comput. Complex., 2011

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

On the zero-error capacity threshold for deletion channels.
Proceedings of the Information Theory and Applications Workshop, 2011

2010
Verifying Computations with Streaming Interactive Proofs.
Electron. Colloquium Comput. Complex., 2010

2009
Graph covers and quadratic minimization.
Proceedings of the 47th Annual Allerton Conference on Communication, 2009


  Loading...