Alexander Smal

According to our database, Alexander Smal authored at least 16 papers between 2011 and 2025.

Collaborative distances:

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

2025

Simplifier: A New Tool for Boolean Circuit Simplification.

Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin

CoRR, March, 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

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint.

Yuval Filmus, Roy Schwartz, Alexander V. Smal

Proceedings of the Integer Programming and Combinatorial Optimization, 2025

2024

Proving Unsatisfiability with Hitting Formulas.

Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Lifting Dichotomies.

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Irreducible Subcube Partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Ryazanov, Alexander V. Smal, Marc Vinyals

Electron. J. Comb., 2023

2022

Irreducible subcube partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals

CoRR, 2022

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games.

Artur Ignatiev, Ivan Mihajlin, Alexander Smal

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

New Bounds on the Half-Duplex Communication Complexity.

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

Proceedings of the SOFSEM 2021: Theory and Practice of Computer Science, 2021

Toward Better Depth Lower Bounds: The XOR-KRW Conjecture.

Ivan Mihajlin, Alexander Smal

Proceedings of the 36th Computational Complexity Conference, 2021

2018

Gate elimination: Circuit size lower bounds and #SAT upper bounds.

Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki

Theor. Comput. Sci., 2018

Half-Duplex Communication Complexity.

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

Prediction from Partial Information and Hindsight, an Alternative Proof.

Alexander Smal, Navid Talebanfard

Electron. Colloquium Comput. Complex., 2017

2016

Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.

Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2012

On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography.

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

Theory Comput. Syst., 2012

2011

Optimal heuristic algorithms for the image of an injective function.

Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Electron. Colloquium Comput. Complex., 2011