Almost Optimal Distribution-Free Sample-Based Testing of k-Modality

DOI10.4230/lipics.approx/random.2020.27OpenAlexW3082455050MaRDI QIDQ6062150

Dana Ron, Asaf Rosin

Publication date: 31 October 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12630/pdf/LIPIcs-APPROX27.pdf/

zbMATH Keywords

distribution-free property testing\(k\)-modalitysample-based property testing

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• Information theory in property testing and monotonicity testing in higher dimension
• Fast approximate PCPs for multidimensional bin-packing problems
• On the strength of comparisons in property testing
• Tolerant property testing and distance approximation
• An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
• Approximating the distance to monotonicity in high dimensions
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Testing Convexity of Figures Under the Uniform Distribution
• Distribution-Free Property-Testing
• Testing monotonicity over graph products
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• Monotonicity testing over general poset domains
• Sublinear algorithms for testing monotone and unimodal distributions
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Improved Bounds for Testing Forbidden Order Patterns
• An ~O(n) Queries Adaptive Tester for Unateness
• Parameterized property testing of functions
• Transitive-Closure Spanners
• Property Testing on Product Distributions
• On Sample-Based Testers
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
• Approximating the Distance to Monotonicity of Boolean Functions
• Testing unateness nearly optimally
• Testing for forbidden order patterns in an array
• A polynomial lower bound for testing monotonicity
• Estimating the distance to a monotone function
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing problems with sublearning sample complexity
• Testing monotonicity

This page was built for publication: Almost Optimal Distribution-Free Sample-Based Testing of k-Modality