Anastasia Sofronova

According to our database, Anastasia Sofronova authored at least 13 papers between 2019 and 2026.

Collaborative distances:

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

2026

No Constant-Cost Protocol for Point-Line Incidence.

Mika Göös, Nathaniel Harms, Florian K. Richter, Anastasia Sofronova

CoRR, April, 2026

No Constant-Cost Protocol for Point-Line Incidence.

Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova

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

Lower Bounds Beyond DNF of Parities.

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

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

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