Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Price of Parsimony: Complexity of Fourier Sparsity Testing
Authors: Arijit Ghosh, Manmatha Roy
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution in this paper is the design of a simple, nonadaptive and almost optimal query algorithm for testing Fourier sparsity. Theorem 1.2. ... We also show that the query complexity of our algorithm is tight up to logarithmic factors by proving a matching lower bound. Theorem 1.3. ... No experimental results were included in the paper; hence, this question is not applicable. ... Our work does not involve data collection or code execution; hence, this question is not applicable. ... No experimental setup was used in this work; therefore, this item is not applicable. ... As no experiments were conducted, questions of statistical significance or error bars do not arise. ... This work does not involve any experiments requiring computational resources; thus, the question is not applicable. |
| Researcher Affiliation | Academia | Arijit Ghosh EMAIL Indian Statistical Institute, Kolkata, India Manmatha Roy EMAIL Indian Statistical Institute, Kolkata, India |
| Pseudocode | Yes | Algorithm 1: FOURIER-SPARSITY-TESTER Input: Tolerance parameter δ 0, proximity parameter ϵ > 0, sparsity parameter s, and oracle access to a function f : Fn 2 R satisfying ||f||2 = 1 Output: YES if dist2 2 (f, Fs) δ, and NO if dist2 2 (f, Fs) δ + ϵ 1: Choose a random affine subspace A = α + H Fn 2, with dim(H) = Θ log s2/ϵ2 2: Let f A denote the restriction of f to A, and compute an estimate eµ of the sum of squares of top s Fourier coefficients of f A in terms of their absolute values 3: If eµ 1 (δ + ϵ/2) then YES, else NO. |
| Open Source Code | No | Our work does not involve data collection or code execution; hence, this question is not applicable. |
| Open Datasets | No | Our work does not involve data collection or code execution; hence, this question is not applicable. |
| Dataset Splits | No | No experimental setup was used in this work; therefore, this item is not applicable. |
| Hardware Specification | No | This work does not involve any experiments requiring computational resources; thus, the question is not applicable. |
| Software Dependencies | No | Our work does not involve data collection or code execution; hence, this question is not applicable. |
| Experiment Setup | No | No experimental setup was used in this work; therefore, this item is not applicable. |