2 citations · 3 across the 2 of their papers we have counts for
6 papers
Proofs, Circuits, and Communication
Susanna F. de Rezende, Mika Göös, Robert Robere
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and que…
Further Collapses in TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
We show . Here the class consists of all total search problems that reduce to the End-of-Potential-Line problem, which…
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…
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…
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki +1
We study the search problem class defined as a modulo- analog of the well-known class introduced by Papadim…
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…