Thomas Watson



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

I am an associate professor of computer science at the University of Memphis and a member of the theory group here.

Previously, I was a postdoctoral research scholar at the University of Toronto, advised by Toniann Pitassi.

I received my Ph.D. in computer science in 2013 from the University of California, Berkeley, advised by 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, advised by Dieter van Melkebeek.

Here is my curriculum vitae. My research interests include computational complexity theory, and theoretical computer science in general.

Book

•Complexity in Computer Science

Funding

•NSF grant CCF-1942742: CAREER: Structural Communication Complexity
•NSF grant CCF-1657377: CRII: AF: Developing and Applying Connections Between Communication Complexity and Query Complexity

Research

•Complexity of Fault Tolerant Query Complexity
Ramita Maharjan and Thomas Watson. FSTTCS 2022
•Erdò‹s-Selfridge Theorem for Nonmonotone CNFs
Md Lutfar Rahman and Thomas Watson. SWAT 2022
•6-Uniform Maker-Breaker Game Is PSPACE-Complete
Md Lutfar Rahman and Thomas Watson. STACS 2021, Combinatorica 2023
•When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. RANDOM 2020
•Tractable Unordered 3-CNF Games
Md Lutfar Rahman and Thomas Watson. LATIN 2020, CC 2025
•A Lower Bound for Sampling Disjoint Sets
Mika Göös and Thomas Watson. RANDOM 2019, TOCT 2020
•Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
Toniann Pitassi, Morgan Shirley, and Thomas Watson. ICALP 2020, CC 2021
•Amplification with One NP Oracle Query
Thomas Watson. ICALP 2019, CC 2022
•Complexity of Unordered CNF Games
Md Lutfar Rahman and Thomas Watson. ISAAC 2018, TOCT 2020
•A ZPPNP[1] Lifting Theorem
Thomas Watson. STACS 2019, TOCT 2020
•Query-to-Communication Lifting for BPP
Mika Göös, Toniann Pitassi, and Thomas Watson. FOCS 2017, SICOMP 2020
•Query-to-Communication Lifting for PNP
Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. CCC 2017, CC 2019
•Quadratic Simulations of Merlin-Arthur Games
Thomas Watson. LATIN 2018, TOCT 2020
•Communication Complexity of Statistical Distance
Thomas Watson. RANDOM 2017, TOCT 2018
•Communication Complexity with Small Advantage
Thomas Watson. CCC 2018, CC 2020
•Extension Complexity of Independent Set Polytopes
Mika Göös, Rahul Jain, and Thomas Watson. FOCS 2016, SICOMP 2018
•Randomized Communication vs. Partition Number
Mika Göös, T.S. Jayram, Toniann Pitassi, and Thomas Watson. ICALP 2017, TOCT 2018
•Deterministic Communication vs. Partition Number
Mika Göös, Toniann Pitassi, and Thomas Watson. FOCS 2015, SICOMP 2018
•The Landscape of Communication Complexity Classes
Mika Göös, Toniann Pitassi, and Thomas Watson. ICALP 2016, CC 2018
•Rectangles Are Nonnegative Juntas
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. STOC 2015, SICOMP 2016
•Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
Mika Göös, Toniann Pitassi, and Thomas Watson. ITCS 2015, Algorithmica 2016
•Communication Complexity of Set-Disjointness for All Probabilities
Mika Göös and Thomas Watson. RANDOM 2014, TOC 2016
•Nonnegative Rank vs. Binary Rank
Thomas Watson. CJTCS 2016
•The Complexity of Deciding Statistical Properties of Samplable Distributions
Thomas Watson. STACS 2014, TOC 2015
•The Complexity of Estimating Min-Entropy
Thomas Watson. CC 2016
•Time Hierarchies for Sampling Distributions
Thomas Watson. ITCS 2013, SICOMP 2014
•Advice Lower Bounds for the Dense Model Theorem
Thomas Watson. STACS 2013, TOCT 2014
•Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem
Thomas Watson. CJTCS 2014
•Extractors and Lower Bounds for Locally Samplable Sources
Anindya De and Thomas Watson. RANDOM 2011, TOCT 2012
•Pseudorandom Generators for Combinatorial Checkerboards
Thomas Watson. CCC 2011, CC 2013
•Query Complexity in Errorless Hardness Amplification
Thomas Watson. RANDOM 2011, CC 2015
•Relativized Worlds Without Worst-Case to Average-Case Reductions for NP
Thomas Watson. RANDOM 2010, TOCT 2012
•Time-Space Efficient Simulations of Quantum Computations
Dieter van Melkebeek and Thomas Watson. TOC 2012

Teaching

•COMP 8613: Computational Complexity (Fall 2020, Fall 2017)
•COMP 7712: Algorithms and Problem Solving (Fall 2024)
•COMP 7612: Foundations of Computing (Spring 2026, Spring 2023, Fall 2022, Spring 2017)
•COMP 4601: Models of Computation (Spring 2026, Fall 2024, Spring 2024, Spring 2023, Spring 2022, Fall 2021, Fall 2020, Spring 2020, Fall 2019, Spring 2019, Fall 2018, Spring 2018, Fall 2016)
•COMP 4030: Design and Analysis of Algorithms (Spring 2024, Spring 2019, Fall 2018)
•COMP 4019: Competitive Programming and Technical Interviews (Fall 2022, Fall 2021, Fall 2020, Fall 2019, Fall 2018, Fall 2017)
•COMP 3150: Programming in C/C++ (Fall 2021)