A Structural Approach to Subset-Sum Problems

DOI10.1007/978-3-540-85221-6_19MaRDI QIDQ3601935zbMATH OpenOpenAlexFDO

Authors Van Vu

Publication date 12 February 2009

Published in Bolyai Society Mathematical Studies (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.3211

zbMATH Keywords

random matricessubset-sumErdős-Ginzburg-Ziv theoremCircular LawFolkman's conjectureFreiman-type structural theoreminverse Little\-wood-Offord theoremsquare-sum free setzero-sum-free sets

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13)

Abstract: We discuss a structural approach to subset-sum problems in additive combinatorics. The core of this approach are Freiman-type structural theorems, many of which will be presented through the paper. These results have applications in various areas, such as number theory, combinatorics and mathematical physics.

Recommendations

• Structural approach to subset sum problems
• Long arithmetic progressions in sumsets: Thresholds and bounds
• scientific article; zbMATH DE number 1315256
• scientific article; zbMATH DE number 1315254
• Finite and infinite arithmetic progressions in sumsets

Cited in

(8)

• Approximability of the Subset Sum Reconfiguration Problem
• New analytical results in subset-sum problem
• A Structure Theory for the Parametric Submodular Intersection Problem
• On a conjecture of Alon
• Solving dense subset-sum problems by using analytical number theory
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Subset sum problems with digraph constraints
• Improved approximation of linear threshold functions

This page was built for publication: A Structural Approach to Subset-Sum Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3601935)