Artur Riazanov

According to our database, Artur Riazanov authored at least 24 papers between 2018 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Lower Bounds Beyond DNF of Parities.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2025

Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Electron. Colloquium Comput. Complex., 2025

Equality is Far Weaker Than Constant-Cost Communication.

Mika Göös, Nathaniel Harms, Artur Riazanov

Electron. Colloquium Comput. Complex., 2025

Monotone Circuit Complexity of Matching.

Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2025

Generalised Linial-Nisan Conjecture is False for DNFs.

Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan

Electron. Colloquium Comput. Complex., 2025

2024

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space.

Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov

ACM Trans. Comput. Theory, September, 2024

Breaking Verifiable Delay Functions in the Random Oracle Model.

Ziyi Guan, Artur Riazanov, Weiqiang Yuan

IACR Cryptol. ePrint Arch., 2024

Partial Minimum Branching Program Size Problem is ETH-hard.

Ludmila Glinskih, Artur Riazanov

Electron. Colloquium Comput. Complex., 2024

Better Boosting of Communication Oracles, or Not.

Nathaniel Harms, Artur Riazanov

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

Top-Down Lower Bounds for Depth-Four Circuits.

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Hardness Condensation by Restriction.

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Sampling and Certifying Symmetric Functions.

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Proving Unsatisfiability with Hitting Formulas.

Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Electron. Colloquium Comput. Complex., 2023

2022

Automating OBDD proofs is NP-hard.

Dmitry Itsykson, Artur Riazanov

Electron. Colloquium Comput. Complex., 2022

Irreducible subcube partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals

CoRR, 2022

Tight Bounds for Tseitin Formulas.

Dmitry Itsykson, Artur Riazanov, Petr Smirnov

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

MCSP is Hard for Read-Once Nondeterministic Branching Programs.

Ludmila Glinskih, Artur Riazanov

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

2021

Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Comput. Complex., 2021

Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Comput. Complex., 2021

2020

Proof complexity of natural formulas via communication arguments.

Dmitry Itsykson, Artur Riazanov

Electron. Colloquium Comput. Complex., 2020

Lower Bounds on OBDD Proofs with Several Orders.

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2020

2019

Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Electron. Colloquium Comput. Complex., 2019

Bounded-depth Frege complexity of Tseitin formulas for all graphs.

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2019

2018

On the Decision Trees with Symmetries.

Artur Riazanov

Proceedings of the Computer Science - Theory and Applications, 2018