research-article

Open access

Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

Authors:

Karl Bringmann,

Vasileios NakosAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 982 - 995

https://doi.org/10.1145/3357713.3384308

Published: 22 June 2020 Publication History

PDF eReader

Abstract

In the classical SubsetSum problem we are given a set X and a target t, and the task is to decide whether there exists a subset of X which sums to t. A recent line of research has resulted in (t · poly (logt))-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time O(n · |S(X,t)|), where S(X,t) is the set of all subset sums of X that are smaller than t. All previous pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set S(X,t).

As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time |S(X,t)|·poly(logt). In particular, we ask whether S(X,t) can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time |S(X,t)|^4/3 · poly(logt).

Central to our approach is the study of top- k -convolution, a natural problem of independent interest: given degree-d sparse polynomials with non-negative coefficients, compute the lowest k non-zero monomials of their product. We design an algorithm running in time k ^4/3 poly(logd), by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets.

Cited By

View all

Chen LLian JMao YZhang GMohar BShinkar IO'Donnell R(2024)Approximating Partition in Near-Linear TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649727(307-318)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649727
Jin CXu YMohar BShinkar IO'Donnell R(2024)Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and MoreProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649605(1573-1584)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649605
Chen LLian JMao YZhang G(2024)An Improved Pseudopolynomial Time Algorithm for Subset Sum2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00129(2202-2216)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00129
Show More Cited By

Index Terms

Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
1. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Faster Pseudopolynomial Time Algorithms for Subset Sum

Given a (multi) set S of n positive integers and a target integer u, the subset sum problem is to decide if there is a subset of S that sums up to u. We present a series of new algorithms that compute and return all the realizable subset sums up to the ...
SETH-based Lower Bounds for Subset Sum and Bicriteria Path
Subset Sumand k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of ...
A near-linear pseudopolynomial time algorithm for subset sum
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

Given a set Z of n positive integers and a target value t, the SubsetSum problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves SubsetSum in time O(nt). This has been improved to O(n max Z) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

H2020 European Research Council

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
579
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)19

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen LLian JMao YZhang GMohar BShinkar IO'Donnell R(2024)Approximating Partition in Near-Linear TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649727(307-318)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649727
Jin CXu YMohar BShinkar IO'Donnell R(2024)Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and MoreProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649605(1573-1584)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649605
Chen LLian JMao YZhang G(2024)An Improved Pseudopolynomial Time Algorithm for Subset Sum2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00129(2202-2216)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00129
Alonistiotis GAntonopoulos AMelissinos NPagourtzis APetsalakis SVasilakis M(2024)Approximating subset sum ratio via partition computationsActa Informatica10.1007/s00236-023-00451-761:2(101-113)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00236-023-00451-7
Bliznets INederlof JSzilágyi K(2024)Parameterized Algorithms for Covering by Arithmetic ProgressionsSOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_9(125-138)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_9
Chan TJin CWilliams VXu Y(2023)Faster Algorithms for Text-to-Pattern Hamming Distances2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00136(2188-2203)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00136
Antonopoulos APagourtzis APetsalakis SVasilakis M(2022)Faster algorithms for k-subset sum and variationsJournal of Combinatorial Optimization10.1007/s10878-022-00928-045:1Online publication date: 1-Dec-2022
https://doi.org/10.1007/s10878-022-00928-0
Alonistiotis GAntonopoulos AMelissinos NPagourtzis APetsalakis SVasilakis M(2022)Approximating Subset Sum Ratio via Subset Sum ComputationsCombinatorial Algorithms10.1007/978-3-031-06678-8_6(73-85)Online publication date: 29-May-2022
https://doi.org/10.1007/978-3-031-06678-8_6
Antonopoulos APagourtzis APetsalakis SVasilakis M(2022)Faster Algorithms for $$k\text {-}\textsc {Subset}\,\textsc {Sum}$$ and VariationsFrontiers of Algorithmics10.1007/978-3-030-97099-4_3(37-52)Online publication date: 3-Mar-2022
https://doi.org/10.1007/978-3-030-97099-4_3
Bringmann KNakos VMarx D(2021)A fine-grained perspective on approximating subset sum and partitionProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458172(1797-1815)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458172
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Faster Pseudopolynomial Time Algorithms for Subset Sum

SETH-based Lower Bounds for Subset Sum and Bicriteria Path

A near-linear pseudopolynomial time algorithm for subset sum