Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MAKSIM LEVITSKII:
All reports by Author Maksim Levitskii:

TR26-256 | 13th October 2026
Nikolai Chukhin, Alexander Kulikov, Maksim Levitskii, Ivan Mihajlin

Polynomial Block Lengths Are Necessary and Sufficient to Beat Insertion Sort

Insertion sort is a basic algorithm for sorting permutations: it repeatedly cuts out one element and inserts it at its place among the elements sorted so far.
It sorts every permutation of length $n$ with at most $n-1$ such moves, and some permutations cannot be sorted with fewer ... more >>>


TR26-135 | 7th August 2026
Nikolai Chukhin, Alexander Kulikov, Maksim Levitskii, Ivan Mihajlin

Quantum Algorithms for Subset SUM and $k$-SUM: Faster and Simpler

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem ... more >>>




ISSN 1433-8092 | Imprint