| Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility ML Carmosino, J Gao, R Impagliazzo, I Mihajlin, R Paturi, S Schneider Proceedings of the 2016 ACM Conference on Innovations in Theoretical …, 2016 | 90 | 2016 |
| Tight bounds for graph homomorphism and subgraph isomorphism M Cygan, FV Fomin, A Golovnev, AS Kulikov, I Mihajlin, J Pachocki, ... Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete …, 2016 | 21 | 2016 |
| Tight lower bounds on graph embedding problems M Cygan, FV Fomin, A Golovnev, AS Kulikov, I Mihajlin, J Pachocki, ... Journal of the ACM (JACM) 64 (3), 1-22, 2017 | 20 | 2017 |
| Approximating shortest superstring problem using de bruijn graphs A Golovnev, AS Kulikov, I Mihajlin Annual Symposium on Combinatorial Pattern Matching, 120-129, 2013 | 20 | 2013 |
| Hardness amplification for non-commutative arithmetic circuits ML Carmosino, R Impagliazzo, S Lovett, I Mihajlin 33rd Computational Complexity Conference (CCC 2018), 2018 | 12 | 2018 |
| Solving SCS for bounded length strings in fewer than 2n steps A Golovnev, AS Kulikov, I Mihajlin Information Processing Letters 114 (8), 421-425, 2014 | 10 | 2014 |
| Lower bounds for the graph homomorphism problem FV Fomin, A Golovnev, AS Kulikov, I Mihajlin International Colloquium on Automata, Languages, and Programming, 481-493, 2015 | 8 | 2015 |
| Solving 3-Superstring in 3 n/3 Time A Golovnev, AS Kulikov, I Mihajlin International Symposium on Mathematical Foundations of Computer Science, 480-491, 2013 | 7 | 2013 |
| Computation of hadwiger number and related contraction problems: Tight lower bounds FV Fomin, D Lokshtanov, I Mihajlin, S Saurabh, M Zehavi arXiv preprint arXiv:2004.11621, 2020 | 6 | 2020 |
| New lower bounds on circuit size of multi-output functions E Demenkov, AS Kulikov, O Melanich, I Mihajlin Theory of Computing Systems 56 (4), 630-642, 2015 | 5 | 2015 |
| Families with infants: A general approach to solve hard partition problems A Golovnev, AS Kulikov, I Mihajlin International Colloquium on Automata, Languages, and Programming, 551-562, 2014 | 5 | 2014 |
| Tight bounds for subgraph isomorphism and graph homomorphism FV Fomin, A Golovnev, AS Kulikov, I Mihajlin arXiv preprint arXiv:1507.03738, 2015 | 4 | 2015 |
| A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function AS Kulikov, O Melanich, I Mihajlin Conference on Computability in Europe, 432-439, 2012 | 4 | 2012 |
| Computing all MOD-functions simultaneously E Demenkov, AS Kulikov, I Mihajlin, H Morizumi International Computer Science Symposium in Russia, 81-88, 2012 | 3 | 2012 |
| Collapsing superstring conjecture A Golovnev, AS Kulikov, A Logunov, I Mihajlin, M Nikolaev arXiv preprint arXiv:1809.08669, 2018 | 2 | 2018 |
| Half-duplex communication complexity K Hoover, R Impagliazzo, I Mihajlin, AV Smal 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018 | 2 | 2018 |
| Beating brute force for (quantified) satisfiability of circuits of bounded treewidth D Lokshtanov, I Mikhailin, R Paturi, P Pudlak Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018 | 2 | 2018 |
| Families with infants: speeding up algorithms for NP-hard problems using FFT A Golovnev, AS Kulikov, I Mihajlin ACM Transactions on Algorithms (TALG) 12 (3), 1-17, 2016 | 2 | 2016 |
| Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds FV Fomin, D Lokshtanov, I Mihajlin, S Saurabh, M Zehavi ACM Transactions on Computation Theory (TOCT) 13 (2), 1-25, 2021 | | 2021 |
| LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, LIPICS V Guruswami, S Sandeep, D Fotakis, J Matuschke, O Papadigenopoulos, ... | | 2019 |
Alexander S. KulikovSteklov Institute of Mathematics at St. PetersburgVerified email at logic.pdmi.ras.ru
