2023/09/26 by Kızıldağ, Eren C.
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2309.15115
We consider the random number partitioning problem (NPP): given a list X∼ N(0,In) of numbers, find a partition σ∈\-1,1\n with a small objective value H(σ)=(1)/(√(n))|⟨ σ,X⟩|. The 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 NPP: fix a σ^* and generate X∼ N(0,In) conditional on H(σ^*)≤ 3-n. The NPP and its planted counterpart are statistically distinguishable as the smallest objective value under the former is Θ(√(n)2-n) w.h.p. Our first focus is on the values of H(σ). We show that, perhaps surprisingly, planting does not induce partitions with an objective value substantially smaller than 2-n: minσ≠ ± σ^*H(σ) = \widetildeΘ(2-n) w.h.p. Furthermore, we completely characterize the smallest H(σ) achieved at any fixed distance from σ^*. Our second focus is on the algorithmic problem of efficiently finding a partition σ, not necessarily equal to ±σ^*, with a small H(σ). We show that planted NPP exhibits an intricate geometrical property known as the multi Overlap Gap Property (m-OGP) for values 2-Θ(n). We then leverage the m-OGP to show that stable algorithms satisfying a certain anti-concentration property fail to find a σ with H(σ)=2-Θ(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.