Image de couverture de livre

Testing noisy low-degree polynomials for sparsity

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bao, Yiqiao, De, Anindya, Nadimpalli, Shivam, Servedio, Rocco A., White, Nathan
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Testing Convex Truncation
par: De, Anindya, et autres
Publié: (2023)

Lower Bounds for Convexity Testing
par: Chen, Xi, et autres
Publié: (2024)

Detecting Low-Degree Truncation
par: De, Anindya, et autres
Publié: (2024)

Halfspaces are hard to test with relative error
par: Chen, Xi, et autres
Publié: (2025)

Sublinear-query relative-error testing of halfspaces
par: Chen, Xi, et autres
Publié: (2026)

Sparsifying Suprema of Gaussian Processes
par: De, Anindya, et autres
Publié: (2024)

Testing Sumsets is Hard
par: Chen, Xi, et autres
Publié: (2024)

Model-agnostic super-resolution in high dimensions
par: Chen, Xi, et autres
Publié: (2025)

Relative-error monotonicity testing
par: Chen, Xi, et autres
Publié: (2024)

No Price Tags? No Problem: Query Strategies for Unpriced Information
par: Nadimpalli, Shivam, et autres
Publié: (2025)

Learning Functions of Halfspaces
par: Alman, Josh, et autres
Publié: (2026)

DNF formulas are efficiently testable with relative error
par: Chen, Xi, et autres
Publié: (2026)

Testing Juntas and Junta Subclasses with Relative Error
par: Chen, Xi, et autres
Publié: (2025)

Faster exact learning of k-term DNFs with membership and equivalence queries
par: Alman, Josh, et autres
Publié: (2025)

DNF Learning via Locally Mixing Random Walks
par: Alman, Josh, et autres
Publié: (2025)

Relative-error testing of conjunctions and decision lists
par: Chen, Xi, et autres
Publié: (2025)

Is nasty noise actually harder than malicious noise?
par: Blanc, Guy, et autres
Publié: (2025)

Relative-error unateness testing
par: Chen, Xi, et autres
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Solving convex QPs with structured sparsity under indicator conditions
par: Bienstock, Daniel, et autres
Publié: (2024)

Revisiting Tree Canonization using polynomials
par: Arvind, V., et autres
Publié: (2024)

Downward self-reducibility in the total function polynomial hierarchy
par: Gajulapalli, Karthik, et autres
Publié: (2025)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
par: Nadimpalli, Shivam, et autres
Publié: (2024)

Trace reconstruction from local statistical queries
par: Chen, Xi, et autres
Publié: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
par: Jaffke, Lars, et autres
Publié: (2022)

Constant congestion linkages in polynomially strong digraphs in polynomial time
par: Lopes, Raul, et autres
Publié: (2024)

On Optimal Testing of Linearity
par: Arora, Vipul, et autres
Publié: (2024)

The Trichotomy of Regular Property Testing
par: Bathie, Gabriel, et autres
Publié: (2025)

Computational Complexity in Property Testing
par: Pinto Jr., Renato Ferreira, et autres
Publié: (2025)

Improved Algorithm for Permutation Testing
par: Zhang, Xiaojin
Publié: (2020)

Testing Properties of Edge Distributions
par: Fei, Yumou
Publié: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
par: Li, Qian, et autres
Publié: (2025)

The Structure of In-Place Space-Bounded Computation
par: Cook, James, et autres
Publié: (2025)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
par: Arvind, V., et autres
Publié: (2023)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
par: Abboud, Amir, et autres
Publié: (2026)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
par: Chen, Xi, et autres
Publié: (2025)

A note on approximating the average degree of bounded arboricity graphs
par: Eden, Talya, et autres
Publié: (2026)

Characterizing and Testing Principal Minor Equivalence of Matrices
par: Chatterjee, Abhranil, et autres
Publié: (2024)

A General Framework for Low Soundness Homomorphism Testing
par: Mittal, Tushant, et autres
Publié: (2025)

Low-degree phase transitions for detecting a planted clique in sublinear time
par: Mardia, Jay, et autres
Publié: (2024)