Alexander V. Smal

Alexander V. Smal

Researcher at JetBrains

Research Interests

Complexity Theory Algorithms Information Theory

Research Experience

Researcher
2024 – Present
JetBrains, Limassol, Cyprus
Member of Algorithms and Complexity Theory Lab
Postdoctoral Fellow
2022 – 2024
Technion – Israel Institute of Technology, Haifa, Israel
Postdoctoral research under the mentorship of Yuval Filmus and Roy Schwartz
PhD Student, Researcher
2008 – Present (on leave)
Steklov Institute of Mathematics at St.Petersburg, St. Petersburg, Russia
Member of Laboratory of Mathemtical Logic.
Early Stage Researcher
2011
Charles University, Prague, Czech Republic
Special Semester in Logic and Complexity
Research Intern
2011
Microsoft Research Silicon Valley, Mountain View, CA, USA
Research intern under the mentorship of Ilya Mironov.

Teaching Experience

Neapolis University Pafos, Cyprus
2024 – Present
BSc program Computer Science and Artificial Intelligence
Courses: Information Theory, Mathematical Logic, Mathematical Analysis
ITMO University, St. Petersburg, Russia
2018 – 2022
Courses: Algorithms, Information Theory
St. Petersburg University, Russia
2020
Courses: Advanced Algorithms
Higher School of Economics, St. Petersburg, Russia
2020
Courses: Information Theory
Computer Science Center, St. Petersburg, Russia
2011 – 2019
Courses: Algorithms, C++
St. Petersburg Academic University, Russia
2008 – 2018
Courses: Algorithms, C++, Information Theory, Foundations of Cryptography

Publications

Conference Papers

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
Yuval Filmus, Roy Schwartz, Alexander V. Smal
Integer Programming and Combinatorial Optimization (IPCO), 2025
Paper arXiv
Lifting Dichotomies
Yaroslav Alekseev, Yuval Filmus, Alexander Smal
Computational Complexity Conference (CCC), 2024
Paper ECCC
Proving Unsatisfiability with Hitting Formulas
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals
Innovations in Theoretical Computer Science (ITCS), 2024
Paper arXiv ECCC
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games
Artur Ignatiev, Ivan Mihajlin, Alexander Smal
International Symposium on Algorithms and Computation (ISAAC), 2022
Paper ECCC
Toward Better Depth Lower Bounds: The XOR-KRW Conjecture
Ivan Mihajlin, Alexander Smal
Computational Complexity Conference (CCC), 2021
Paper ECCC
New Bounds on the Half-Duplex Communication Complexity
Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov
SOFSEM: Theory and Practice of Computer Science, 2021
Paper ECCC
Half-Duplex Communication Complexity
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal
International Symposium on Algorithms and Computation (ISAAC), 2018
Paper ECCC
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Mathematical Foundations of Computer Science (MFCS), 2016
Paper ECCC

Journal Articles

Irreducible Subcube Partitions
Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Ryazanov, Alexander V. Smal, Marc Vinyals
Electronic Journal of Combinatorics, vol. 30, no. 3, 2023
Paper arXiv
Prediction from Partial Information and Hindsight, an Alternative Proof
Alexander V. Smal, Navid Talebanfard
Information Processing Letters, vol. 136, pp. 102-104, 2018
Paper ECCC
Gate Elimination: Circuit Size Lower Bounds and #SAT Upper Bounds
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
Theoretical Computer Science, vol. 719, pp. 46-63, 2018
Paper
On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography
Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal
Theory of Computing Systems, vol. 51, no. 2, pp. 179-195, 2012
Paper ECCC

Preprints

Catalytic Computing and Register Programs Beyond Log-Depth
Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra
arXiv:2504.17412, 2025
arXiv ECCC
Simplifier: A New Tool for Boolean Circuit Simplification
Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin
arXiv:2503.19103, 2025
arXiv

Education

PhD in Computer Science
2008 – 2022
Steklov Institute of Mathematics at St.Petersburg, St. Petersburg, Russia
Advisor: Edward A. Hirsch
MSc in Computer Science
2006 – 2008
ITMO University, St. Petersburg, Russia
BSc in Computer Science
2002 – 2006
ITMO University, St. Petersburg, Russia