Thomas Watson

Publication Activity (10 Years)

Years Active: 2008-2023
Publications (10 Years): 66

Top Topics

Statistical Distributions

Query Complexity

Independent Set

Top Venues

Electron. Colloquium Comput. Complex.

Comput. Complex.

ACM Trans. Comput. Theory

Publications

Md Lutfar Rahman, Thomas Watson
6-Uniform Maker-Breaker Game is PSPACE-Complete. Comb. 43 (3) (2023)
Md Lutfar Rahman, Thomas Watson
Erdős-Selfridge Theorem for Nonmonotone CNFs. CoRR (2022)
Thomas Watson
Amplification with One NP Oracle Query. Comput. Complex. 31 (1) (2022)
Ramita Maharjan, Thomas Watson
Complexity of Fault Tolerant Query Complexity. FSTTCS (2022)
Md Lutfar Rahman, Thomas Watson
Erdős-Selfridge Theorem for Nonmonotone CNFs. SWAT (2022)
Md Lutfar Rahman, Thomas Watson
6-Uniform Maker-Breaker Game Is PSPACE-Complete. STACS (2021)
Toniann Pitassi, Morgan Shirley, Thomas Watson
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Comput. Complex. 30 (2) (2021)
Thomas Watson
Lifting Theorem. ACM Trans. Comput. Theory 12 (4) (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? APPROX-RANDOM (2020)
Md Lutfar Rahman, Thomas Watson
Tractable Unordered 3-CNF Games. LATIN (2020)
Thomas Watson
Quadratic Simulations of Merlin-Arthur Games. ACM Trans. Comput. Theory 12 (2) (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? CoRR (2020)
Toniann Pitassi, Morgan Shirley, Thomas Watson
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. ICALP (2020)
Md Lutfar Rahman, Thomas Watson
Complexity of Unordered CNF Games. ACM Trans. Comput. Theory 12 (3) (2020)
Thomas Watson
Correction to: Communication complexity with small advantage. Comput. Complex. 29 (1) (2020)
Mika Göös, Thomas Watson
A Lower Bound for Sampling Disjoint Sets. ACM Trans. Comput. Theory 12 (3) (2020)
Thomas Watson
Communication Complexity with Small Advantage. Comput. Complex. 29 (1) (2020)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. SIAM J. Comput. 49 (4) (2020)
Md Lutfar Rahman, Thomas Watson
6-Uniform Maker-Breaker Game Is PSPACE-Complete. Electron. Colloquium Comput. Complex. 27 (2020)
Thomas Watson
A Lower Bound for Sampling Disjoint Sets. Electron. Colloquium Comput. Complex. 26 (2019)
Thomas Watson
Amplification with One NP Oracle Query. ICALP (2019)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Correction to: Query-to-Communication Lifting for P NP. Comput. Complex. 28 (3) (2019)
Mika Göös, Thomas Watson
A Lower Bound for Sampling Disjoint Sets. APPROX-RANDOM (2019)
Md Lutfar Rahman, Thomas Watson
Tractable Unordered 3-CNF Games. Electron. Colloquium Comput. Complex. 26 (2019)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P NP. Comput. Complex. 28 (1) (2019)
Toniann Pitassi, Morgan Shirley, Thomas Watson
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Electron. Colloquium Comput. Complex. 26 (2019)
Thomas Watson
Lifting Theorem. STACS (2019)
Thomas Watson
Quadratic Simulations of Merlin-Arthur Games. LATIN (2018)
Thomas Watson
Communication Complexity of Statistical Distance. ACM Trans. Comput. Theory 10 (1) (2018)
Md Lutfar Rahman, Thomas Watson
Complexity of Unordered CNF Games. ISAAC (2018)
Md Lutfar Rahman, Thomas Watson
Complexity of Unordered CNF Games. Electron. Colloquium Comput. Complex. 25 (2018)
Mika Göös, Toniann Pitassi, Thomas Watson
Deterministic Communication vs. Partition Number. SIAM J. Comput. 47 (6) (2018)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. SIAM J. Comput. 47 (1) (2018)
Mika Göös, Toniann Pitassi, Thomas Watson
The Landscape of Communication Complexity Classes. Comput. Complex. 27 (2) (2018)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication versus Partition Number. ACM Trans. Comput. Theory 10 (1) (2018)
Thomas Watson
Amplification with One NP Oracle Query. Electron. Colloquium Comput. Complex. 25 (2018)
Thomas Watson
Communication Complexity with Small Advantage. Computational Complexity Conference (2018)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P^NP. Electron. Colloquium Comput. Complex. 24 (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. Electron. Colloquium Comput. Complex. 24 (2017)
Thomas Watson
A ZPP^NP[1] Lifting Theorem. Electron. Colloquium Comput. Complex. 24 (2017)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P^NP. Computational Complexity Conference (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. FOCS (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. CoRR (2017)
Thomas Watson
Quadratic Simulations of Merlin-Arthur Games. Electron. Colloquium Comput. Complex. 24 (2017)
Thomas Watson
Communication Complexity of Statistical Distance. APPROX-RANDOM (2017)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication vs. Partition Number. ICALP (2017)
Thomas Watson
Nonnegative Rank vs. Binary Rank. Chic. J. Theor. Comput. Sci. 2016 (2016)
Mika Göös, Thomas Watson
Communication Complexity of Set-Disjointness for All Probabilities. Theory Comput. 12 (1) (2016)
Thomas Watson
Communication Complexity of Statistical Distance. Electron. Colloquium Comput. Complex. 23 (2016)
Thomas Watson
The complexity of estimating min-entropy. Comput. Complex. 25 (1) (2016)
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45 (5) (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. FOCS (2016)
Thomas Watson
Nonnegative Rank vs. Binary Rank. CoRR (2016)
Mika Göös, Toniann Pitassi, Thomas Watson
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Algorithmica 76 (3) (2016)
Mika Göös, Toniann Pitassi, Thomas Watson
The Landscape of Communication Complexity Classes. ICALP (2016)
Thomas Watson
Communication Complexity with Small Advantage. Electron. Colloquium Comput. Complex. 23 (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. Electron. Colloquium Comput. Complex. 23 (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. CoRR (2016)
Mika Göös, Toniann Pitassi, Thomas Watson
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. ITCS (2015)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication vs. Partition Number. Electron. Colloquium Comput. Complex. 22 (2015)
Thomas Watson
The Complexity of Deciding Statistical Properties of Samplable Distributions. Theory Comput. 11 (2015)
Mika Göös, Toniann Pitassi, Thomas Watson
Deterministic Communication vs. Partition Number. Electron. Colloquium Comput. Complex. 22 (2015)
Mika Göös, Toniann Pitassi, Thomas Watson
Deterministic Communication vs. Partition Number. FOCS (2015)
Thomas Watson
Query Complexity in Errorless Hardness Amplification. Comput. Complex. 24 (4) (2015)
Mika Göös, Toniann Pitassi, Thomas Watson
The Landscape of Communication Complexity Classes. Electron. Colloquium Comput. Complex. 22 (2015)
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Rectangles Are Nonnegative Juntas. STOC (2015)
Thomas Watson
Advice Lower Bounds for the Dense Model Theorem. ACM Trans. Comput. Theory 7 (1) (2014)
Mika Göös, Thomas Watson
Communication Complexity of Set-Disjointness for All Probabilities. Electron. Colloquium Comput. Complex. 21 (2014)
Thomas Watson
Time Hierarchies for Sampling Distributions. SIAM J. Comput. 43 (5) (2014)
Thomas Watson
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. Chic. J. Theor. Comput. Sci. 2014 (2014)
Mika Göös, Toniann Pitassi, Thomas Watson
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Rectangles Are Nonnegative Juntas. Electron. Colloquium Comput. Complex. 21 (2014)
Thomas Watson
The Complexity of Deciding Statistical Properties of Samplable Distributions. STACS (2014)
Mika Göös, Thomas Watson
Communication Complexity of Set-Disjointness for All Probabilities. APPROX-RANDOM (2014)
Thomas Watson
Advice Lower Bounds for the Dense Model Theorem. STACS (2013)
Thomas Watson
Time hierarchies for sampling distributions. ITCS (2013)
Thomas Watson
Pseudorandom generators for combinatorial checkerboards. Comput. Complex. 22 (4) (2013)
Thomas Watson
The Complexity of Deciding Statistical Properties of Samplable Distributions. Electron. Colloquium Comput. Complex. 20 (2013)
Anindya De, Thomas Watson
Extractors and Lower Bounds for Locally Samplable Sources. ACM Trans. Comput. Theory 4 (1) (2012)
Thomas Watson
Time Hierarchies for Sampling Distributions. Electron. Colloquium Comput. Complex. 19 (2012)
Thomas Watson
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. ACM Trans. Comput. Theory 4 (3) (2012)
Thomas Watson
The Complexity of Estimating Min-Entropy. Electron. Colloquium Comput. Complex. 19 (2012)
Dieter van Melkebeek, Thomas Watson
Time-Space Efficient Simulations of Quantum Computations. Theory Comput. 8 (1) (2012)
Thomas Watson
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. Electron. Colloquium Comput. Complex. 18 (2011)
Thomas Watson
Query Complexity in Errorless Hardness Amplification. APPROX-RANDOM (2011)
Thomas Watson
Advice Lower Bounds for the Dense Model Theorem. Electron. Colloquium Comput. Complex. 18 (2011)
Anindya De, Thomas Watson
Extractors and Lower Bounds for Locally Samplable Sources. Electron. Colloquium Comput. Complex. 18 (2011)
Thomas Watson
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem CoRR (2011)
Thomas Watson
Pseudorandom Generators for Combinatorial Checkerboards. Computational Complexity Conference (2011)
Anindya De, Thomas Watson
Extractors and Lower Bounds for Locally Samplable Sources. APPROX-RANDOM (2011)
Dieter van Melkebeek, Thomas Watson
Time-Space Efficient Simulations of Quantum Computations. Electron. Colloquium Comput. Complex. 17 (2010)
Thomas Watson
Query Complexity in Errorless Hardness Amplification. Electron. Colloquium Comput. Complex. 17 (2010)
Thomas Watson
Pseudorandom Generators for Combinatorial Checkerboards. Electron. Colloquium Comput. Complex. 17 (2010)
Thomas Watson
Relativized Worlds Without Worst-Case to Average-Case Reductions for NP. Electron. Colloquium Comput. Complex. 17 (2010)
Thomas Watson
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. APPROX-RANDOM (2010)
Dieter van Melkebeek, Thomas Watson
A Quantum Time-Space Lower Bound for the Counting Hierarchy. Electron. Colloquium Comput. Complex. 15 (017) (2008)