{"id":"arxiv/2607.10343","url":"https://arxiv.org/abs/2607.10343","tags":["cs.DS","math.CO"],"score":0,"title":"Dense Subset Sum in Multi-Dimension","domain":"cs.DS","source":"arxiv","authors":["Lin Chen","Tingwei Hu","Yuchen Mao","Guochuan Zhang"],"reviews":0,"subject":"cs.DS","summary":"We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, given a set $A$ of $n$ vectors in the $d$-dimensional hyperrectangle $[N_1]\\times [N_2]\\times\\cdots\\times [N_d]$, we study the structure of $\\mathcal{S}(A)$, which is the set of all subset sums of $A$. We focus on the dense regime of the problem where $n \\gg \\sqrtΦ$ and $Φ= N_1 \\times \\cdots \\times N_d$. We show that for any constant $d\\geq 1$, if $n \\gg \\sqrtΦ$, then $\\mathcal{S}(A)$ contains a long generalized…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-11","reactions":{}}