Thomas Watson

Dunn Hall 315
Department of Computer Science
University of Memphis
Memphis, TN 38152

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.

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

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

COMP 8613: Computational Complexity (Fall 2020, Fall 2017)
COMP 7612: Foundations of Computing (Fall 2022, Spring 2017)
COMP 4601: Models of Computation (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 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)