3 citations · 4 across the 4 of their papers we have counts for
6 papers · 1 filter
No Constant-Cost Protocol for Point--Line Incidence
Mika Göös, Nathaniel Harms, Florian K. Richter +1
Alice and Bob are given -bit integer pairs and , respectively, and they must decide if . We prove that the randomised communication complexity of this Poi…
Automating Cutting Planes is NP-Hard}
Mika Göös, Sajin Koroth, Ian Mertz +1
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula , 1) It is NP-hard to find a CP refutation of in time polynomial in the length of th…
The Power of Many Samples in Query Complexity
Andrew Bassilakis, Andrew Drucker, Mika Göös +3
The randomized query complexity of a boolean function is famously characterized (via Yao's minimax) by the least number of queries needed to dis…
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Mika Göös, Aviad Rubinstein
We prove an lower bound on the randomized communication complexity of finding an -approximate Nash equilibrium (for constant ) in a two-player game…
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…
Separating OR, SUM, and XOR Circuits
Magnus Find, Mika Göös, Matti Järvisalo +3
Given a boolean n by n matrix A we consider arithmetic circuits for computing the transformation x->Ax over different semirings. Namely, we study three circuit models: monotone OR-…