We stand with Ukraine  

Thomas Watson

Affiliations:
  • University of Memphis, Department of Computer Science, TN, USA
  • University of Toronto, Department of Computer Science, ON, Canada
  • University of California, Berkeley, USA (PhD 2013)


According to our database1, Thomas Watson authored at least 40 papers between 2008 and 2022.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Amplification with One NP Oracle Query.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2022

Erdős-Selfridge Theorem for Nonmonotone CNFs.
[BibTeX]
[DOI]
Md Lutfar Rahman
,
Thomas Watson
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Complexity of Fault Tolerant Query Complexity.
[BibTeX]
[DOI]
Ramita Maharjan
,
Thomas Watson
Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.
[BibTeX]
[DOI]
Toniann Pitassi
,
Morgan Shirley
,
Thomas Watson
Comput. Complex., 2021

2020
A ZPP<sup>NP[1]</sup> Lifting Theorem.
[BibTeX]
[DOI]
Thomas Watson
ACM Trans. Comput. Theory, 2020

A Lower Bound for Sampling Disjoint Sets.
[BibTeX]
[DOI]
Mika Göös
,
Thomas Watson
ACM Trans. Comput. Theory, 2020

Query-to-Communication Lifting for BPP.
[BibTeX]
[DOI]
Mika Göös
,
Toniann Pitassi
,
Thomas Watson
SIAM J. Comput., 2020

6-Uniform Maker-Breaker Game Is PSPACE-Complete.
[BibTeX]
[DOI]
Md Lutfar Rahman
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2020

Correction to: Communication complexity with small advantage.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2020

Communication Complexity with Small Advantage.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2020

When Is Amplification Necessary for Composition in Randomized Query Complexity?
[BibTeX]
[DOI]
Shalev Ben-David
,
Mika Göös
,
Robin Kothari
,
Thomas Watson
Proceedings of the Approximation, 2020

2019
A Lower Bound for Sampling Disjoint Sets.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2019

Tractable Unordered 3-CNF Games.
[BibTeX]
[DOI]
Md Lutfar Rahman
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2019

Correction to: Query-to-Communication Lifting for P NP.
[BibTeX]
[DOI]
Mika Göös
,
Pritish Kamath
,
Toniann Pitassi
,
Thomas Watson
Comput. Complex., 2019

Query-to-Communication Lifting for P NP.
[BibTeX]
[DOI]
Mika Göös
,
Pritish Kamath
,
Toniann Pitassi
,
Thomas Watson
Comput. Complex., 2019

2018
Randomized Communication versus Partition Number.
[BibTeX]
[DOI]
Mika Göös
,
T. S. Jayram
,
Toniann Pitassi
,
Thomas Watson
ACM Trans. Comput. Theory, 2018

Deterministic Communication vs. Partition Number.
[BibTeX]
[DOI]
Mika Göös
,
Toniann Pitassi
,
Thomas Watson
SIAM J. Comput., 2018

Extension Complexity of Independent Set Polytopes.
[BibTeX]
[DOI]
Mika Göös
,
Rahul Jain
,
Thomas Watson
SIAM J. Comput., 2018

Complexity of Unordered CNF Games.
[BibTeX]
[DOI]
Md Lutfar Rahman
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2018

The Landscape of Communication Complexity Classes.
[BibTeX]
[DOI]
Mika Göös
,
Toniann Pitassi
,
Thomas Watson
Comput. Complex., 2018

2017
A ZPP^NP[1] Lifting Theorem.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2017

Quadratic Simulations of Merlin-Arthur Games.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2017

2016
Rectangles Are Nonnegative Juntas.
[BibTeX]
[DOI]
Mika Göös
,
Shachar Lovett
,
Raghu Meka
,
Thomas Watson
,
David Zuckerman
SIAM J. Comput., 2016

Communication Complexity of Statistical Distance.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2016

Nonnegative Rank vs. Binary Rank.
[BibTeX]
[DOI]
Thomas Watson
Chic. J. Theor. Comput. Sci., 2016

The complexity of estimating min-entropy.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2016

2015
Randomized Communication vs. Partition Number.
[BibTeX]
[DOI]
Mika Göös
,
T. S. Jayram
,
Toniann Pitassi
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2015

Query Complexity in Errorless Hardness Amplification.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2015

2014
Time Hierarchies for Sampling Distributions.
[BibTeX]
[DOI]
Thomas Watson
SIAM J. Comput., 2014

Communication Complexity of Set-Disjointness for All Probabilities.
[BibTeX]
[DOI]
Mika Göös
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2014

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.
[BibTeX]
[DOI]
Mika Göös
,
Toniann Pitassi
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2014

Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem.
[BibTeX]
[DOI]
Thomas Watson
Chic. J. Theor. Comput. Sci., 2014

2013
The Computational Complexity of Randomness.
[BibTeX]
[DOI]
Thomas Weir Watson
PhD thesis, 2013

The Complexity of Deciding Statistical Properties of Samplable Distributions.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2013

Pseudorandom generators for combinatorial checkerboards.
[BibTeX]
[DOI]
Thomas Watson
Comput. Complex., 2013

2011
Advice Lower Bounds for the Dense Model Theorem.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2011

Extractors and Lower Bounds for Locally Samplable Sources.
[BibTeX]
[DOI]
Anindya De
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2011

2010
Relativized Worlds Without Worst-Case to Average-Case Reductions for NP.
[BibTeX]
[DOI]
Thomas Watson
Electron. Colloquium Comput. Complex., 2010

Time-Space Efficient Simulations of Quantum Computations.
[BibTeX]
[DOI]
Dieter van Melkebeek
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2010

2008
A Quantum Time-Space Lower Bound for the Counting Hierarchy.
[BibTeX]
[DOI]
Dieter van Melkebeek
,
Thomas Watson
Electron. Colloquium Comput. Complex., 2008


  Loading...