2026-07-23T19:43:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24482 2025-12-16T13:59:43Z ddc:004 open_access

Testing Sumsets Is Hard Chen, Xi Nadimpalli, Shivam Randolph, Tim Servedio, Rocco A. Zamir, Or Sumsets additive combinatorics property testing Boolean functions A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. 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 {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Shivam Nadimpalli and Tim Randolph and Rocco A. Servedio and Or Zamir 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.14 urn:nbn:de:0030-drops-244822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode