47 citations · 138 across the 17 of their papers we have counts for
5 papers · 1 filter
Randomised Composition and Small-Bias Minimax
Shalev Ben-David, Eric Blais, Mika Göös +1
We prove two results about randomised query complexity . First, we introduce a "linearised" complexity measure and show that it satisfies an inner-opti…
Communication Complexity of Collision
Mika Göös, Siddhartha Jain
The Collision problem is to decide whether a given list of numbers is -to- or -to- when promised one of them is the case. We show an $n^{Ω(1)…
Separations in Proof Complexity and TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Re…
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…