Sharp Bounds for Generalized Uniformity Testing
Authors: Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We establish tight bounds on the sample complexity of generalized uniformity testing. In more detail, we present a computationally efficient tester whose sample complexity is optimal, within constant factors, and a matching worst-case information-theoretic lower bound. Specifically, we show that the sample complexity of generalized uniformity testing is Θ 1/(ϵ4/3 p 3) + 1/(ϵ2 p 2) . |
| Researcher Affiliation | Academia | Ilias Diakonikolas University of Southern California diakonik@usc.edu Daniel M. Kane University of California, San Diego dakane@ucsd.edu Alistair Stewart University of Southern California stewart.al@gmail.com |
| Pseudocode | Yes | Algorithm 1 Algorithm for Rough Moment Estimation, Algorithm 2 Algorithm for Moment Estimation, Algorithm 3 Algorithm for Large ϵ, Algorithm 4 Algorithm for Small Epsilon, Algorithm 5 The Full Tester |
| Open Source Code | No | The paper focuses on theoretical bounds and algorithms; no statement about providing open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper presenting algorithms and proofs; it does not use empirical datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical data splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental procedures that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not provide details on software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not detail an experimental setup, hyperparameters, or training configurations. |