Ivan Mihajlin

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 29

Top Topics

Subgraph Isomorphism

Sufficiently Accurate

Graph Pattern Matching

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. SODA (2024)
Alexander S. Kulikov, Ivan Mihajlin
If Edge Coloring is Hard under SETH, then SETH is False. SOSA (2024)
Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
Improved Space Bounds for Subset Sum. CoRR (2024)
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. CoRR (2023)
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov
Polynomial formulations as a barrier for reduction-based hardness proofs. SODA (2023)
Alexander S. Kulikov, Ivan Mihajlin
Polynomial formulations as a barrier for reduction-based hardness proofs. CoRR (2022)
Artur Ignatiev, Ivan Mihajlin, Alexander Smal
Super-cubic lower bound for generalized Karchmer-Wigderson games. Electron. Colloquium Comput. Complex. 29 (2022)
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
CNF Encodings of Parity. CoRR (2022)
Ivan Mihajlin, Anastasia Sofronova
A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates. Electron. Colloquium Comput. Complex. (2022)
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin
CNF Encodings of Parity. MFCS (2022)
Artur Ignatiev, Ivan Mihajlin, Alexander Smal
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games. ISAAC (2022)
Ivan Mihajlin, Anastasia Sofronova
A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. CCC (2022)
Ivan Mihajlin, Alexander Smal
Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. Computational Complexity Conference (2021)
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov
Minimum Common String Partition: Exact Algorithms. ESA (2021)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. ACM Trans. Comput. Theory 13 (2) (2021)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. CoRR (2020)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. ICALP (2020)
Ivan Mihajlin, Alexander Smal
Toward better depth lower bounds: the XOR-KRW conjecture. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
Collapsing Superstring Conjecture. APPROX-RANDOM (2019)
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal
Half-Duplex Communication Complexity. ISAAC (2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal
Half-duplex communication complexity. Electron. Colloquium Comput. Complex. 25 (2018)
Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
Hardness Amplification for Non-Commutative Arithmetic Circuits. Computational Complexity Conference (2018)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin
Collapsing Superstring Conjecture. CoRR (2018)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64 (3) (2017)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. CoRR (2016)
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. ITCS (2016)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12 (3) (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA (2016)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. CoRR (2015)
Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. Electron. Colloquium Comput. Complex. 22 (2015)
Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin
New Lower Bounds on Circuit Size of Multi-output Functions. Theory Comput. Syst. 56 (4) (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. CoRR (2015)
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Lower Bounds for the Graph Homomorphism Problem. ICALP (1) (2015)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with Infants: A General Approach to Solve Hard Partition Problems. ICALP (1) (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
steps. Inf. Process. Lett. 114 (8) (2014)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Solving 3-Superstring in 3 n/3 Time. MFCS (2013)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Approximating Shortest Superstring Problem Using de Bruijn Graphs. CPM (2013)
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Families with infants: a general approach to solve hard partition problems. CoRR (2013)
Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi
Computing All MOD-Functions Simultaneously. CSR (2012)
Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin
A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function. CiE (2012)