Testing Fourier Dimensionality and Sparsity
Authors:
- 1 January 2009
- book chapter
- Published by Springer Nature
- p. 500-512
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- Testing juntasJournal of Computer and System Sciences, 2004
- Testing Low-Degree Polynomials over GF(2)2003
- Testing Basic Boolean FormulaeSIAM Journal on Discrete Mathematics, 2002
- Spectral analysis of Boolean functions as a graph eigenvalue problemIEEE Transactions on Computers, 1999
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform DistributionJournal of Computer and System Sciences, 1997
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Learning Decision Trees Using the Fourier SpectrumSIAM Journal on Computing, 1993
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993