Ivan Mihajlin

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