| 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 | 117 | 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 | 25 | 2016 |
| Approximating shortest superstring problem using de bruijn graphs A Golovnev, AS Kulikov, I Mihajlin Annual Symposium on Combinatorial Pattern Matching, 120-129, 2013 | 21 | 2013 |
| 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 |
| Hardness amplification for non-commutative arithmetic circuits ML Carmosino, R Impagliazzo, S Lovett, I Mihajlin 33rd Computational Complexity Conference (CCC 2018), 2018 | 13 | 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 | 12 | 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 | 10 | 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 | 9 | 2013 |
| 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 | 6 | 2021 |
| 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 | 6 | 2015 |
| Toward better depth lower bounds: the XOR-KRW conjecture I Mihajlin, A Smal 36th Computational Complexity Conference (CCC 2021), 2021 | 5 | 2021 |
| Half-duplex communication complexity K Hoover, R Impagliazzo, I Mihajlin, AV Smal 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018 | 5 | 2018 |
| 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 |
| 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 | 5 | 2012 |
| 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 | 4 | 2016 |
| Tight bounds for subgraph isomorphism and graph homomorphism FV Fomin, A Golovnev, AS Kulikov, I Mihajlin arXiv preprint arXiv:1507.03738, 2015 | 4 | 2015 |
| Computing all MOD-functions simultaneously E Demenkov, AS Kulikov, I Mihajlin, H Morizumi International Computer Science Symposium in Russia, 81-88, 2012 | 4 | 2012 |
| Collapsing superstring conjecture A Golovnev, AS Kulikov, A Logunov, I Mihajlin, M Nikolaev arXiv preprint arXiv:1809.08669, 2018 | 3 | 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 | 3 | 2018 |
| Polynomial formulations as a barrier for reduction-based hardness proofs AS Kulikov, I Mihajlin arXiv preprint arXiv:2205.07709, 2022 | | 2022 |
Alexander S. KulikovSteklov Institute of Mathematics at St. PetersburgVerified email at logic.pdmi.ras.ru
