Anastasia Sofronova

21 papers A* 1A 5B 1Journal 14
YearRankTypeTitle / Venue / Authors
2026 A conf
Lower Bounds Beyond DNF of Parities.
ITCS
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2025 A conf
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion.
CCC
Anastasia Sofronova, Dmitry Sokolov
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 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
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
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 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 A conf
A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates.
CCC
Ivan Mihajlin, Anastasia Sofronova
2022 J jnl
A Lower Bound for
Electron. Colloquium Comput. Complex.
Anastasia Sofronova, Dmitry Sokolov
2022 J jnl
A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates.
Electron. Colloquium Comput. Complex.
Ivan Mihajlin, Anastasia Sofronova
2021 A conf
Branching Programs with Bounded Repetitions and Flow Formulas.
CCC
Anastasia Sofronova, Dmitry Sokolov
2021 J jnl
Branching Programs with Bounded Repetitions and Flow Formulas.
Electron. Colloquium Comput. Complex.
Anastasia Sofronova, Dmitry Sokolov
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