Anastasia Sofronova

According to our database, Anastasia Sofronova authored at least 10 papers between 2019 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

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

2023

Top-Down Lower Bounds for Depth-Four Circuits.

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

Electron. Colloquium Comput. Complex., 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

Electron. Colloquium Comput. Complex., 2021

2019

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

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2019