4 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…
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov +1
We show that for a randomly sampled unsatisfiable -CNF over variables the randomized two-party communication cost of finding a clause falsified by the given variable…