Publications

Chukhin, N., Kulikov, A. S., Levitskii, M., & Mihajlin, I. (2026). Improved Quantum Algorithms for Subset Sum and k-SUM. [ECCC]

The Subset Sum problem asks whether, given $n$ integers and a target, some subset sums to the target. Its best known worst-case classical running time is $O^*(2^{n/2})$, while the previous best quantum upper bound was $O^*(2^{n/3})$. The $k$-SUM problem asks whether one can select entries from $k$ lists that sum to a target.

We present a new quantum algorithm for worst-case $k$-SUM that improves the best known exponent for all $k$ congruent to $3$ or $6$ modulo $7$. Unlike the preceding bound, it gives a worst-case guarantee rather than one restricted to single-solution random instances. Combining our algorithm for 7-SUM with the standard block reduction yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previous $O^*(2^{n/3})$ bound.

We came up with quite a simple quantum algorithm for the $k$-SUM problem. The previous fastest worst-case quantum algorithm ran in time roughly $n^{0.33k}$, and we pushed this down to roughly $n^{0.29k}$ for large $k$. This also gives a $2^{2n/7} \approx 2^{0.286n}$ quantum upper bound for Subset Sum (note that the classical quantum techniques cannot beat the $0.25$ barrier without improving the deterministic $2^{0.5 n}$ algorithm).

The algorithm itself is very easy. In fact, it is similar to what was already known in the cryptographic literature, but the previous results applied only random instances of $k$-SUM.
Chukhin, N., Kulikov, A. S., Mihajlin, I., & Smal, A. (2026). The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already. [arXiv]

In the Shortest Common Superstring problem, one is given a set of strings and seeks a shortest string containing each input string as a substring. The longstanding greedy superstring conjecture states that repeatedly merging a pair of strings with maximum overlap gives a 2-approximation. Even for instances in which all strings have the same length $k$, the exact approximation ratio was previously unknown for every $k \geq 3$.

We prove that strings of length six already suffice for the greedy algorithm to attain approximation ratio 2, and hence the ratio is at least 2 for every $k \geq 6$. We also completely characterize the length-three case, proving that its worst-case approximation ratio is $9/5$.

In this paper, we were interested in the greedy algorithm for the Shortest Common Superstring problem, which is conjectured to be a 2-approximation. The annoying part is that we are still very far from proving this, and from understanding the greedy algorithm well in general. We constructed an instance of strings of length 6 on which the greedy algorithm already has approximation ratio 2. This refutes a previous conjecture predicting ratio $2-1/k$ for strings of length $k$. We also analyzed the algorithm’s behavior on strings of length 3 and proved that its approximation ratio is exactly $9/5$ there. Unfortunately, the upper bound is quite nontrivial even for this seemingly trivial class of inputs.
Braulov, G., Chukhin, N., Kulikov, A. S., & Mihajlin, I. (2026). Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy. [ECCC]

The graph homomorphism problem $\mathrm{HOM}$ asks whether an $n$-vertex source graph $G$ maps to an $h$-vertex target graph $H$ while preserving edges. A straightforward algorithm has running time $O(2^{n\log h})$, and under ETH there are no $2^{o(n\log h)}$ algorithms. We study the complexity of $\mathrm{HOM}$ in terms of the degeneracy of $H$, a natural graph parameter between the known algorithmic and hardness regimes.

We show that, under ETH, there is no $2^{o(\operatorname{degen}(H)n)}$ algorithm for any value of $\operatorname{degen}(H)$ as a function of $n$. Bounded degeneracy alone does not make target size benign: even targets of degeneracy at most two and quasi-polynomial size force $n^{\Omega(n)}$-scale hardness. Finally, we introduce a no-compression barrier explaining why known fine-grained lower bounds for sparse 2-CSP are not tight under ETH.

The graph homomorphism problem (HOM) and its variants have very nice dichotomies in several computational settings: P versus NP-hard, FP versus #P-hard, FPT versus W[1]-hard, and so on. So a natural question is: on which instances does HOM become hard in the fine-grained sense?

For some structural parameters, the picture was pretty clear. For example, if the target graph has small treewidth, the problem is easy to solve. On the other hand, even a constant chromatic number does not prevent the problem from being very hard. So, we looked at perhaps the most natural parameter for which nothing was known and something rather crazy happened. We considered the graph degeneracy and obtained that it does not make the problem easy, but the problem is not hard anymore. We proved hardness for several degeneracy regimes and also showed why substantially improving our bounds would probably be very challenging.

Maybe this is my favourite part. If $s$ denotes the input bit size, then, to the best of our knowledge, no known fine-grained reduction under ETH gives a $2^{\omega(s/\log s)}$ lower bound. We tried to explain why. A sufficiently strong refutation of this barrier would imply new circuit lower bounds, and substantially improving our degeneracy result would also break the $s/\log s$ barrier. I think much more can be derived from this conjecture (an SETH analogue is already known to be true).
Chukhin, N. (2026). A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank. [ECCC]

Recently, together with Kulikov, Mihajlin, and Smirnova, we gave conditional constructions of functions with large monotone circuit complexity, matrices with high rigidity, and three-dimensional tensors of strongly superlinear rank. In this note, I strengthen the rigidity construction under the same assumption and, as a direct consequence, immediately obtain a slightly improved trade-off theorem for tensor rank.
Chukhin, N., Kulikov, A. S., Mihajlin, I., & Smirnova, A. (2026). Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. [STACS]

Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform lower bounds and nonuniform lower bounds in restricted circuit models. In this paper, we show how uniform nondeterministic lower bounds can be used to construct generators of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank.

If, for some $\varepsilon$ and $k$, $k$-SAT cannot be solved in input-oblivious co-nondeterministic time $O(2^{(1/2+\varepsilon)n})$, then there exists a monotone Boolean function family in coNP of monotone circuit size $2^{\Omega(n/\log n)}$. This gives a win-win circuit lower bound: either $E^{NP}$ requires superlinear series-parallel circuits or coNP requires exponentially large monotone circuits.

If MAX-3-SAT cannot be solved in co-nondeterministic time $O(2^{(1-\varepsilon)n})$ for every $\varepsilon>0$, then there exist small families of matrices with rigidity exceeding the best known constructions, as well as small families of three-dimensional tensors of rank $n^{1+\Delta}$ for some $\Delta>0$.

In this paper, we proved several win-win theorems. Probably the most interesting says that either $E^{\mathrm{NP}}$ requires superlinear series-parallel circuits, or $\mathrm{coNP}$ contains a monotone function family requiring circuits of size $2^{\Omega(n/\log n)}$ – far stronger than what is known unconditionally. And the proof is surprisingly simple.

We then extended the same basic idea to construct other hard objects: not only Boolean functions with high monotone circuit complexity, but also rigid matrices and tensors of high rank. In each case, the idea is quite intuitive – to reduce the complexity of solving a computational problem to a structural property of the objects we construct. Hence, if the problem is hard to solve, the objects should be ``hard’’.
Chukhin, N., Kulikov, A. S., & Mikhajlin, I. (2025). Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. [STACS]

Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of $(3-o(1))\log n$ established by Håstad over 25 years ago. The Karchmer–Raz–Wigderson conjecture offers a promising approach to advance these bounds and separate P from NC¹. It suggests that the depth complexity of a function composition approximates the sum of the depth complexities of its components.

In this paper, we examine the strong composition of the Karchmer–Wigderson relations for the parity function and a random Boolean function. We prove that with probability $1-o(1)$, any protocol solving this composition requires at least $n^{3-o(1)}$ leaves. This establishes a depth lower bound of $(3-o(1))\log n$, matching Håstad’s bound, while applying to a broader class of inner functions.

Our proof combines formal complexity measures: Khrapchenko’s method first shows that many instances remain unsolved after several communication steps, and a second measure shows that the remaining problem is at least as hard as the corresponding OR composition.

One day, people will prove very strong circuit-depth lower bounds. Unfortunately, to get there, we need new techniques. We started from the function behind the strongest known formula-depth lower bound (often called Andreev’s function), which is a composition of a hard function with XOR. We flipped the order and considered a composition of XOR with a hard function.

It is natural to expect that this reversal should not change the formula complexity very much. The catch is that current methods cannot prove a strong lower bound for this. Our paper tries to make progress on this, and we could prove the desired kind of bound only for the stronger model. We hope this may become one step toward better depth lower bounds.
Belova, T., Chukhin, N., Kulikov, A. S., & Mihajlin, I. (2024). Improved Space Bounds for Subset Sum. [ESA]

More than 40 years ago, Schroeppel and Shamir presented an algorithm that solves the Subset Sum problem for $n$ integers in time $O^*(2^{0.5n})$ and space $O^*(2^{0.25n})$. The time upper bound remains unbeaten, but the space upper bound has been improved to $O^*(2^{0.249999n})$ in a recent breakthrough paper by Nederlof and Węgrzycki (STOC 2021). Their algorithm is a clever combination of a number of previously known techniques with a new reduction and a new algorithm for the Orthogonal Vectors problem.

In this paper, we give two new algorithms for Subset Sum. We start by presenting an Arthur–Merlin algorithm: upon receiving the verifier’s randomness, the prover sends an $n/4$-bit long proof to the verifier who checks it in deterministic time and space $O^*(2^{n/4})$. An interesting consequence is the following fine-grained lower bound: assuming that 4-SUM cannot be solved in time $O(n^{2-\varepsilon})$ for all $\varepsilon>0$, Circuit SAT cannot be solved in time $O(g2^{(1-\varepsilon)n})$ for all $\varepsilon>0$, where $n$ and $g$ denote the number of inputs and gates.

Then, we improve the space bound by Nederlof and Węgrzycki to $O^*(2^{0.246n})$ and also simplify their algorithm and its analysis. We achieve this space bound by further filtering sets of subsets using a random prime number. This allows us to reduce an instance of Subset Sum to a larger number of instances of smaller size.