2026-07-21T19:38:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25519 2026-03-19T13:34:27Z ddc:004 open_access

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions Datta, Swarnalipa Ghosh, Arijit Kayal, Chandrima Paraashar, Manaswi Roy, Manmatha Boolean Function Isomorphism of Boolean Function Fourier Analysis Sublinear Algorithm Property Testing Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swarnalipa Datta and Arijit Ghosh and Chandrima Kayal and Manaswi Paraashar and Manmatha Roy 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.30 urn:nbn:de:0030-drops-255194 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode