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

- Understanding the power of low-degree polynomials to approximate Boolean functions. Answering these questions has a variety of applications, especially to quantum computing, learning theory, and computational complexity theory.
- Designing protocols for proving the correctness of computations (possibly in zero-knowlege), in which the prover and verifier are highly efficient both in theory and in practice.
- Developing efficient streaming and sketching algorithms for basic tasks that are often performed on large data sets.

I am an Associate Professor at Georgetown University, where I have been since Fall 2016. 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.

- COSC 544 -- Probabilistic Proof Systems (Fall 2020, Fall 2017)
- COSC 548 -- Streaming Algorithms (Fall 2018, Fall 2016)
- ANLY 550 -- Structures and Algorithms for Analytics (Spring 2019, Spring 2018, Spring 2017)
- ANLY 558 -- Advanced Algorithms for Analytics (Spring 2021)

- Shuchen Zhu (PhD Student)
- Nikhil Mande (former postdoc, now a postdoc at CWI)

- TCC 2021
- ESA 2021
- TCC 2020
- STOC 2019
- SOSA 2019
- SODA 2018
- FSTTCS 2017
- ICALP 2016
- ALENEX 2016
- SDM 2015

- I am a co-creator and core contributor to DataSketches, an open source library of production quality streaming algorithms for a variety of important query classes, including identifying frequent items, unique count queries, quantiles, and subset sum queries.

- Interactive Proofs. Presented at the Proofs, Consensus, and Decentralizing Society Boot Camp, Simons Institute for the Theory of Computing, August 2019. Video of Part 1 Video of Part 2
- A Crash Course on Fast Interactive Proofs. A followup to the talk above, presented in September 2019 during the Simons Institute semester on Proofs, Consensus, and Decentralizing Society.
- Approximate Degree: A Survey. Presented at the 2018 CMO workshop on Analytic Techniques in Theoretical Computer Science.
- 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".
- Chebyshev Polynomials, Approximate Degree, and their Applications. FOCS 2016 Workshop on "(Some) Orthogonal Polynomials and their Applications to TCS". [talk video available here]
- Approximate Degree and the Method of Dual Polynomials. Columbia University Theory Seminar, November 2014.

Provides a unified overview of [BT13], [BT14], and [Tha14]. - 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.

- Yale
Probabilistic Networks Group.

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