NDLI: Testing Fourier Dimensionality and Sparsity

Please wait, while we are loading the content...

Testing Fourier Dimensionality and Sparsity

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Gopalan, Parikshit Shpilka, Amir O'Donnell, Ryan Wimmer, Karl Servedio, Rocco A.
Copyright Year	2011
Abstract	We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable. We give the first efficient algorithms for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients) and for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing that any testing algorithmeven an adaptive onemust have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Building on these results, we give an implicit learning algorithm that lets us test any subproperty of Fourier concision. We also present some applications of these results to exact learning and decoding. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from [V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 563576].
Starting Page	1075
Ending Page	1100
Page Count	26
File Format	PDF
ISSN	00975397
DOI	10.1137/100785429
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	40
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2011-07-19
Access Restriction	Subscribed
Subject Keyword	Fourier series in special orthogonal functions Boolean functions Switching theory, application of Boolean algebra; Boolean functions Fourier spectrum discrete Fourier analysis local testability property testing
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Chow Parameters Problem

Testing Fourier dimensionality and sparsity (2009)

An Entropic Proof of Chang's Inequality

Testing Fourier dimensionality and sparsity (2009)

Locally monotone Boolean and pseudo-Boolean functions

Landscape Boolean Functions

Pivotal decompositions of functions

Rayleigh quotients of Dillon's functions

On the resolution of the sensitivity conjecture

Testing Fourier Dimensionality and Sparsity

Similar Documents

The Chow Parameters Problem

Testing Fourier dimensionality and sparsity (2009)

An Entropic Proof of Chang's Inequality

Testing Fourier dimensionality and sparsity (2009)

Locally monotone Boolean and pseudo-Boolean functions

Landscape Boolean Functions

Pivotal decompositions of functions

Rayleigh quotients of Dillon's functions

On the resolution of the sensitivity conjecture

Testing Fourier Dimensionality and Sparsity