On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography EA Hirsch, D Itsykson, I Monakhov, A Smal Theory of Computing Systems 51 (2), 179-195, 2012 | 14 | 2012 |
Toward better depth lower bounds: The XOR-KRW conjecture I Mihajlin, A Smal 36th Computational Complexity Conference (CCC 2021), 2021 | 13 | 2021 |
Circuit size lower bounds and# SAT upper bounds through a general framework A Golovnev, AS Kulikov, AV Smal, S Tamaki 41st International Symposium on Mathematical Foundations of Computer Science …, 2016 | 12 | 2016 |
Prediction from partial information and hindsight, an alternative proof AV Smal, N Talebanfard Information Processing Letters 136, 102-104, 2018 | 10 | 2018 |
Half-duplex communication complexity K Hoover, R Impagliazzo, I Mihajlin, AV Smal 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018 | 10 | 2018 |
New bounds on the half-duplex communication complexity Y Dementiev, A Ignatiev, V Sidelnik, A Smal, M Ushakov International Conference on Current Trends in Theory and Practice of …, 2021 | 5 | 2021 |
Irreducible subcube partitions Y Filmus, E Hirsch, S Kurz, F Ihringer, A Riazanov, A Smal, M Vinyals arXiv preprint arXiv:2212.14685, 2022 | 4 | 2022 |
Proving unsatisfiability with hitting formulas Y Filmus, EA Hirsch, A Riazanov, A Smal, M Vinyals arXiv preprint arXiv:2302.06241, 2023 | 3 | 2023 |
Super-cubic lower bound for generalized karchmer-wigderson games A Ignatiev, I Mihajlin, A Smal 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 2022 | 3 | 2022 |
Optimal heuristic algorithms for the image of an injective function EA Hirsch, DM Itsykson, VO Nikolaenko, AV Smal Journal of Mathematical Sciences 188 (1), 7-16, 2013 | 3 | 2013 |
Gate elimination: Circuit size lower bounds and# SAT upper bounds A Golovnev, AS Kulikov, AV Smal, S Tamaki Theoretical Computer Science 719, 46-63, 2018 | 2 | 2018 |
Optimal heuristic algorithms for the image of an injective function EA Hirsch, DM Itsykson, VO Nikolaenko, AV Smal Записки научных семинаров ПОМИ 399 (0), 15-31, 2012 | 2 | 2012 |
Succinct Interactive Proofs for Quantified Boolean Formulas EA Hirsch, D van Melkebeek, A Smal | | 2013 |
On an optimal randomized acceptor for graph nonisomorphism Edward A. Hirsch Steklov Institute of Mathematics at St. Petersburg, Russian Academy of Sciences Dmitry Itsykson … V Nikolaenko, A Smal First Russian-Finnish Symposium on Discrete Mathematics 6 (4), 21, 2011 | | 2011 |
Summer School “Computational Complexity Theory” A Kulikov, I Mihajlin, A Smal, D Sokolov | | |