Testing Fourier dimensionality and sparsity

DOI10.1137/100785429zbMATH Open1235.94084OpenAlexW2084369441MaRDI QIDQ5894337FDOQ5894337

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

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

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)

Cited In (27)

• A unified framework for testing linear-invariant properties
• Title not available (Why is that?)
• 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
• Testing Fourier Dimensionality and Sparsity
• Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions
• Testing submodularity and other properties of valuation functions
• Title not available (Why is that?)
• 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
• Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace
• The list-decoding size of Fourier-sparse Boolean 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)