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

discrete Fourier analysisFourier spectrumlocal testabilityproperty testing

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

(32)

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