Artur Riazanov

According to our database, Artur Riazanov authored at least 28 papers between 2018 and 2026.

Collaborative distances:

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

2026

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity.

Susanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov

CoRR, May, 2026

Spiky Rank and Its Applications to Rigidity and Circuits.

Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman

Electron. Colloquium Comput. Complex., 2026

Pseudodeterministic Communication Complexity.

Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Monotone Circuit Complexity of Matching.

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

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Sampling Permutations with Cell Probes Is Hard.

Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Lower Bounds Beyond DNF of Parities.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

Partial Minimum Branching Program Size Problem Is ETH-Hard.

Ludmila Glinskih, Artur Riazanov

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Breaking Verifiable Delay Functions in the Random Oracle Model.

Ziyi Guan, Artur Riazanov, Weiqiang Yuan

Proceedings of the Advances in Cryptology - CRYPTO 2025, 2025

Generalised Linial-Nisan Conjecture Is False for DNFs.

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

Proceedings of the 40th Computational Complexity Conference, 2025

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

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the Approximation, 2025

Equality Is Far Weaker Than Constant-Cost Communication.

Mika Göös, Nathaniel Harms, Artur Riazanov

Proceedings of the Approximation, 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

Hardness Condensation by Restriction.

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

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Proving Unsatisfiability with Hitting Formulas.

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

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 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

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sampling and Certifying Symmetric Functions.

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Proceedings of the Approximation, 2023

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

Automating OBDD proofs is NP-hard.

Dmitry Itsykson, Artur Riazanov

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 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

Proof Complexity of Natural Formulas via Communication Arguments.

Dmitry Itsykson, Artur Riazanov

Proceedings of the 36th Computational Complexity Conference, 2021

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

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

On the Decision Trees with Symmetries.

Artur Riazanov

Proceedings of the Computer Science - Theory and Applications, 2018