Planted Random Number Partitioning Problem

We consider the random number partitioning problem ($\mathtt{\text{NPP}}$): given a list $X\sim \mathcal{N}(0,I_n)$ of numbers, find a partition $\sigma \in \{-1,1{\}}^n$ with a small objective value $H(\sigma )=\frac{1}{\sqrt{n}}\mid ⟨\sigma ,X⟩\mid$. The $\mathtt{\text{NPP}}$ is widely studied in computer science; it is also closely related to the design of randomized controlled trials. In this paper, we propose a planted version of the $\mathtt{\text{NPP}}$: fix a ${\sigma }^{\ast }$ and generate $X\sim \mathcal{N}(0,I_n)$ conditional on $H({\sigma }^{\ast })\le 3^{-n}$. The $\mathtt{\text{NPP}}$ and its planted counterpart are statistically distinguishable as the smallest objective value under the former is $\mathrm{\Theta }(\sqrt{n}{2}^{-n})$ w.h.p. Our first focus is on the values of $H(\sigma )$. We show that, perhaps surprisingly, planting does not induce partitions with an objective value substantially smaller than $2^{-n}$: ${\min }_{\sigma \mathrm{\ne }\pm {\sigma }^{\ast }}H(\sigma )=\tilde{\mathrm{\Theta }}(2^{-n})$ w.h.p. Furthermore, we completely characterize the smallest $H(\sigma )$ achieved at any fixed distance from ${\sigma }^{\ast }$. Our second focus is on the algorithmic problem of efficiently finding a partition $\sigma$, not necessarily equal to $\pm {\sigma }^{\ast }$, with a small $H(\sigma )$. We show that planted $\mathtt{\text{NPP}}$ exhibits an intricate geometrical property known as the multi Overlap Gap Property ($m$-OGP) for values $2^{-\mathrm{\Theta }(n)}$. We then leverage the $m$-OGP to show that stable algorithms satisfying a certain anti-concentration property fail to find a $\sigma$ with $H(\sigma )=2^{-\mathrm{\Theta }(n)}$. Our results are the first instance of the $m$-OGP being established and leveraged to rule out stable algorithms for a planted model. More importantly, they show that the $m$-OGP framework can also apply to planted models, if the algorithmic goal is to return a solution with a small objective value.