7 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…
Spiky Rank and Its Applications to Rigidity and Circuits
Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov +2
We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix i…
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…
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…