Buchumschlag

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Nadimpalli, Shivam, Patel, Shyamal
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

DNF Learning via Locally Mixing Random Walks
von: Alman, Josh, et al.
Veröffentlicht: (2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Faster exact learning of k-term DNFs with membership and equivalence queries
von: Alman, Josh, et al.
Veröffentlicht: (2025)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Learning and Testing Convex Functions
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Testing Convex Truncation
von: De, Anindya, et al.
Veröffentlicht: (2023)

Testing noisy low-degree polynomials for sparsity
von: Bao, Yiqiao, et al.
Veröffentlicht: (2025)

Testing Sumsets is Hard
von: Chen, Xi, et al.
Veröffentlicht: (2024)

A Simple Algorithm for Dynamic Carpooling with Recourse
von: Efron, Yuval, et al.
Veröffentlicht: (2024)

Tight Bounds for Learning Polyhedra with a Margin
von: Patel, Shyamal, et al.
Veröffentlicht: (2026)

Detecting Low-Degree Truncation
von: De, Anindya, et al.
Veröffentlicht: (2024)

Fault-Tolerant Bounded Flow Preservers
von: Bansal, Shivam, et al.
Veröffentlicht: (2024)

Learning Functions of Halfspaces
von: Alman, Josh, et al.
Veröffentlicht: (2026)

Tolerant Testing for Unique Games
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Testing Juntas and Junta Subclasses with Relative Error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2023)

Nearly Optimal Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
von: Kosinas, Evangelos
Veröffentlicht: (2025)

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Halfspaces are hard to test with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
von: Parter, Merav, et al.
Veröffentlicht: (2025)

Near Optimal Dual Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2025)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
von: Klivans, Adam R., et al.
Veröffentlicht: (2026)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
von: Wang, Hanzhi
Veröffentlicht: (2024)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
von: Udwani, Rajan
Veröffentlicht: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2026)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Sparsifying Suprema of Gaussian Processes
von: De, Anindya, et al.
Veröffentlicht: (2024)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Testing with Non-identically Distributed Samples
von: Garg, Shivam, et al.
Veröffentlicht: (2023)

Equivalence Testing: The Power of Bounded Adaptivity
von: Chakraborty, Diptarka, et al.
Veröffentlicht: (2024)

Optimal Non-Oblivious Open Addressing
von: Bender, Michael A., et al.
Veröffentlicht: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
von: Navarro, Gonzalo
Veröffentlicht: (2024)

Distribution Testing Meets Sum Estimation
von: Pradhan, Pinki, et al.
Veröffentlicht: (2025)

Model-agnostic super-resolution in high dimensions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Optimal Testing of Reed-Muller Codes with an Online Adversary
von: Kelman, Esty, et al.
Veröffentlicht: (2026)