Justin Thaler

Assistant Professor
Georgetown University
Department of Computer Science

St. Mary's Hall
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.
Since Fall 2016, I have been an Assistant Professor in the Department of Computer Science at Georgetown University. Prior to joining Georgetown, I spent two years as a Research Scientist at Yahoo Labs in New York. I was also 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.

Teaching

Research Papers  

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)
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; Invited to the special issue of SICOMP for FOCS '17
  • On the Power of Statistical Zero Knowledge
    Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan
    FOCS 2017; Invited to the special issue of SICOMP 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
  • Approximate Degree and the Complexity of Depth Three Circuits
    Mark Bun and Justin Thaler
    Manuscript
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
  • 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; Accepted to 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 program committee or a reviewer for the following:

Open Source Software


Slides From Survey Talks

Miscellaneous Links

Last Updated

May 12, 2018.