2 citations · 2 across the 1 of their papers we have counts for
3 papers
cs.CC2020★ 2 cited
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…
cs.CC2017
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…
cs.CC2016
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…