Ivan Mihajlin

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Polynomial formulations as a barrier for reduction-based hardness proofs.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates.

[BibT_eX]

[DOI]

Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2022

Super-cubic lower bound for generalized Karchmer-Wigderson games.

[BibT_eX]

[DOI]

Artur Ignatiev

Alexander Smal

Electron. Colloquium Comput. Complex., 2022

Polynomial formulations as a barrier for reduction-based hardness proofs.

[BibT_eX]

[DOI]

CoRR, 2022

CNF Encodings of Parity.

[BibT_eX]

[DOI]

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates.

[BibT_eX]

[DOI]

Anastasia Sofronova

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Minimum Common String Partition: Exact Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Toward better depth lower bounds: the XOR-KRW conjecture.

[BibT_eX]

[DOI]

Alexander Smal

Electron. Colloquium Comput. Complex., 2020

2019

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Half-duplex communication complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Hardness Amplification for Non-Commutative Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

CoRR, 2018

2017

Tight Lower Bounds on Graph Embedding Problems.

[BibT_eX]

[DOI]

J. ACM, 2017

2016

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

New Lower Bounds on Circuit Size of Multi-output Functions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.

[BibT_eX]

[DOI]

CoRR, 2015

Lower Bounds for the Graph Homomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Solving SCS for bounded length strings in fewer than 2<sup>n</sup> steps.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Families with Infants: A General Approach to Solve Hard Partition Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Solving 3-Superstring in 3 n/3 Time.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Approximating Shortest Superstring Problem Using de Bruijn Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012

Computing All MOD-Functions Simultaneously.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2012

A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function.

[BibT_eX]

[DOI]

Olga Melanich