2 citations · 2 across the 2 of their papers we have counts for
5 papers
Pseudodeterminism and MA != NP^BPP in Communication Complexity
Thomas Watson
We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualita…
Erdős-Selfridge Theorem for Nonmonotone CNFs
Md Lutfar Rahman, Thomas Watson
In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values t…
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari +1
Suppose we have randomized decision trees for an outer function and an inner function . The natural approach for obtaining a randomized decision tree for the composed functi…
Query-to-Communication Lifting for BPP
Mika Göös, Toniann Pitassi, Thomas Watson
For any -bit boolean function , we show that the randomized communication complexity of the composed function , where is an index gadget, is characterized by…
Extension Complexity of Independent Set Polytopes
Mika Göös, Rahul Jain, Thomas Watson
We exhibit an -node graph whose independent set polytope requires extended formulations of size exponential in . Previously, no explicit examples of -dimensional…