Skip to content

Author

N. Chukhin

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Nov 2026

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$...

N. Chukhin, Karthik Gajulapalli, Alexander Golovnev et al. · 0 citations
Preprint Aug 2026

Improved Quantum Algorithms for Subset Sum and $k$-SUM

A new quantum algorithm solving worst-case $k-SUM in time $\widetilde O(n^{\Psi_k})$, which is not only faster for all $k$ congruent to $3$ or $6$ modulo $7, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances.

N. Chukhin, Alexander S. Kulikov, Maksim Levitskii et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.