Yaroslav Alekseev

According to our database, Yaroslav Alekseev authored at least 18 papers between 2019 and 2026.

Collaborative distances:

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

2026

New Polynomial-Depth Res(+) Lower Bounds.

Yaroslav Alekseev, Nikita Gaevoy

Electron. Colloquium Comput. Complex., 2026

Sampling Permutations with Cell Probes Is Hard.

Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds.

Yaroslav Alekseev, Nikita Gaevoy

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

Linear Matroid Intersection Is in Catalytic Logspace.

Aryan Agarwala, Yaroslav Alekseev, Antoine Vinciguerra

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

2025

Approximate polymorphisms of predicates.

Yaroslav Alekseev, Yuval Filmus

Electron. Colloquium Comput. Complex., 2025

Lifting to Bounded-Depth and Regular Resolutions over Parities via Games.

Yaroslav Alekseev, Dmitry Itsykson

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Tropical Proof Systems: Between R(CP) and Resolution.

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Catalytic Computing and Register Programs Beyond Log-Depth.

Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Generalised Linial-Nisan Conjecture Is False for DNFs.

Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the 40th Computational Complexity Conference, 2025

2024

ATSM: A coverage-based framework and a tool for test suite minimization.

Yaroslav Alekseev, Mikhail Onischuck, Arseniy Zorin, Vitaliy Chernyi, Evgeniy Iliyn, Vladimir M. Itsykson

J. Softw. Evol. Process., June, 2024

Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

SIAM J. Comput., 2024

Lifting to regular resolution over parities via games.

Yaroslav Alekseev, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2024

Tropical proof systems.

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch

Electron. Colloquium Comput. Complex., 2024

Lifting Dichotomies.

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Proceedings of the 39th Computational Complexity Conference, 2024

2023

The Power of the Binary Value Principle.

Yaroslav Alekseev, Edward A. Hirsch

Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

2021

A Lower Bound for Polynomial Calculus with Extension Rule.

Yaroslav Alekseev

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2019