Ivan Mihajlin

activity

20132026

most citedFamilies with infants: a general approach to solve hard partition problems

2 citations · 3 across the 13 of their papers we have counts for

collaborators

Showing 2024Show all

2 papers · 1 filter

cs.CC2024★ 1 cited

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…

cs.CC2024

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 $n$ integers in time $O^{*} (2^{0.5 n})$ and space $O^{*} (2^{0.25 n})$ . The tim…