3 papers
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 integers in time and space . The tim…
cs.CC2023
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin +3
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponent…
cs.CC2022
Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov +2
The Strong Exponential Time Hypothesis (SETH) asserts that for every there exists such that -SAT requires time . The field of fine-grained…