Justin Thaler

Associate Professor
Georgetown University
Department of Computer Science

St. Mary's Hall, Room 354
3700 Reservoir Road NW
Washington, DC 20057

e-mail: justin [dot] thaler [at] georgetown [dot] edu

About Me

I am broadly interested in algorithms and computational complexity, primarily focusing on the following three research goals.
I am an Associate Professor at Georgetown University and a Research Partner at a16z crypto research. Prior to joining Georgetown, I spent two years as a Research Scientist at Yahoo Labs in New York. Before that, I was a Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. I received my Ph.D. from the Theory of Computation Group at Harvard University, where I was fortunate to be advised by Michael Mitzenmacher, and I graduated from Yale University in 2009 with a B.S. in Computer Science and a second major in Mathematics.

I am currently at a16z crypto research and on leave from Georgetown.

Teaching

Current and Former Students and Postdocs

Research Papers

2023
  • The Sum-Check Protocol over Fields of Small Characteristic
    Justin Thaler
    Manuscript
  • BabySpartan: Lasso-based SNARK for non-uniform computation
    Srinath Setty, and Justin Thaler
    Manuscript
  • Jolt: SNARKs for Virtual Machines via Lookups
    Arasu Arun Srinath Setty, and Justin Thaler
    Manuscript
  • Unlocking the lookup singularity with Lasso
    Srinath Setty, Justin Thaler, and Riad Wahby
    Manuscript
  • Customizable constraint systems for succinct arguments
    Srinath Setty, Justin Thaler, and Riad Wahby
    Manuscript
  • Fiat-Shamir Security of FRI and Related SNARKs
    Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, and Michał Zając
    Asiacrypt 2023
  • Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup
    Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, and Justin Thaler
    Latincrypt 2023
  • Brakedown: Linear-time and post-quantum SNARKs for R1CS
    Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby
    CRYPTO 2023
2022
  • Approximate Degree in Quantum and Classical Computing
    Mark Bun and Justin Thaler
    Foundations and Trends in Theoretical Computer Science
  • Order-Invariant Cardinality Estimators Are Differentially Private
    Charlie Dickens, Daniel Ting, and Justin Thaler
    NeurIPS 2022
2021
  • Proofs, Arguments, and Zero-Knowledge
    Justin Thaler
    Foundations and Trends in Theoretical Computer Science
  • Guest Column: Approximate Degree in Classical and Quantum Computing
    Mark Bun and Justin Thaler
    ACM SIGACT News, January 2021
  • Quantum Proofs of Proximity
    Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, and Justin Thaler
    TQC 2021, Quantum
2020
  • Vanishing-Error Approximate Degree and QMA Complexity
    Alexander A. Sherstov and Justin Thaler
    Accepted to CJTCS
  • Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
    Amit Chakrabarti, Prantar Ghosh, and Justin Thaler
    RANDOM 2020
  • Improved Approximate Degree Bounds For k-Distinctness
    Nikhil Mande, Justin Thaler, and Shuchen Zhu
    TQC 2020
  • Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler
    QIP 2020, CCC 2020
  • Ad Hoc Multi-Input Functional Encryption
    Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler
    ITCS 2020
2019
  • Approximate Degree, Secret Sharing, and Concentration Phenomena
    Andrej Bogdanov, Nikhil Mande, Justin Thaler, and Christopher Williamson
    RANDOM 2019
  • The Large-Error Approximate Degree of AC^0
    Mark Bun and Justin Thaler
    RANDOM 2019; Theory of Computing (Special Issue for RANDOM 2019)
  • Sign-Rank Can Increase Under Intersection
    Mark Bun, Nikhil Mande, Justin Thaler
    ICALP 2019; TOCT
  • Quantum Algorithms and Approximating Polynomials for Composed Functions With Shared Inputs
    Mark Bun, Robin Kothari, Justin Thaler
    SODA 2019, full version in Quantum.
2018
  • Doubly-efficient zkSNARKs without trusted setup
    Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish
    IEEE Symposium on Security and Privacy (S&P) 2018
  • The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
    Mark Bun, Robin Kothari, Justin Thaler
    STOC 2018; Preliminary version in QIP 2018 (plenary talk). Invited to Theory of Computing.
  • Approximate Degree and the Complexity of Depth Three Circuits
    Mark Bun and Justin Thaler
    RANDOM 2018
2017
  • Full Accounting for Verifiable Outsourcing
    Riad S. Wahby, Ye Ji, Andrew J. Blumberg, abhi shelat, Justin Thaler, Michael Walfish, and Thomas Wies
    CCS 2017
  • A High-Performance Algorithm for Identifying Frequent Items in Data Streams
    Daniel Anderson, Pryce Bevan, Kevin Lang, Edo Liberty, Lee Rhodes, and Justin Thaler
    IMC 2017
  • A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
    Mark Bun and Justin Thaler
    FOCS 2017. SICOMP (Special Issue for FOCS '17)
  • On the Power of Statistical Zero Knowledge
    Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan
    FOCS 2017. SICOMP (special issue for FOCS '17)
  • Reliably Learning the ReLU in Polynomial Time
    Surbhi Goel, Varun Kanade, Adam Klivans and Justin Thaler
    COLT 2017
  • Determining Tournament Payout Structures for Daily Fantasy Sports
    Christopher Musco, Maxim Sviridenko, and Justin Thaler
    ALENEX 2017; Invited to special issue of ACM Journal of Experimental Algorithmics for ALENEX 2017
2016
  • Dual Polynomials for Collision and Element Distinctness
    Mark Bun and Justin Thaler
    Theory of Computing
  • Improved Bounds on the Sign-Rank of AC$^0$
    Mark Bun and Justin Thaler
    ICALP 2016
  • Lower Bounds for the Approximate Degree of Block-Composed Functions
    Justin Thaler
    ICALP 2016
  • Semi-Streaming Algorithms for Annotated Graph Streams
    Justin Thaler
    ICALP 2016
  • Space Lower Bounds for Itemset Frequency Sketches
    Edo Liberty, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman,
    PODS 2016
  • A Framework for Estimating Stream Expression Cardinalities
    Anirban Dasgupta, Kevin Lang, Lee Rhodes, and Justin Thaler
    ICDT 2016; Best Newcomer Paper Award; Invited to special issue of TODS for ICDT 2016
2015
  • Streaming Verification in Data Analysis
    Samira Daruki, Justin Thaler, and Suresh Venkatasubramanian
    ISAAC 2015
  • Variable Selection is Hard
    Dean Foster, Howard Karloff, and Justin Thaler
    COLT 2015
  • Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
    Mark Bun and Justin Thaler
    ICALP 2015
  • Verifiable Stream Computation and Arthur-Merlin Communication
    Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian
    CCC 2015, SICOMP
  • A Note on the GKR Protocol
    Justin Thaler
    Manuscript
  • Verifiable Computation Using Multiple Provers
    Andrew J. Blumberg, Justin Thaler, Victor Vu, and Michael Walfish
    Manuscript
2014
  • Distribution-Independent Reliable Learning
    Varun Kanade and Justin Thaler
    COLT 2014
  • Parallel Peeling Algorithms
    Jiayang Jiang, Michael Mitzenmacher, and Justin Thaler
    SPAA 2014; Winner of Best Paper Award; full version in TOPC (special issue for SPAA 2014)
  • Annotations in Data Streams
    Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler
    ACM Transactions on Algorithms
  • Faster Private Release of Marginals on Small Databases
    Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan
    ITCS 2014
  • Annotations for Sparse Data Streams
    Amit Chakrabarti, Graham Cormode, Navin Goyal. and Justin Thaler
    SODA 2014
2013
  • Time-Optimal Interactive Proofs for Circuit Evaluation
    Justin Thaler
    CRYPTO 2013
  • Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
    Mark Bun and Justin Thaler
    ICALP 2013; Winner of Best Paper award for Track A; Journal version in Information and Computation (special issue for ICALP 2013)
2012
  • Faster Algorithms for Privately Releasing Marginals
    Justin Thaler, Jonathan Ullman, and Salil Vadhan
    ICALP 2012
  • Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
    Li-Yang Tan, Rocco Servedio, and Justin Thaler
    COLT 2012
  • Peeling Arguments and Double Hashing
    Michael Mitzenmacher, and Justin Thaler
    Allerton 2012 (Invited Paper)
  • Verifiable Computation with Massively Parallel Interactive Proofs
    Justin Thaler, Mike Roberts, Michael Mitzenmacher, and Hanspeter Pfister
    HotCloud 2012
  • Continuous Time Channels with Interference
    Ioanna Ivan, Michael Mitzenmacher, Justin Thaler, and Henry Yuen
    ISIT 2012
  • Hierarchical Heavy Hitters with the Space Saving Algorithm
    Michael Mitzenmacher, Thomas Steinke, and Justin Thaler
    ALENEX 2012
  • Practical Verified Computation with Streaming Interactive Proofs
    Graham Cormode, Michael Mitzenmacher, and Justin Thaler
    ITCS 2012
  • Verifying Computations with Streaming Interactive Proofs
    Graham Cormode, Justin Thaler, and Ke Yi
    VLDB 2012
  • Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability
    Michael T. Goodrich, Dan Hirschberg, Michael Mitzenmacher, and Justin Thaler
    MedAlg 2012
2011
  • On the Zero-Error Capacity Threshold for Deletion Channels
    Ian Kash, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman
    ITA 2011
  • External Memory Multimaps
    Elaine Angelino, Michael Mitzenmacher, and Justin Thaler
    ISAAC 2011; Algorithmica (special issue for ISAAC 2011)
2010
  • Streaming Graph Computations with a Helpful Advisor
    Graham Cormode, Michael Mitzenmacher, and Justin Thaler
    ESA 2010; Algorithmica 2013
2009
  • Graph Covers and Quadratic Minimization
    Nicholas Ruozzi, Sekhar Tatikonda, and Justin Thaler
    Allerton 2009
Expository Articles

Academic Service

I have been, or currently am, a member of the following program committees:

Open Source Software


Slides From Survey Talks

Miscellaneous Links