The authors identify a link between agnostic conjunction learning and tolerant junta testing, and use it to improve both algorithms, roughly to 2^{O~(n^{1/3})} time and 2^{O~(k^{1/3})} queries.
Canonne, Talya Eden, Amit Levi, and Dana Ron
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
The authors identify a link between agnostic conjunction learning and tolerant junta testing, and use it to improve both algorithms, roughly to 2^{O~(n^{1/3})} time and 2^{O~(k^{1/3})} queries.