New algorithms and lower bounds for monotonicity testing

DOI10.1109/FOCS.2014.38MaRDI QIDQ6947233zbMATH OpenFDO

Authors Li-Yang Tan, Rocco A. Servedio, Xi Chen

Publication date 5 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2014.38

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(4)

• Testing intersecting and union-closed families
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Relative-error testing of conjunctions and decision lists

This page was built for publication: New algorithms and lower bounds for monotonicity testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6947233)