5 papers
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…
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…