Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

2024/04/17 by Chen, Xi, Fei, Yumou, Patel, Shyamal · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2404.11103

Abstract

We give a distribution-free testing algorithm for decision lists with O(n^11/12/ε³) queries. This is the first sublinear algorithm for this problem, which shows that, unlike halfspaces, testing is strictly easier than learning for decision lists. Complementing the algorithm, we show that any distribution-free tester for decision lists must make Ω(√(n)) queries, or draw Ω(n) samples when the algorithm is sample-based.

Cited by

• Halfspaces are hard to test with relative error

Related

• On Learning and Testing Decision Tree
• Distribution-free Junta Testing
• Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
• Interactive Proofs For Distribution Testing With Conditional Oracles
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing