6 papers
Equality is Far Weaker than Constant-Cost Communication
Mika Göös, Nathaniel Harms, Artur Riazanov
We exhibit an -bit communication problem with a constant-cost randomized protocol but which requires deterministic (or even non-deterministic) queries to an Equality…
Monotone Circuit Complexity of Matching
Bruno Cavalar, Mika Göös, Artur Riazanov +2
We show that the perfect matching function on -vertex graphs requires monotone circuits of size . This improves on the lower bound of Razbo…
Sign-Rank of -Hamming Distance is Constant
Mika Göös, Nathaniel Harms, Valentin Imbach +1
We prove that the sign-rank of the -Hamming Distance matrix on bits is , independent of the number of bits . This strongly refutes the conjecture of Hatami, Hat…
Direct Sums for Parity Decision Trees
Tyler Besselman, Mika Göös, Siyao Guo +2
Direct sum theorems state that the cost of solving instances of a problem is at least times the cost of solving a single instance. We prove the first such results in the…
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…
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain +1
We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-w…