A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function. - Alexander S. Kulikov; Olga Melanich; Ivan Mihajlin (CiE, 2012)

Computing All MOD-Functions Simultaneously. - Evgeny Demenkov; Alexander S. Kulikov; Ivan Mihajlin; Hiroki Morizumi (CSR, 2012)

Approximating Shortest Superstring Problem Using de Bruijn Graphs. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (CPM, 2013)

Solving 3-Superstring in 3 n/3 Time. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (MFCS, 2013)

Families with Infants: A General Approach to Solve Hard Partition Problems. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ICALP (1), 2014)

Solving SCS for bounded length strings in fewer than 2n steps. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (Inf. Process. Lett., 2014)

Lower Bounds for the Graph Homomorphism Problem. - Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ICALP (1), 2015)

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. - Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (CoRR, 2015)

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. - Marco Carmosino; Jiawei Gao 001; Russell Impagliazzo; Ivan Mihajlin; Ramamohan Paturi; Stefan Schneider 003 (Electron. Colloquium Comput. Complex., 2015)

New Lower Bounds on Circuit Size of Multi-output Functions. - Evgeny Demenkov; Alexander S. Kulikov; Olga Melanich; Ivan Mihajlin (Theory Comput. Syst., 2015)

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (SODA, 2016)

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. - Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin (ACM Trans. Algorithms, 2016)

Tight Lower Bounds on Graph Embedding Problems. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (J. ACM, 2017)

Collapsing Superstring Conjecture. - Alexander Golovnev; Alexander S. Kulikov; Alexander Logunov; Ivan Mihajlin (CoRR, 2018)

Hardness Amplification for Non-Commutative Arithmetic Circuits. - Marco Carmosino; Russell Impagliazzo; Shachar Lovett; Ivan Mihajlin (Electron. Colloquium Comput. Complex., 2018)

Half-duplex communication complexity. - Kenneth Hoover; Russell Impagliazzo; Ivan Mihajlin; Alexander Smal (Electron. Colloquium Comput. Complex., 2018)

Collapsing Superstring Conjecture. - Alexander Golovnev; Alexander S. Kulikov; Alexander Logunov; Ivan Mihajlin; Maksim Nikolaev (APPROX-RANDOM, 2019)

Toward better depth lower bounds: the XOR-KRW conjecture. - Ivan Mihajlin; Alexander Smal (Electron. Colloquium Comput. Complex., 2020)

Minimum Common String Partition: Exact Algorithms. - Marek Cygan; Alexander S. Kulikov; Ivan Mihajlin; Maksim Nikolaev; Grigory Reznikov (ESA, 2021)

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. - Fedor V. Fomin; Daniel Lokshtanov; Ivan Mihajlin; Saket Saurabh 001; Meirav Zehavi (ACM Trans. Comput. Theory, 2021)

A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. - Ivan Mihajlin; Anastasia Sofronova (CCC, 2022)

CNF Encodings of Parity. - Gregory Emdin; Alexander S. Kulikov; Ivan Mihajlin; Nikita Slezkin (MFCS, 2022)

Polynomial formulations as a barrier for reduction-based hardness proofs. - Alexander S. Kulikov; Ivan Mihajlin (CoRR, 2022)

Super-cubic lower bound for generalized Karchmer-Wigderson games. - Artur Ignatiev; Ivan Mihajlin; Alexander Smal (Electron. Colloquium Comput. Complex., 2022)

A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates. - Ivan Mihajlin; Anastasia Sofronova (Electron. Colloquium Comput. Complex., 2022)

Polynomial formulations as a barrier for reduction-based hardness proofs. - Tatiana Belova; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Denil Sharipov (SODA, 2023)

Improved Space Bounds for Subset Sum. - Tatiana Belova; Nikolai Chukhin; Alexander S. Kulikov; Ivan Mihajlin (ESA, 2024)

Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. - Tatiana Belova; Alexander S. Kulikov; Ivan Mihajlin; Olga Ratseeva; Grigory Reznikov; Denil Sharipov (SODA, 2024)

If Edge Coloring is Hard under SETH, then SETH is False. - Alexander S. Kulikov; Ivan Mihajlin (SOSA, 2024)

Deriving Nonuniform Lower Bounds from Uniform Nondeterministic Lower Bounds. - Nikolai Chukhin; Alexander S. Kulikov; Ivan Mihajlin; Arina Smirnova (CoRR, 2024)

CNF Encodings of Symmetric Functions. - Gregory Emdin; Alexander S. Kulikov; Ivan Mihajlin; Nikita Slezkin (Theory Comput. Syst., 2024)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. - Nikolai Chukhin; Alexander S. Kulikov; Ivan Mihajlin (STACS, 2025)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond. - Nikolai Chukhin; Alexander S. Kulikov; Ivan Mihajlin; Arina Smirnova (Electron. Colloquium Comput. Complex., 2025)