Alexander Smal

According to our database, Alexander Smal authored at least 16 papers between 2010 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

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

Lifting dichotomies.

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Electron. Colloquium Comput. Complex., 2024

2023

Proving Unsatisfiability with Hitting Formulas.

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

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

Super-cubic lower bound for generalized Karchmer-Wigderson games.

Artur Ignatiev, Ivan Mihajlin, Alexander Smal

Electron. Colloquium Comput. Complex., 2022

Irreducible subcube partitions.

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

CoRR, 2022

2020

Toward better depth lower bounds: the XOR-KRW conjecture.

Ivan Mihajlin, Alexander Smal

Electron. Colloquium Comput. Complex., 2020

New bounds on the half-duplex communication complexity.

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

Electron. Colloquium Comput. Complex., 2020

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

Prediction from partial information and hindsight, an alternative proof.

Alexander V. Smal, Navid Talebanfard

Inf. Process. Lett., 2018

Half-duplex communication complexity.

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Electron. Colloquium Comput. Complex., 2018

2016

Circuit size lower bounds and #SAT upper bounds through a general framework.

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

Electron. Colloquium Comput. Complex., 2016

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

2010

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography.

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

Electron. Colloquium Comput. Complex., 2010