Adaptive Lower Bound for Testing Monotonicity on the Line

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.31OpenAlexW2964084133MaRDI QIDQ5009526

Aleksandrs Belovs

Publication date: 4 August 2021

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

zbMATH Keywords

property testingmonotonicity on the hypergridmonotonicity on the line

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

Improved algorithm for permutation testing ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing lower bounds via communication complexity
• Spot-checkers
• On the strength of comparisons in property testing
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Parameterized property testing of functions
• Robust Characterizations of Polynomials with Applications to Program Testing
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• A polynomial lower bound for testing monotonicity
• A o(n) monotonicity tester for boolean functions over the hypercube
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• Testing monotonicity

This page was built for publication: Adaptive Lower Bound for Testing Monotonicity on the Line