1 citations · 1 across the 9 of their papers we have counts for
10 papers
A Tight Cycle-Cover Inequality for Shortest Common Superstring
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1
In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best…
The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1
In the Shortest Common Superstring (SCS) problem, one is given a set of strings and is asked to find a string of minimum length containing each of the input strings as a substring.…
Improved Quantum Algorithms for Subset Sum and -SUM
Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1
The Subset Sum problem asks whether, given integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is (Horo…
If Edge Coloring is Hard under SETH, then SETH is False
Alexander S. Kulikov, Ivan Mihajlin
The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time (let alone ), where is the number of nodes of the inp…
Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy
Grigorii Braulov, Nikolai Chukhin, Alexander S. Kulikov +1
The graph homomorphism problem HOM is: given an -vertex source graph and an -vertex target graph , is there a mapping from to that preserves edges? A str…
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1
Proving complexity lower bounds remains a challenging task: we only know how to prove conditional uniform lower bounds and nonuniform lower bounds in restricted circuit models. Wil…
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin
Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of established by Hastad over 25 years ago. Th…
Improved Space Bounds for Subset Sum
Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov +1
More than 40 years ago, Schroeppel and Shamir presented an algorithm that solves the Subset Sum problem for integers in time and space . The tim…
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin +3
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponent…
Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov +2
The Strong Exponential Time Hypothesis (SETH) asserts that for every there exists such that -SAT requires time . The field of fine-grained…