2024/01/14 by Chen, Xi, Nadimpalli, Shivam, Randolph, Tim +2
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.07242
A subset S of the Boolean hypercube \mathbbF2n is a sumset if S = \a + b : a, b∈ A\ for some A ⊆ \mathbbF2n. Sumsets are central objects of study in additive combinatorics, featuring in several influential results. We prove a lower bound of Ω(2n/2) for the number of queries needed to test whether a Boolean function f:\mathbbF2n → \0,1\ is the indicator function of a sumset. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal 2n/2 ⋅ poly(n)-query algorithm for a smoothed analysis formulation of the sumset refutation problem.