Ivan Mihajlin
Ivan Mihajlin
Verified email at eng.ucsd.edu
Title
Cited by
Cited by
Year
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
902016
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
212016
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
202017
Approximating shortest superstring problem using de bruijn graphs
A Golovnev, AS Kulikov, I Mihajlin
Annual Symposium on Combinatorial Pattern Matching, 120-129, 2013
202013
Hardness amplification for non-commutative arithmetic circuits
ML Carmosino, R Impagliazzo, S Lovett, I Mihajlin
33rd Computational Complexity Conference (CCC 2018), 2018
122018
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
102014
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
82015
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
72013
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
62020
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
52015
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
52014
Tight bounds for subgraph isomorphism and graph homomorphism
FV Fomin, A Golovnev, AS Kulikov, I Mihajlin
arXiv preprint arXiv:1507.03738, 2015
42015
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
42012
Computing all MOD-functions simultaneously
E Demenkov, AS Kulikov, I Mihajlin, H Morizumi
International Computer Science Symposium in Russia, 81-88, 2012
32012
Collapsing superstring conjecture
A Golovnev, AS Kulikov, A Logunov, I Mihajlin, M Nikolaev
arXiv preprint arXiv:1809.08669, 2018
22018
Half-duplex communication complexity
K Hoover, R Impagliazzo, I Mihajlin, AV Smal
29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018
22018
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
22018
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
22016
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
The system can't perform the operation now. Try again later.
Articles 1–20