Justin Thaler 


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:
M. Bun, R. Kothari, and J. Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials QIP 2018 (plenary talk) 
M. Bun and J. Thaler
Approximate Degree and the Complexity of Depth Three Circuits Manuscript. 
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 HighPerformance 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. Invited to the special issue of SICOMP for FOCS '17. 
A. Bouland, L. Chen, D. Holden, J. Thaler, P.N. Vasudevan
On the Power of Statistical Zero Knowledge FOCS 2017. Invited to the special issue of SICOMP for FOCS '17. 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 ALENEX 2017 
M. Bun and J. Thaler
Improved Bounds on the SignRank of AC^0 ICALP 2016 
J. Thaler
Lower Bounds for the Approximate Degree of BlockComposed Functions ICALP 2016 
J. Thaler
SemiStreaming 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. 
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 ConstantDepth Circuits ICALP 2015 
A. Chakrabarti, G. Cormode, A. McGregor, J. Thaler, and S. Venkatasubramanian
Verifiable Stream Computation and ArthurMerlin Communication CCC 2015 
J. Thaler
A Note on the GKR Protocol Manuscript. 
A. J. Blumberg, J. Thaler, V. Vu, and M. Walfish
Verifiable Computation Using Multiple Provers Manuscript. 
V. Kanade and J. Thaler
DistributionIndependent 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
TimeOptimal Interactive Proofs for Circuit Evaluation CRYPTO 2013 
M. Bun and J. Thaler
Dual Lower Bounds for Approximate Degree and MarkovBernstein 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
CacheOblivious 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, LY. Tan, and J. Thaler
AttributeEfficient Learning and WeightDegree 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 ZeroError 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 409442. 
N. Ruozzi, J. Thaler, and S. Tatikonda
Graph Covers and Quadratic Minimization Allerton 2009 
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 . 