Artur Riazanov

54 papers A* 2A 9B 3Misc 1Journal 37Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A conf
Lower Bounds Beyond DNF of Parities.
ITCS
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2026 J jnl
Spiky Rank and Its Applications to Rigidity and Circuits.
CoRR
Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman
2026 J jnl
Spiky Rank and Its Applications to Rigidity and Circuits.
Electron. Colloquium Comput. Complex.
Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman
2025 — conf
Breaking Verifiable Delay Functions in the Random Oracle Model.
CRYPTO (7)
Ziyi Guan, Artur Riazanov, Weiqiang Yuan
2025 A conf
Equality Is Far Weaker Than Constant-Cost Communication.
APPROX/RANDOM
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 J jnl
Equality is Far Weaker Than Constant-Cost Communication.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 J jnl
Equality is Far Weaker than Constant-Cost Communication.
CoRR
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 A conf
Generalised Linial-Nisan Conjecture Is False for DNFs.
CCC
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Generalised Linial-Nisan Conjecture is False for DNFs.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Lower Bounds Beyond DNF of Parities.
Electron. Colloquium Comput. Complex.
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Monotone Circuit Complexity of Matching.
CoRR
Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 J jnl
Monotone Circuit Complexity of Matching.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 A conf
Partial Minimum Branching Program Size Problem Is ETH-Hard.
ITCS
Ludmila Glinskih, Artur Riazanov
2025 J jnl
Pseudodeterministic Communication Complexity.
CoRR
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Pseudodeterministic Communication Complexity.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Sampling Permutations with Cell Probes is Hard.
CoRR
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
2025 J jnl
Sampling Permutations with Cell Probes is Hard.
Electron. Colloquium Comput. Complex.
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
2025 J jnl
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication.
CoRR
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 A conf
Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication.
APPROX/RANDOM
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication.
Electron. Colloquium Comput. Complex.
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2024 — conf
Better Boosting of Communication Oracles, or Not.
FSTTCS
Nathaniel Harms, Artur Riazanov
2024 J jnl
Better Boosting of Communication Oracles, or Not.
CoRR
Nathaniel Harms, Artur Riazanov
2024 J jnl
Breaking Verifiable Delay Functions in the Random Oracle Model.
IACR Cryptol. ePrint Arch.
Ziyi Guan, Artur Riazanov, Weiqiang Yuan
2024 A* conf
Hardness Condensation by Restriction.
STOC
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2024 J jnl
Partial Minimum Branching Program Size Problem is ETH-hard.
CoRR
Ludmila Glinskih, Artur Riazanov
2024 J jnl
Partial Minimum Branching Program Size Problem is ETH-hard.
Electron. Colloquium Comput. Complex.
Ludmila Glinskih, Artur Riazanov
2024 A conf
Proving Unsatisfiability with Hitting Formulas.
ITCS
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2024 J jnl
Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space.
CoRR
Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov
2024 J jnl
Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space.
ACM Trans. Comput. Theory
Svyatoslav Gryaznov, Sergei Ovcharov, Artur Riazanov
2023 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Ann. Pure Appl. Log.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2023 J jnl
Hardness Condensation by Restriction.
Electron. Colloquium Comput. Complex.
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Proving Unsatisfiability with Hitting Formulas.
CoRR
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2023 J jnl
Proving Unsatisfiability with Hitting Formulas.
Electron. Colloquium Comput. Complex.
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
2023 A conf
Sampling and Certifying Symmetric Functions.
APPROX/RANDOM
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Sampling and Certifying Symmetric Functions.
CoRR
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 J jnl
Sampling and Certifying Symmetric Functions.
Electron. Colloquium Comput. Complex.
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
2023 A* conf
Top-Down Lower Bounds for Depth-Four Circuits.
FOCS
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2023 J jnl
Top-Down Lower Bounds for Depth-Four Circuits.
CoRR
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2023 J jnl
Top-Down Lower Bounds for Depth-Four Circuits.
Electron. Colloquium Comput. Complex.
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2022 B conf
Automating OBDD proofs is NP-hard.
MFCS
Dmitry Itsykson, Artur Riazanov
2022 J jnl
Automating OBDD proofs is NP-hard.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov
2022 J jnl
Irreducible subcube partitions.
CoRR
Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals
2022 B conf
MCSP is Hard for Read-Once Nondeterministic Branching Programs.
LATIN
Ludmila Glinskih, Artur Riazanov
2022 A conf
Tight Bounds for Tseitin Formulas.
SAT
Dmitry Itsykson, Artur Riazanov, Petr Smirnov
2021 J jnl
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2021 J jnl
Lower Bounds on OBDD Proofs with Several Orders.
ACM Trans. Comput. Log.
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
2021 J jnl
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2021 A conf
Proof Complexity of Natural Formulas via Communication Arguments.
CCC
Dmitry Itsykson, Artur Riazanov
2020 J jnl
Lower Bounds on OBDD Proofs with Several Orders.
Electron. Colloquium Comput. Complex.
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
2020 J jnl
Proof complexity of natural formulas via communication arguments.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov
2019 J jnl
Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Electron. Colloquium Comput. Complex.
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov
2019 B conf
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs.
MFCS
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2019 J jnl
Bounded-depth Frege complexity of Tseitin formulas for all graphs.
Electron. Colloquium Comput. Complex.
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova
2018 Misc conf
On the Decision Trees with Symmetries.
CSR
Artur Riazanov