Research map / Learning theory and algorithms / Sample complexity

Distribution Free Fourier Sparsity Testing

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning under log-concave distributions

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies distribution-free property testing of Fourier sparsity for Boolean functions f: F_2^n -> R, where the tester must work under an unknown input distribution rather than uniform.

Problem

Testing whether a function f: F_2^n -> R is s-Fourier-sparse, given query access, under arbitrary (distribution-free) input distributions; prior Fourier sparsity testing largely assumed the uniform distribution.

Approach

Extends Fourier sparsity property testing from the uniform-distribution setting to the distribution-free setting, where the tester has only sample access to the unknown distribution and query access to the function. Full technical details are unavailable beyond the abstract.

Experimental setup

Builds on: uniform-distribution Fourier sparsity testing

Closest papers by meaning

• Price of Parsimony: Complexity of Fourier Sparsity Testing (NeurIPS 2025 · similarity 0.92)
• Implicit Sensing for Fourier Sparse Boolean Functions (ICLR 2026 · similarity 0.91)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases (AAAI 2021 · similarity 0.88)
• Efficiently Learning Significant Fourier Feature Pairs for Statistical Independence Testing (NeurIPS 2024 · similarity 0.86)
• The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.83)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.83)