Thomas Watson



Interests
Computational complexity theory, and theoretical computer science in general.

Biography
I am a postdoctoral research scholar at the University of Toronto, where my advisor is Toniann Pitassi. Here is my curriculum vitae. I received my Ph.D. in theoretical computer science in 2013 from the University of California, Berkeley, where my advisor was Luca Trevisan. Here is my dissertation. I received my undergraduate degree with majors in computer science, mathematics, and computer engineering in 2008 from the University of Wisconsin - Madison, where my advisor was Dieter van Melkebeek.

Research
Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Preprint.
Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. RANDOM 2014.
Thomas Watson. Sampling Versus Unambiguous Nondeterminism in Communication Complexity. Preprint.
Thomas Watson. The Complexity of Deciding Statistical Properties of Samplable Distributions. STACS 2014.
Thomas Watson. The Complexity of Estimating Min-Entropy. CC 2015.
Thomas Watson. Time Hierarchies for Sampling Distributions. ITCS 2013.
Thomas Watson. Advice Lower Bounds for the Dense Model Theorem. STACS 2013.
Thomas Watson. Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. CJTCS 2014.
Anindya De and Thomas Watson. Extractors and Lower Bounds for Locally Samplable Sources. RANDOM 2011.
Thomas Watson. Pseudorandom Generators for Combinatorial Checkerboards. CCC 2011.
Thomas Watson. Query Complexity in Errorless Hardness Amplification. RANDOM 2011.
Thomas Watson. Relativized Worlds Without Worst-Case to Average-Case Reductions for NP. RANDOM 2010.
Dieter van Melkebeek and Thomas Watson. Time-Space Efficient Simulations of Quantum Computations. TOC 2012.

Teaching
CS 70: Discrete Mathematics and Probability Theory, UC Berkeley, Summer 2013
CS 70: Discrete Mathematics and Probability Theory, UC Berkeley, Spring 2012
CS 170: Efficient Algorithms and Intractable Problems, UC Berkeley, Fall 2011

Courses
Courses taken at Madison, Berkeley, and Toronto