Ivan Mihajlin
Ivan Mihajlin
Verified email at
Cited by
Cited by
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
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
Approximating shortest superstring problem using de bruijn graphs
A Golovnev, AS Kulikov, I Mihajlin
Annual Symposium on Combinatorial Pattern Matching, 120-129, 2013
Hardness amplification for non-commutative arithmetic circuits
ML Carmosino, R Impagliazzo, S Lovett, I Mihajlin
33rd Computational Complexity Conference (CCC 2018), 2018
Lower bounds for the graph homomorphism problem
FV Fomin, A Golovnev, AS Kulikov, I Mihajlin
Automata, Languages, and Programming: 42nd International Colloquium, ICALP …, 2015
Toward better depth lower bounds: The XOR-KRW conjecture
I Mihajlin, A Smal
36th Computational Complexity Conference (CCC 2021), 2021
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
Half-duplex communication complexity
K Hoover, R Impagliazzo, I Mihajlin, AV Smal
29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018
Solving 3-Superstring in 3 n/3 Time
A Golovnev, AS Kulikov, I Mihajlin
Mathematical Foundations of Computer Science 2013: 38th International …, 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
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
New lower bounds on circuit size of multi-output functions
E Demenkov, AS Kulikov, O Melanich, I Mihajlin
Theory of Computing Systems 56, 630-642, 2015
Polynomial formulations as a barrier for reduction-based hardness proofs
T Belova, A Golovnev, AS Kulikov, I Mihajlin, D Sharipov
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023
Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
D Lokshtanov, I Mikhailin, R Paturi, P Pudlák
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018
A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
AS Kulikov, O Melanich, I Mihajlin
How the World Computes: Turing Centenary Conference and 8th Conference on …, 2012
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
Computing all MOD-functions simultaneously
E Demenkov, AS Kulikov, I Mihajlin, H Morizumi
International Computer Science Symposium in Russia, 81-88, 2012
Collapsing superstring conjecture
A Golovnev, AS Kulikov, A Logunov, I Mihajlin, M Nikolaev
arXiv preprint arXiv:1809.08669, 2018
A better-than-3log (n) depth lower bound for De Morgan formulas with restrictions on top gates
I Mihajlin, A Sofronova
37th Computational Complexity Conference (CCC 2022), 2022
Complexity of linear operators
AS Kulikov, I Mikhailin, A Mokhov, V Podolskii
arXiv preprint arXiv:1812.11772, 2018
The system can't perform the operation now. Try again later.
Articles 1–20