Testing Fourier dimensionality and sparsity

DOI10.1137/100785429MaRDI QIDQ5894337zbMATH OpenOpenAlexFDO

Authors 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

property testingdiscrete Fourier analysisFourier spectrumlocal testability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fault detection; testing in circuits and networks (94C12)

Recommendations

• Testing Fourier Dimensionality and Sparsity
• The list-decoding size of Fourier-sparse Boolean functions
• The list-decoding size of Fourier-sparse Boolean functions
• Fourier sparsity and dimension
• Efficiently Testing Sparse GF(2) Polynomials

Cited in

(27)

• Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace
• The list-decoding size of Fourier-sparse Boolean functions
• A unified framework for testing linear-invariant properties
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Almost optimal distribution-free junta testing
• A generalization of a theorem of Rothschild and van Lint
• Testing Booleanity and the uncertainty principle
• Near-optimal upper bound on Fourier dimension of Boolean functions in terms of Fourier sparsity
• Exponentially improved algorithms and lower bounds for testing signed majorities
• The list-decoding size of Fourier-sparse Boolean functions
• Structure of protocols for XOR functions
• Sampling Boolean functions over Abelian groups and applications
• An improved test of Boolean functions for \(k\)-dimensionality
• On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers
• Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions
• Testing Fourier Dimensionality and Sparsity
• Testing submodularity and other properties of valuation functions
• scientific article; zbMATH DE number 7561509 (Why is no real title available?)
• Fourier sparsity and dimension
• Algebraically degenerate approximations of Boolean functions
• Testing Sparsity-Inducing Penalties
• Testing Properties of Sparse Images
• An optimal tester for \(k\)-Linear
• Almost Optimal Testers for Concise Representations.
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• A generalization of a theorem of Rothschild and van Lint
• On the decision tree complexity of threshold functions

This page was built for publication: Testing Fourier dimensionality and sparsity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5894337)