Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.38zbMath1467.68210arXiv1706.05556OpenAlexW2963396042MaRDI QIDQ5002641

Xi Chen, Li-Yang Tan, Erik Waingarten, Rocco A. Servedio

Publication date: 28 July 2021

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

zbMATH Keywords

monotonicityadaptivityproperty testinglinear threshold functions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20)

Related Items (1)

A Polynomial Lower Bound for Testing Monotonicity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• Property testing lower bounds via communication complexity
• Spot-checkers
• On the strength of comparisons in property testing
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
• Testing Halfspaces
• Testing monotonicity over graph products
• Monotonicity testing over general poset domains
• Sublinear algorithms for testing monotone and unimodal distributions
• Testing monotone high‐dimensional distributions
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Testing Probability Distributions using Conditional Samples
• L _p -testing
• A polynomial lower bound for testing monotonicity
• Estimating the distance to a monotone function
• 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: Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces