default search action
Thomas Watson 0001
Person information
- affiliation: University of Memphis, Department of Computer Science, TN, USA
- affiliation: University of Toronto, Department of Computer Science, ON, Canada
- affiliation (PhD 2013): University of California, Berkeley, USA
- not to be confused with: Thomas Watson 0004
Other persons with the same name
- Thomas Watson 0002 — ABB Flexible Autom., Auburn Hills, MI, USA
- Thomas Watson 0003 — IBM Software Group, Austin, TX, USA
- Thomas P. Watson (aka: Thomas Watson 0004) — University of Memphis, Department of Electrical and Computer Engineering, TN, USA
- Thomas Watson 0005 — New Mexico Institute of Mining and Technology, Socorro, NM, USA
- Thomas Watson 0006 — Intel, Hillsboro, OR, USA
- Thomas Watson 0007 — University of Memphis, Department of Electrical and Computer Engineering, TN, USA
- Thomas Watson 0008 — GlaxoSmithKline (GSK Plc), London, UK
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
- [j31]Md Lutfar Rahman, Thomas Watson:
6-Uniform Maker-Breaker Game is PSPACE-Complete. Comb. 43(3): 595-612 (2023) - 2022
- [j30]Thomas Watson:
Amplification with One NP Oracle Query. Comput. Complex. 31(1): 3 (2022) - [c29]Ramita Maharjan, Thomas Watson:
Complexity of Fault Tolerant Query Complexity. FSTTCS 2022: 26:1-26:11 - [c28]Md Lutfar Rahman, Thomas Watson:
Erdős-Selfridge Theorem for Nonmonotone CNFs. SWAT 2022: 31:1-31:11 - [i36]Md Lutfar Rahman, Thomas Watson:
Erdős-Selfridge Theorem for Nonmonotone CNFs. CoRR abs/2201.00968 (2022) - 2021
- [j29]Toniann Pitassi, Morgan Shirley
, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Comput. Complex. 30(2): 10 (2021) - [c27]Md Lutfar Rahman, Thomas Watson:
6-Uniform Maker-Breaker Game Is PSPACE-Complete. STACS 2021: 57:1-57:15 - 2020
- [j28]Thomas Watson:
Communication Complexity with Small Advantage. Comput. Complex. 29(1): 2 (2020) - [j27]Thomas Watson:
Correction to: Communication complexity with small advantage. Comput. Complex. 29(1): 3 (2020) - [j26]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. SIAM J. Comput. 49(4) (2020) - [j25]Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. ACM Trans. Comput. Theory 12(2): 14:1-14:11 (2020) - [j24]Md Lutfar Rahman, Thomas Watson:
Complexity of Unordered CNF Games. ACM Trans. Comput. Theory 12(3): 18:1-18:18 (2020) - [j23]Mika Göös, Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. ACM Trans. Comput. Theory 12(3): 20:1-20:13 (2020) - [j22]Thomas Watson:
A ZPPNP[1] Lifting Theorem. ACM Trans. Comput. Theory 12(4): 27:1-27:20 (2020) - [c26]Shalev Ben-David, Mika Göös, Robin Kothari
When Is Amplification Necessary for Composition in Randomized Query Complexity? APPROX-RANDOM 2020: 28:1-28:16 - [c25]Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. ICALP 2020: 92:1-92:19 - [c24]Md Lutfar Rahman, Thomas Watson:
Tractable Unordered 3-CNF Games. LATIN 2020: 360-372 - [i35]Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson:
When Is Amplification Necessary for Composition in Randomized Query Complexity? CoRR abs/2006.10957 (2020) - [i34]Md Lutfar Rahman, Thomas Watson:
6-Uniform Maker-Breaker Game Is PSPACE-Complete. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j21]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P NP. Comput. Complex. 28(1): 113-144 (2019) - [j20]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Correction to: Query-to-Communication Lifting for P NP. Comput. Complex. 28(3): 543-544 (2019) - [c23]Mika Göös, Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. APPROX-RANDOM 2019: 51:1-51:13 - [c22]Thomas Watson:
Amplification with One NP Oracle Query. ICALP 2019: 96:1-96:13 - [c21]Thomas Watson:
A ZPPNP[1] Lifting Theorem. STACS 2019: 59:1-59:16 - [i33]Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i32]Md Lutfar Rahman, Thomas Watson:
Tractable Unordered 3-CNF Games. Electron. Colloquium Comput. Complex. TR19 (2019) - [i31]Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j19]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. Comput. Complex. 27(2): 245-304 (2018) - [j18]Mika Göös, Rahul Jain
Extension Complexity of Independent Set Polytopes. SIAM J. Comput. 47(1): 241-269 (2018) - [j17]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. SIAM J. Comput. 47(6): 2435-2450 (2018) - [j16]Thomas Watson:
Communication Complexity of Statistical Distance. ACM Trans. Comput. Theory 10(1): 2:1-2:11 (2018) - [j15]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication versus Partition Number. ACM Trans. Comput. Theory 10(1): 4:1-4:20 (2018) - [c20]Thomas Watson:
Communication Complexity with Small Advantage. CCC 2018: 9:1-9:17 - [c19]Md Lutfar Rahman, Thomas Watson:
Complexity of Unordered CNF Games. ISAAC 2018: 9:1-9:12 - [c18]Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. LATIN 2018: 864-872 - [i30]Md Lutfar Rahman, Thomas Watson:
Complexity of Unordered CNF Games. Electron. Colloquium Comput. Complex. TR18 (2018) - [i29]Thomas Watson:
Amplification with One NP Oracle Query. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c17]Thomas Watson:
Communication Complexity of Statistical Distance. APPROX-RANDOM 2017: 49:1-49:10 - [c16]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. CCC 2017: 12:1-12:16 - [c15]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. FOCS 2017: 132-143 - [c14]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication vs. Partition Number. ICALP 2017: 52:1-52:15 - [i28]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. CoRR abs/1703.07666 (2017) - [i27]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. Electron. Colloquium Comput. Complex. TR17 (2017) - [i26]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. Electron. Colloquium Comput. Complex. TR17 (2017) - [i25]Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. Electron. Colloquium Comput. Complex. TR17 (2017) - [i24]Thomas Watson:
A ZPP^NP[1] Lifting Theorem. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j14]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Algorithmica 76(3): 684-719 (2016) - [j13]Thomas Watson:
The complexity of estimating min-entropy. Comput. Complex. 25(1): 153-175 (2016) - [j12]Thomas Watson:
Nonnegative Rank vs. Binary Rank. Chic. J. Theor. Comput. Sci. 2016 (2016) - [j11]Mika Göös, Shachar Lovett
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45(5): 1835-1869 (2016) - [j10]Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. Theory Comput. 12(1): 1-23 (2016) - [c13]Mika Göös, Rahul Jain
Extension Complexity of Independent Set Polytopes. FOCS 2016: 565-572 - [c12]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. ICALP 2016: 86:1-86:15 - [i23]Thomas Watson:
Nonnegative Rank vs. Binary Rank. CoRR abs/1603.07779 (2016) - [i22]Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. CoRR abs/1604.07062 (2016) - [i21]Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. Electron. Colloquium Comput. Complex. TR16 (2016) - [i20]Thomas Watson:
Communication Complexity with Small Advantage. Electron. Colloquium Comput. Complex. TR16 (2016) - [i19]Thomas Watson:
Communication Complexity of Statistical Distance. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j9]Thomas Watson:
Query Complexity in Errorless Hardness Amplification. Comput. Complex. 24(4): 823-850 (2015) - [j8]Thomas Watson:
The Complexity of Deciding Statistical Properties of Samplable Distributions. Theory Comput. 11: 1-34 (2015) - [c11]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. FOCS 2015: 1077-1088 - [c10]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. ITCS 2015: 113-122 - [c9]Mika Göös, Shachar Lovett
Rectangles Are Nonnegative Juntas. STOC 2015: 257-266 - [i18]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication vs. Partition Number. Electron. Colloquium Comput. Complex. TR15 (2015) - [i17]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. Electron. Colloquium Comput. Complex. TR15 (2015) - [i16]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j7]Thomas Watson:
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. Chic. J. Theor. Comput. Sci. 2014 (2014) - [j6]Thomas Watson:
Time Hierarchies for Sampling Distributions. SIAM J. Comput. 43(5): 1709-1727 (2014) - [j5]Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem. ACM Trans. Comput. Theory 7(1): 1:1-1:18 (2014) - [c8]Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. APPROX-RANDOM 2014: 721-736 - [c7]Thomas Watson:
The Complexity of Deciding Statistical Properties of Samplable Distributions. STACS 2014: 663-674 - [i15]Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. Electron. Colloquium Comput. Complex. TR14 (2014) - [i14]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - [i13]Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [b1]Thomas Weir Watson:
The Computational Complexity of Randomness. University of California, Berkeley, USA, 2013 - [j4]Thomas Watson:
Pseudorandom generators for combinatorial checkerboards. Comput. Complex. 22(4): 727-769 (2013) - [c6]Thomas Watson:
Time hierarchies for sampling distributions. ITCS 2013: 429-440 - [c5]Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem. STACS 2013: 634-645 - [i12]Thomas Watson:
The Complexity of Deciding Statistical Properties of Samplable Distributions. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j3]Dieter van Melkebeek, Thomas Watson:
Time-Space Efficient Simulations of Quantum Computations. Theory Comput. 8(1): 1-51 (2012) - [j2]Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources. ACM Trans. Comput. Theory 4(1): 3:1-3:21 (2012) - [j1]Thomas Watson:
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. ACM Trans. Comput. Theory 4(3): 8:1-8:30 (2012) - [i11]Thomas Watson:
Time Hierarchies for Sampling Distributions. Electron. Colloquium Comput. Complex. TR12 (2012) - [i10]Thomas Watson:
The Complexity of Estimating Min-Entropy. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c4]Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources. APPROX-RANDOM 2011: 483-494 - [c3]Thomas Watson:
Query Complexity in Errorless Hardness Amplification. APPROX-RANDOM 2011: 688-699 - [c2]Thomas Watson:
Pseudorandom Generators for Combinatorial Checkerboards. CCC 2011: 232-242 - [i9]Thomas Watson:
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. CoRR abs/1107.1265 (2011) - [i8]Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources. Electron. Colloquium Comput. Complex. TR11 (2011) - [i7]Thomas Watson:
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem. Electron. Colloquium Comput. Complex. TR11 (2011) - [i6]Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c1]Thomas Watson:
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. APPROX-RANDOM 2010: 752-765 - [i5]Dieter van Melkebeek, Thomas Watson:
Time-Space Efficient Simulations of Quantum Computations. Electron. Colloquium Comput. Complex. TR10 (2010) - [i4]Thomas Watson:
Relativized Worlds Without Worst-Case to Average-Case Reductions for NP. Electron. Colloquium Comput. Complex. TR10 (2010) - [i3]Thomas Watson:
Query Complexity in Errorless Hardness Amplification. Electron. Colloquium Comput. Complex. TR10 (2010) - [i2]Thomas Watson:
Pseudorandom Generators for Combinatorial Checkerboards. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2008
- [i1]Dieter van Melkebeek, Thomas Watson:
A Quantum Time-Space Lower Bound for the Counting Hierarchy. Electron. Colloquium Comput. Complex. TR08 (2008)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:20 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: