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…
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…
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…
Top-Down Lower Bounds for Depth-Four Circuits
Mika Göös, Artur Riazanov, Anastasia Sofronova +1
We present a top-down lower-bound method for depth- boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth- cir…