A. Sofronova

collaborators

3 papers

cs.CC2026

Pseudodeterministic Communication Complexity

Mika GÃ¶Ã¶s, Nathaniel Harms, Artur Riazanov +3

We exhibit an $n$ -bit partial function with randomized communication complexity $O (lo g n)$ but such that any completion of this function into a total one requires randomized commu…

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^{I^c ◯ (1)}}$ . This improves on the $n^{I^c ◯ (l o g n)}$ lower bound of Raz…

cs.CC2025

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 $O (lo g n)$ -CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable…