Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces (Q5002641): Difference between revisions

@@ label / en / label / en @@
+Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
@@ Property / author @@
+Rocco A. Servedio
@@ Property / author: Rocco A. Servedio / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.05556
@@ Property / arXiv ID: 1706.05556 / rank @@
+Normal rank
@@ Property / cites work @@
+Estimating the distance to a monotone function
@@ Property / cites work: Estimating the distance to a monotone function / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal unateness testers for real-valued functions: Adaptivity helps
+Normal rank
@@ Property / cites work @@
+Sublinear algorithms for testing monotone and unimodal distributions
+Normal rank
@@ Property / cites work @@
+A polynomial lower bound for testing monotonicity
@@ Property / cites work: A polynomial lower bound for testing monotonicity / rank @@
+Normal rank
@@ Property / cites work @@
+L             <sub>p</sub>             -testing
@@ Property / cites work: L <sub>p</sub> -testing / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing lower bounds via communication complexity
+Normal rank
@@ Property / cites work @@
+Monotonicity testing and shortest-path routing on the cube
+Normal rank
@@ Property / cites work @@
+Testing Probability Distributions using Conditional Samples
+Normal rank
@@ Property / cites work @@
+A o(n) monotonicity tester for boolean functions over the hypercube
+Normal rank
@@ Property / cites work @@
+Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
+Normal rank
@@ Property / cites work @@
+Q5497118
@@ Property / cites work: Q5497118 / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
+Normal rank
@@ Property / cites work @@
+Q5111156
@@ Property / cites work: Q5111156 / rank @@
+Normal rank
@@ Property / cites work @@
+Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
+Normal rank
@@ Property / cites work @@
+Q4941829
@@ Property / cites work: Q4941829 / rank @@
+Normal rank
@@ Property / cites work @@
+Spot-checkers
@@ Property / cites work: Spot-checkers / rank @@
+Normal rank
@@ Property / cites work @@
+Q5538132
@@ Property / cites work: Q5538132 / rank @@
+Normal rank
@@ Property / cites work @@
+On the strength of comparisons in property testing
+Normal rank
@@ Property / cites work @@
+Monotonicity testing over general poset domains
@@ Property / cites work: Monotonicity testing over general poset domains / rank @@
+Normal rank
@@ Property / cites work @@
+Testing monotonicity
@@ Property / cites work: Testing monotonicity / rank @@
+Normal rank
@@ Property / cites work @@
+Testing monotonicity over graph products
@@ Property / cites work: Testing monotonicity over graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Testing Halfspaces
@@ Property / cites work: Testing Halfspaces / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
+Normal rank
@@ Property / cites work @@
+Exponentially improved algorithms and lower bounds for testing signed majorities
+Normal rank
@@ Property / cites work @@
+Testing monotone high‐dimensional distributions
@@ Property / cites work: Testing monotone high‐dimensional distributions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4601832
@@ Property / cites work: Q4601832 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2963396042
@@ Property / OpenAlex ID: W2963396042 / rank @@
+Normal rank
@@ Property / title @@
+Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces (English)
+Normal rank