Justin Thaler

Georgetown University
Department of Computer Science
St. Mary's Hall
3700 Reservoir Road NW
Washington, DC 20057
justin [dot] thaler [at] georgetown [dot] edu

Biography. I am 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.

Research Interests. I am broadly interested in algorithms and computational complexity. Examples of my research goals include:


Research Papers

M. Bun and J. Thaler
Approximate Degree and the Complexity of Depth Three Circuits
R. S. Wahby, Y. Ji, A. J. Blumberg, a. shelat, J. Thaler, M. Walfish, and T. Wies
Full Accounting for Verifiable Outsourcing
CCS 2017
D. Anderson, P. Bevin, K. Lang, E. Liberty, L. Rhodes, and J. Thaler
A High-Performance Algorithm for Identifying Frequent Items in Data Streams
IMC 2017
M. Bun and J. Thaler
A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
FOCS 2017
A. Bouland, L. Chen, D. Holden, J. Thaler, P.N. Vasudevan
On the Power of Statistical Zero Knowledge
FOCS 2017
Note: an earlier version of this manscript was entitled "On SZK and PP".
S. Goel, V. Kanade, A. Klivans, and J. Thaler
Reliably Learning the ReLU in Polynomial Time
COLT 2017
M. Bun and J. Thaler
Dual Polynomials for Collision and Element Distinctness
Theory of Computing
C. Musco, M. Sviridenko, and J. Thaler
Determining Tournament Payout Structures for Daily Fantasy Sports
M. Bun and J. Thaler
Improved Bounds on the Sign-Rank of AC^0
ICALP 2016
J. Thaler
Lower Bounds for the Approximate Degree of Block-Composed Functions
ICALP 2016
J. Thaler
Semi-Streaming Algorithms for Annotated Graph Streams
ICALP 2016
E. Liberty, M. Mitzenmacher, J. Thaler, and J. Ullman
Space Lower Bounds for Itemset Frequency Sketches
PODS 2016
A. Dasgupta, K. Lang, L. Rhodes, and J. Thaler
A Framework for Estimating Stream Expression Cardinalities
ICDT 2016. Best Newcomer Paper Award. Invited to TODS (special issue for ICDT 2016).
S. Daruki, J. Thaler, and S. Venkatasubramanian
Streaming Verification in Data Analysis
ISAAC 2015
D. Foster, H. Karloff, and J. Thaler
Variable Selection is Hard
COLT 2015
M. Bun and J. Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
ICALP 2015
A. Chakrabarti, G. Cormode, A. McGregor, J. Thaler, and S. Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication
CCC 2015
J. Thaler
A Note on the GKR Protocol
A. J. Blumberg, J. Thaler, V. Vu, and M. Walfish
Verifiable Computation Using Multiple Provers
V. Kanade and J. Thaler
Distribution-Independent Reliable Learning
COLT 2014
J. Jiang, M. Mitzenmacher, and J. Thaler
Parallel Peeling Algorithms
SPAA 2014. Winner of Best Paper Award. Accepted to TOPC (special issue for SPAA 2014).
A. Chakrabarti, G. Cormode, A. McGregor, and J. Thaler
Annotations in Data Streams
[Note: This paper supersedes a preliminary version by Chakrabarti, Cormode, and McGregor that appeared in ICALP 2009.]
Accepted to ACM Transactions on Algorithms
K. Chandrasekaran, J. Thaler, J. Ullman, and A. Wan
Faster Private Release of Marginals on Small Databases
ITCS 2014
A. Chakrabarti, G. Cormode, N. Goyal, and J. Thaler
Annotations for Sparse Data Streams
SODA 2014
J. Thaler
Time-Optimal Interactive Proofs for Circuit Evaluation
M. Bun and J. Thaler
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
ICALP 2013. Winner of Best Paper Award for Track A.
Journal version accepted to Information and Computation (special issue for ICALP 2013).
M. Mitzenmacher and J. Thaler
Peeling Arguments and Double Hashing
Allerton 2012 (Invited Paper)
M. T. Goodrich, D. Hirschberg, M. Mitzenmacher, and J. Thaler
Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability
MedAlg 2012
J. Thaler, J. Ullman, and S. Vadhan
Faster Algorithms for Privately Releasing Marginals
ICALP 2012
R. Servedio, L-Y. Tan, and J. Thaler
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
COLT 2012
J. Thaler, M. Roberts, M. Mitzenmacher, and H. Pfister
Verifiable Computation with Massively Parallel Interactive Proofs
HotCloud 2012
I. Ivan, M. Mitzenmacher, J. Thaler, and H. Yuen
Continuous Time Channels with Interference
ISIT 2012
M. Mitzenmacher, T. Steinke, and J. Thaler
Hierarchical Heavy Hitters with the Space Saving Algorithm
G. Cormode, M. Mitzenmacher, and J. Thaler
Practical Verified Computation with Streaming Interactive Proofs
ITCS 2012
E. Angelino, M. Goodrich, M. Mitzenmacher, and J. Thaler
External Memory Multimaps
ISAAC 2011. Journal version accepted to special issue of Algorithmica.
G. Cormode, J. Thaler, and K. Yi
Verifying Computations with Streaming Interactive Proofs
VLDB 2012
I. Kash, M. Mitzenmacher, J. Thaler, and J. Ullman
On the Zero-Error Capacity Threshold for Deletion Channels
2011 Information Theory and Applications Workshop
G. Cormode, M. Mitzenmacher, and J. Thaler
Streaming Graph Computations with a Helpful Advisor
ESA 2010. Journal version in Algorithmica: Volume 65, Issue 2 (2013), pages 409-442.
N. Ruozzi, J. Thaler, and S. Tatikonda
Graph Covers and Quadratic Minimization
Allerton 2009

Expository Articles

M. Mitzenmacher and J. Thaler
Technical Perspective: Catching Lies (and Mistakes) in Offloaded Computation
CACM, February 2016
J. Thaler
Stream Verification
A short article surveying models and algorithms for stream verification. An abridged version of the article appears in in Springer's Encyclopedia of Algorithms .

Academic Service

I have served on, or will serve on, the following Program Committees
  • SODA 2018
  • FSTTCS 2017
  • ICALP 2016
  • ALENEX 2016
  • SDM 2015
  • Talk Slides

    1. Verifiable Computing: Between Theory and Practice. Presented at the STOC 2017 Theory Fest Workshop on "Probabilistically checkable and interactive proofs (PCP/IP): between theory and practice".
    2. Chebyshev Polynomials, Approximate Degree, and their Applications. FOCS 2016 Workshop on "(Some) Orthogonal Polynomials and their Applications to TCS". [talk video available here]
    3. Approximate Degree and the Method of Dual Polynomials. Columbia University Theory Seminar, November 2014.
      Provides a unified overview of [BT13], [BT14], and [Tha14].
    4. Modern Verifiable Computation. A 3-hour tutorial on interactive proofs and argument systems. Presented at 2016 Summer School on Secure and Oblivious Computation and Outsourcing at University of Notre Dame.

    Miscellaneous Links

    1. I am a co-creator and core contributor to Data Sketches, an open source library of production quality streaming algorithms for a variety of important query classes, including identifying frequent items, computing unique counts, and quantiles.

    2. An expository blog post (up-to-date as of September 2013) I wrote surveying recent efforts toward developing practical protocols for verifiable computation. I hope the post will help make sense of this extremely active area.

    3. Yale Probabilistic Networks Group.

    4. A website describing my project on streaming entropy computation during the 2007 REU at DIMACS . Note that I can no longer maintain the webpage, and the links to code on the site are now broken; however, the code can be accessed directly here. The site contains implementations of the algorithms described in A Near-Optimal Algorithm for Computing the Entropy of a Stream, by A. Chakrabarti, G. Cormode, and A. McGregor (In ACM Transactions on Algorithms, 6 (2010), no. 3, pg. 1-21). The REU was a terrific experience.