Optimal unateness testers for real-valued functions: Adaptivity helps

DOI10.4230/LIPICS.ICALP.2017.5zbMATH Open1441.68279OpenAlexW2599411700MaRDI QIDQ5111334FDOQ5111334

Authors: Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri 

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1703.05199

Recommendations

• Optimal unateness testers for real-valued functions: adaptivity helps
• Testing unateness nearly optimally
• An \(\widetilde O(n)\) queries adaptive tester for unateness
• Point optimal testing with roots that are functionally local to unity
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• An adaptivity hierarchy theorem for property testing
• An adaptivity hierarchy theorem for property testing
• Testing for a general class of functional inequalities
• Almost Optimal Testers for Concise Representations.
• scientific article; zbMATH DE number 19010

zbMATH Keywords

property testingunate and monotone functions

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational methods for problems pertaining to real functions (26-08)

Cited In (8)

• Title not available (Why is that?)
• Testing piecewise functions
• Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• Title not available (Why is that?)
• Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• The power and limitations of uniform samples in testing properties of figures

This page was built for publication: Optimal unateness testers for real-valued functions: Adaptivity helps

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