Justin Thaler

ORCID

Publication Activity (10 Years)

Years Active: 2009-2023
Publications (10 Years): 95

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

IACR Cryptol. ePrint Arch.

APPROX-RANDOM

Publications

Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. CRYPTO (2) (2023)
Srinath T. V. Setty, Justin Thaler
BabySpartan: Lasso-based SNARK for non-uniform computation. IACR Cryptol. ePrint Arch. 2023 (2023)
Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, Michal Zajac
Fiat-Shamir Security of FRI and Related SNARKs. IACR Cryptol. ePrint Arch. 2023 (2023)
Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Unlocking the lookup singularity with Lasso. IACR Cryptol. ePrint Arch. 2023 (2023)
Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Customizable constraint systems for succinct arguments. IACR Cryptol. ePrint Arch. 2023 (2023)
Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý
Relative Error Streaming Quantiles. J. ACM 70 (5) (2023)
Arasu Arun, Srinath T. V. Setty, Justin Thaler
Jolt: SNARKs for Virtual Machines via Lookups. IACR Cryptol. ePrint Arch. 2023 (2023)
Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, Michal Zajac
Fiat-Shamir Security of FRI and Related SNARKs. ASIACRYPT (2) (2023)
Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler
sfTestudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. LATINCRYPT (2023)
Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. IACR Cryptol. ePrint Arch. 2023 (2023)
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. Quantum 6 (2022)
Justin Thaler
Proofs, Arguments, and Zero-Knowledge. Found. Trends Priv. Secur. 4 (2-4) (2022)
Charlie Dickens, Justin Thaler, Daniel Ting
Order-Invariant Cardinality Estimators Are Differentially Private. NeurIPS (2022)
Charlie Dickens, Justin Thaler, Daniel Ting
(Nearly) All Cardinality Estimators Are Differentially Private. CoRR (2022)
Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý
Relative Error Streaming Quantiles. SIGMOD Rec. 51 (1) (2022)
Mark Bun, Justin Thaler
Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci. 15 (3-4) (2022)
Mark Bun, Justin Thaler
. Theory Comput. 17 (2021)
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. CoRR (2021)
Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021 (2021)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory 13 (4) (2021)
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. Electron. Colloquium Comput. Complex. 28 (2021)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum 5 (2021)
Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý
Relative Error Streaming Quantiles. PODS (2021)
Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby
Linear-time zero-knowledge SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021 (2021)
Nikhil S. Mande, Justin Thaler, Shuchen Zhu
Improved Approximate Degree Bounds for k-Distinctness. TQC (2020)
Justin Thaler, Woong Shin, Steven Roberts, James H. Rogers, Todd Rosedahl
Hybrid Approach to HPC Cluster Telemetry and Hardware Log Analytics. HPEC (2020)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On the Power of Statistical Zero Knowledge. SIAM J. Comput. 49 (4) (2020)
Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý
Relative Error Streaming Quantiles. CoRR (2020)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Computational Complexity Conference (2020)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. CoRR (2020)
Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler
Ad Hoc Multi-Input Functional Encryption. ITCS (2020)
Nikhil S. Mande, Justin Thaler, Shuchen Zhu
Improved Approximate Degree Bounds For k-distinctness. CoRR (2020)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. Electron. Colloquium Comput. Complex. 27 (2020)
Mark Bun, Justin Thaler
. SIAM J. Comput. 49 (4) (2020)
Mark Bun, Justin Thaler
Guest Column: Approximate Degree in Classical and Quantum Computing. SIGACT News 51 (4) (2020)
Nikhil S. Mande, Justin Thaler, Shuchen Zhu
Improved Approximate Degree Bounds For $k$-distinctness. Electron. Colloquium Comput. Complex. 27 (2020)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. APPROX-RANDOM (2020)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16 (2020)
Mark Bun, Justin Thaler
. APPROX-RANDOM (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. CoRR (2019)
Alexander A. Sherstov, Justin Thaler
Vanishing-Error Approximate Degree and QMA Complexity. CoRR (2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
Approximate degree, secret sharing, and concentration phenomena. Electron. Colloquium Comput. Complex. 26 (2019)
Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler
Ad Hoc Multi-Input Functional Encryption. IACR Cryptol. ePrint Arch. 2019 (2019)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication. SIAM J. Comput. 48 (4) (2019)
Alexander A. Sherstov, Justin Thaler
Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR (2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
Approximate Degree, Secret Sharing, and Concentration Phenomena. APPROX-RANDOM (2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
Approximate degree, secret sharing, and concentration phenomena. CoRR (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. ICALP (2019)
Mark Bun, Justin Thaler
Approximate Degree and the Complexity of Depth Three Circuits. APPROX-RANDOM (2018)
Mark Bun, Robin Kothari, Justin Thaler
The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. 25 (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR (2018)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 25 (2018)
Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, Michael Walfish
Doubly-Efficient zkSNARKs Without Trusted Setup. IEEE Symposium on Security and Privacy (2018)
Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, Thomas Wies
Full Accounting for Verifiable Outsourcing. CCS (2017)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On the Power of Statistical Zero Knowledge. FOCS (2017)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 24 (2017)
Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, Michael Walfish
Doubly-efficient zkSNARKs without trusted setup. IACR Cryptol. ePrint Arch. 2017 (2017)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR (2017)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. 24 (2017)
Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler
Reliably Learning the ReLU in Polynomial Time. COLT (2017)
Mark Bun, Justin Thaler
. CoRR (2017)
Mark Bun, Justin Thaler
. FOCS (2017)
Daniel Anderson, Pryce Bevan, Kevin J. Lang, Edo Liberty, Lee Rhodes, Justin Thaler
A high-performance algorithm for identifying frequent items in data streams. Internet Measurement Conference (2017)
Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, Thomas Wies
Full accounting for verifiable outsourcing. IACR Cryptol. ePrint Arch. 2017 (2017)
Christopher Musco, Maxim Sviridenko, Justin Thaler
Determining Tournament Payout Structures for Daily Fantasy Sports. ALENEX (2017)
Daniel Anderson, Pryce Bevan, Kevin J. Lang, Edo Liberty, Lee Rhodes, Justin Thaler
A High-Performance Algorithm for Identifying Frequent Items in Data Streams. CoRR (2017)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 23 (2016)
Justin Thaler
Semi-Streaming Algorithms for Annotated Graph Streams. ICALP (2016)
Mark Bun, Justin Thaler
Approximate Degree and the Complexity of Depth Three Circuits. Electron. Colloquium Comput. Complex. 23 (2016)
Mark Bun, Justin Thaler
Improved Bounds on the Sign-Rank of AC^0. ICALP (2016)
Edo Liberty, Michael Mitzenmacher, Justin Thaler, Jonathan R. Ullman
Space Lower Bounds for Itemset Frequency Sketches. PODS (2016)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On SZK and PP. CoRR (2016)
Christopher Musco, Maxim Sviridenko, Justin Thaler
Determining Tournament Payout Structures for Daily Fantasy Sports. CoRR (2016)
Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, Justin Thaler
A Framework for Estimating Stream Expression Cardinalities. ICDT (2016)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On SZK and PP. Electron. Colloquium Comput. Complex. 23 (2016)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. Theory Comput. 12 (1) (2016)
Michael Mitzenmacher, Justin Thaler
Technical Perspective: Catching lies (and mistakes) in offloaded computation. Commun. ACM 59 (2) (2016)
Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler
Reliably Learning the ReLU in Polynomial Time. CoRR (2016)
Jiayang Jiang, Michael Mitzenmacher, Justin Thaler
Parallel Peeling Algorithms. ACM Trans. Parallel Comput. 3 (1) (2016)
Justin Thaler
Lower Bounds for the Approximate Degree of Block-Composed Functions. ICALP (2016)
Justin Thaler
Stream Verification. CoRR (2015)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. Electron. Colloquium Comput. Complex. 22 (2015)
Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, Justin Thaler
A Framework for Estimating Stream Expression Cardinalities. CoRR (2015)
Samira Daruki, Justin Thaler, Suresh Venkatasubramanian
Streaming Verification in Data Analysis. CoRR (2015)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. CoRR (2015)
Samira Daruki, Justin Thaler, Suresh Venkatasubramanian
Streaming Verification in Data Analysis. ISAAC (2015)
Dean P. Foster, Howard J. Karloff, Justin Thaler
Variable Selection is Hard. COLT (2015)
Mark Bun, Justin Thaler
Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput. 243 (2015)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication. Computational Complexity Conference (2015)
Mark Bun, Justin Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) (2015)
Justin Thaler
Semi-Streaming Algorithms for Annotated Graph Streams. CoRR (2014)
Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler
Annotations for Sparse Data Streams. SODA (2014)
Andrew J. Blumberg, Justin Thaler, Victor Vu, Michael Walfish
Verifiable computation using multiple provers. IACR Cryptol. ePrint Arch. 2014 (2014)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler
Annotations in Data Streams. ACM Trans. Algorithms 11 (1) (2014)
Justin Thaler
Semi-Streaming Algorithms for Annotated Graph Streams. Electron. Colloquium Comput. Complex. 21 (2014)

Justin Thaler.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Justin Thaler