Thomas Watson



Dunn Hall 315
Department of Computer Science
University of Memphis
Memphis, TN 38152
Thomas.Watson@memphis.edu


I am an assistant professor of computer science at the University of Memphis. Here is my curriculum vitae. Previously, I was a postdoctoral research scholar at the University of Toronto, where my advisor was Toniann Pitassi. 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.


My research interests include computational complexity theory, and theoretical computer science in general.

Research
Thomas Watson. A ZPPNP[1] Lifting Theorem. Preprint.
Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for BPP. FOCS 2017.
Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for PNP. CCC 2017.
Thomas Watson. Quadratic Simulations of Merlin-Arthur Games. Preprint.
Thomas Watson. Communication Complexity of Statistical Distance. RANDOM 2017.
Thomas Watson. Communication Complexity with Small Advantage. Preprint.
Mika Göös, Rahul Jain, and Thomas Watson. Extension Complexity of Independent Set Polytopes. FOCS 2016.
Mika Göös, T.S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication vs. Partition Number. ICALP 2017.
Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic Communication vs. Partition Number. FOCS 2015.
Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. ICALP 2016.
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles Are Nonnegative Juntas. STOC 2015.
Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. ITCS 2015.
Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. RANDOM 2014.
Thomas Watson. Nonnegative Rank vs. Binary Rank. CJTCS 2016.
Thomas Watson. The Complexity of Deciding Statistical Properties of Samplable Distributions. STACS 2014.
Thomas Watson. The Complexity of Estimating Min-Entropy. CC 2016.
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
University of Memphis: COMP 8992: Computational Complexity (Fall 2017)
University of Memphis: COMP 4992: Competitive Programming and Technical Interviews (Fall 2017)
University of Memphis: COMP 7612: Foundations of Computing (Spring 2017)
University of Memphis: COMP 4601: Models of Computation (Fall 2016)
University of Toronto: CSC 2401: Computational Complexity Theory (Fall 2015)
University of California, Berkeley: CS 70: Discrete Mathematics and Probability Theory (Summer 2013, Spring 2012)
University of California, Berkeley: CS 170: Efficient Algorithms and Intractable Problems (Fall 2011)