9 papers
Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov +3
We exhibit an -bit partial function with randomized communication complexity but such that any completion of this function into a total one requires randomized commu…
Sampling Permutations with Cell Probes is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov +2
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from . How hard is it to output a sequence in that is close to…
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 Raz…
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…
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…
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 th…