1 citations · 1 across the 4 of their papers we have counts for
6 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…
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…