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. Deterministic Communication vs. Partition Number. FOCS 2015. | ||||

• | Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. Preprint. | ||||

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