3 citations · 4 across the 3 of their papers we have counts for
6 papers
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-…
Randomized Distributed Decision
Pierre Fraigniaud, Amos Korman, Merav Parter +1
The paper tackles the power of randomization in the context of locality by analyzing the ability to`boost' the success probability of deciding a distributed language. The main outc…