Mika Göös

collaborators

Showing cs.CCShow all

5 papers · 1 filter

cs.CC2025

Equality is Far Weaker than Constant-Cost Communication

Mika Göös, Nathaniel Harms, Artur Riazanov

We exhibit an $n$ -bit communication problem with a constant-cost randomized protocol but which requires $n^{Ω (1)}$ deterministic (or even non-deterministic) queries to an Equality…

cs.CC2025

Monotone Circuit Complexity of Matching

Bruno Cavalar, Mika Göös, Artur Riazanov +2

We show that the perfect matching function on $n$ -vertex graphs requires monotone circuits of size $2^{n^{Ω (1)}}$ . This improves on the $n^{Ω (l o g n)}$ lower bound of Razbo…

cs.CC2025

Sign-Rank of $k$ -Hamming Distance is Constant

Mika Göös, Nathaniel Harms, Valentin Imbach +1

We prove that the sign-rank of the $k$ -Hamming Distance matrix on $n$ bits is $2^{O (k)}$ , independent of the number of bits $n$ . This strongly refutes the conjecture of Hatami, Hat…

cs.CC2024

Direct Sums for Parity Decision Trees

Tyler Besselman, Mika Göös, Siyao Guo +2

Direct sum theorems state that the cost of solving $k$ instances of a problem is at least $Ω (k)$ times the cost of solving a single instance. We prove the first such results in the…

cs.CC2024

Supercritical Tradeoffs for Monotone Circuits

Mika Göös, Gilbert Maystre, Kilian Risse +1

We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…

Equality is Far Weaker than Constant-Cost Communication

Monotone Circuit Complexity of Matching

Sign-Rank of k-Hamming Distance is Constant

Direct Sums for Parity Decision Trees

Supercritical Tradeoffs for Monotone Circuits

Sign-Rank of $k$ -Hamming Distance is Constant