| Interests | |||||
| Computational complexity theory, and theoretical computer science in general. | |||||
| Biography | |||||
| I am a fifth year graduate student in computer science at the University of California, Berkeley. My advisor is Luca Trevisan. I obtained my undergraduate degree in May 2008 from the University of Wisconsin - Madison with majors in computer science, mathematics, and computer engineering. In 2009 I was awarded an NSF Graduate Research Fellowship. Here are my curriculum vitae and my dissertation. | |||||
| Research | |||||
| • | Thomas Watson. The Complexity of Estimating Min-Entropy. Manuscript. | ||||
| • | 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. Manuscript. | ||||
| • | 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, Spring 2012 | |||||
| CS 170: Efficient Algorithms and Intractable Problems, Fall 2011 | |||||
| Courses | |||||
| Courses taken at Berkeley and at Madison | |||||