Adaptive lower bound for testing monotonicity on the line

DOI10.4230/LIPICS.APPROX-RANDOM.2018.31MaRDI QIDQ5009526zbMATH OpenOpenAlexFDO

Authors Aleksandrs Belovs

Publication date 4 August 2021

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

zbMATH Keywords

monotonicity on the hypergridmonotonicity on the lineproperty testing

Mathematics Subject Classification ID

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

Recommendations

• An optimal lower bound for monotonicity testing over hypergrids
• scientific article; zbMATH DE number 6395191
• A polynomial lower bound for testing monotonicity
• A polynomial lower bound for testing monotonicity
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries

Cites work

• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• A polynomial lower bound for testing monotonicity
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• scientific article; zbMATH DE number 6538684 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Monotonicity testing over general poset domains
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• On the strength of comparisons in property testing
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Parameterized property testing of functions
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Testing monotonicity

Cited in

(13)

• On the strength of comparisons in property testing
• An optimal lower bound for monotonicity testing over hypergrids
• Monotonicity checking
• Monotonicity testing and shortest-path routing on the cube
• Testing local properties of arrays
• A polynomial lower bound for testing monotonicity
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Improved algorithm for permutation testing
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Property testing with online adversaries
• Property testing with online adversaries
• New sublinear algorithms and lower bounds for LIS estimation

This page was built for publication: Adaptive lower bound for testing monotonicity on the line

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