2 citations · 2 across the 6 of their papers we have counts for
9 papers
TFNP in the Random Oracle Model
Noah Fleming, Mika Göös, Ziyi Guan +7
We determine which major $\TFNP$ classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of $\TFNP$ from str…
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…
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…
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…
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…
Better Boosting of Communication Oracles, or Not
Nathaniel Harms, Artur Riazanov
Suppose we have a two-party communication protocol for which allows the parties to make queries to an oracle computing ; for example, they may query an Equality oracle. To t…
Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov
We consider the proof system Res() introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.'20), which is an extension of the resolution proof system and operates with disj…