Alexander V. Smal

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Catalytic computing and register programs beyond log-depth	2026-08-05	Paper
Lifting dichotomies	2026-01-28	Paper
Separating coverage and submodular: maximization subject to a cardinality constraint	2025-12-22	Paper
Lifting dichotomies Computational Complexity	2025-11-28	Paper
Proving unsatisfiability with hitting formulas	2025-11-04	Paper
Super-cubic lower bound for generalized Karchmer-Wigderson games	2024-09-11	Paper
Irreducible subcube partitions The Electronic Journal of Combinatorics	2024-02-23	Paper
Toward better depth lower bounds: the XOR-KRW conjecture	2023-07-12	Paper
Proving Unsatisfiability with Hitting Formulas	2023-02-13	Paper
Half-duplex communication complexity	2022-07-21	Paper
New bounds on the half-duplex communication complexity	2022-03-24	Paper
Prediction from partial information and hindsight, an alternative proof Information Processing Letters	2018-05-25	Paper
Circuit size lower bounds and \#SAT upper bounds through a general framework	2018-03-21	Paper
Gate elimination: circuit size lower bounds and \#SAT upper bounds Theoretical Computer Science	2018-03-12	Paper
Optimal heuristic algorithms for the image of an injective function Journal of Mathematical Sciences (New York)	2013-04-09	Paper
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography Theory of Computing Systems	2012-12-07	Paper

Research outcomes over time

This page was built for person: Alexander V. Smal