Anastasia Sofronova

According to our database, Anastasia Sofronova authored at least 11 papers between 2019 and 2025.

Collaborative distances:

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

2025

Pseudodeterministic Communication Complexity.

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

CoRR, November, 2025

Lower Bounds Beyond DNF of Parities.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

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

A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion.

Anastasia Sofronova, Dmitry Sokolov

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

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

2022

A Lower Bound for <i>k</i>-DNF Resolution on Random CNF Formulas via Expansion.

Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2022

A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates.

Ivan Mihajlin, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2022

A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates.

Ivan Mihajlin, Anastasia Sofronova

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Branching Programs with Bounded Repetitions and Flow Formulas.

Anastasia Sofronova, Dmitry Sokolov

Proceedings of the 36th Computational Complexity Conference, 2021

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