2026-07-25T06:06:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22648 2026-04-17T05:31:49Z ddc:004 open_access

Estimating Euclidean Distance to Linearity Bogdanov, Andrej Taschin, Lorenzo sublinear-time algorithms statistical estimation analysis of boolean functions property testing regression Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Bogdanov and Lorenzo Taschin 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.20 urn:nbn:de:0030-drops-226481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode