Justin Thaler

Research Fellow
Simons Institute for the Theory of Computing, UC Berkeley
Calvin Lab, Berkeley, CA 94720
jthaler [at] fas [dot] harvard [dot] edu


I am now a Microsoft Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. Before that, I was a Ph.D. student in the Theory of Computation Group at Harvard University, where I was fortunate to be advised by Michael Mitzenmacher. I graduated from Yale University in 2009 with a B.S. in Computer Science and a second major in Mathematics. I am broadly interested in algorithms and computational complexity, especially algorithms for massive data sets, verifiable computation, and computational learning theory.

Ph.D. Thesis

Practical Verified Computation with Streaming Interactive Proofs
Harvard University, 2013.

Research Papers

A. Chakrabarti, G. Cormode, A. McGregor, J. Thaler, and S. Venkatasubramanian
On Interactivity in Arthur-Merlin Communication and Stream Computation
Manuscript.
J. Thaler, V. Vu, M. Walfish, and A. J. Blumberg
Verifiable Computation Using Multiple Provers
In preparation.
M. Bun and J. Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Manuscript.
V. Kanade and J. Thaler
Distribution-Independent Reliable Learning
COLT 2014
J. Jiang, M. Mitzenmacher, and J. Thaler
Parallel Peeling Algorithms
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
CRYPTO 2013
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
ALENEX 2012
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

Talk Slides

  1. Practical Verified Computation with Streaming Interactive Proofs. AT&T Research. Florham Park, March 2013.
    Provides a unified overview of [CCMT12], [CMT10], [CTY12], [CMT12], [TRMP12], and [T13].
    [slides]


Miscellaneous Links

  1. 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.

  2. Yale Probabilistic Networks Group.

  3. http://dimax.rutgers.edu/~jthaler/. A website describing my project on streaming entropy computation during the 2007 REU at DIMACS . 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.