Testing Fourier Dimensionality and Sparsity
From MaRDI portal
Publication:5894337
DOI10.1137/100785429zbMath1235.94084OpenAlexW2084369441MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Fault detection; testing in circuits and networks (94C12)
Related Items
On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers ⋮ Algebraically degenerate approximations of Boolean functions ⋮ Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions ⋮ An optimal tester for \(k\)-Linear ⋮ Structure of Protocols for XOR Functions ⋮ An improved test of Boolean functions for \(k\)-dimensionality ⋮ Almost Optimal Testers for Concise Representations. ⋮ Fourier Sparsity of GF(2) Polynomials ⋮ On the structure of Boolean functions with small spectral norm ⋮ Unnamed Item ⋮ 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 ⋮ Unnamed Item ⋮ Almost optimal distribution-free junta testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Unnamed Item ⋮ On the decision tree complexity of threshold functions ⋮ Unnamed Item ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities
