DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.21

Improved Space Bounds for Subset Sum

Authors: Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

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 of this result is the following fine-grained lower bound: assuming that 4-SUM cannot be solved in time O(n^{2-ε}) for all ε > 0, Circuit SAT cannot be solved in time O(g2^{(1-ε)n}), for all ε > 0 (where n and g denote the number of inputs and the number of gates, respectively). 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.

Cite as

Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin. Improved Space Bounds for Subset Sum. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{belova_et_al:LIPIcs.ESA.2024.21,
  author =	{Belova, Tatiana and Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan},
  title =	{{Improved Space Bounds for Subset Sum}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.21},
  URN =		{urn:nbn:de:0030-drops-210925},
  doi =		{10.4230/LIPIcs.ESA.2024.21},
  annote =	{Keywords: algorithms, subset sum, complexity, space, upper bounds}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.24

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

Authors: Tatiana Belova and Ivan Bliznets

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs.

Cite as

Tatiana Belova and Ivan Bliznets. Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{belova_et_al:LIPIcs.ISAAC.2022.24,
  author =	{Belova, Tatiana and Bliznets, Ivan},
  title =	{{Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.24},
  URN =		{urn:nbn:de:0030-drops-173097},
  doi =		{10.4230/LIPIcs.ISAAC.2022.24},
  annote =	{Keywords: Parameterized complexity, Hardness of approximation, Edge modification problems}
}

Search Results

Documents authored by Belova, Tatiana

Improved Space Bounds for Subset Sum

Abstract

Cite as

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

Abstract

Cite as

Thanks for your feedback!

Could not send message