Thomas WatsonDunn Hall 315 Computer Science Department University of Memphis Memphis, TN 38152 Thomas.Watson@memphis.edu |  |
I am an Associate Professor of Computer Science at the University of Memphis. My research interests include computational complexity theory and theoretical computer science in general. Here is my curriculum vitae.
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.
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
| • | Pseudodeterminism and MA≠NPBPP in Communication Complexity |
| Thomas Watson | |
| Preprint 2026 | |
| • | 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, TOCS 2026 | |
| • | 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 |
| Fall 2026, Spring 2026, Spring 2023, Fall 2022, Spring 2017 | |
| • | COMP 4601: Models of Computation |
| Fall 2026, 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 |