2 citations · 3 across the 6 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.CC2022
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)…
cs.CC2022★ 2 cited
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…