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