Testing Fourier Dimensionality and Sparsity

DOI10.1137/100785429zbMath1235.94084MaRDI QIDQ5894337

Parikshit Gopalan, Ryan O'Donnell, Amir Shpilka, Karl Wimmer, Rocco A. Servedio

Publication date: 7 November 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100785429

zbMATH Keywords

Fourier spectrum; discrete Fourier analysis; property testing; local testability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94C12: Fault detection; testing in circuits and networks

Related Items

Unnamed Item, Structure of Protocols for XOR Functions, Unnamed Item, Unnamed Item, A unified framework for testing linear‐invariant properties, Unnamed Item, Almost optimal distribution-free junta testing, Fourier Sparsity of GF(2) Polynomials, A generalization of a theorem of Rothschild and van Lint, Sensitivity, affine transforms and quantum communication complexity, A generalization of a theorem of Rothschild and van Lint, Almost Optimal Testers for Concise Representations., On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers, An improved test of Boolean functions for \(k\)-dimensionality, Algebraically degenerate approximations of Boolean functions, Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions, On the structure of Boolean functions with small spectral norm, On the decision tree complexity of threshold functions, Exponentially improved algorithms and lower bounds for testing signed majorities, An optimal tester for \(k\)-Linear