Approximating the distance to monotonicity of Boolean functions
From MaRDI portal
Publication:6074683
DOI10.1002/rsa.21029zbMath1522.68749arXiv1911.06924OpenAlexW3176051744MaRDI QIDQ6074683
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.06924
property testingsublinear algorithmsanalysis of Boolean functionstolerant and erasure-resilient testing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monotonicity testing and shortest-path routing on the cube
- Testing juntas
- Property testing lower bounds via communication complexity
- Information theory in property testing and monotonicity testing in higher dimension
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- On the strength of comparisons in property testing
- A lower bound for testing juntas
- Tolerant property testing and distance approximation
- An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
- Local Reconstructors and Tolerant Testers for Connectivity and Diameter
- Approximating the distance to monotonicity in high dimensions
- Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
- Property testing and its connection to learning and approximation
- Testing monotonicity over graph products
- Improved Bounds for Testing Juntas
- Monotonicity testing over general poset domains
- Tolerant Linearity Testing and Locally Testable Codes
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Tolerant testers of image properties
- Erasure-Resilient Property Testing
- Settling the Query Complexity of Non-adaptive Junta Testing
- An ~O(n) Queries Adaptive Tester for Unateness
- Robust Characterizations of Polynomials with Applications to Program Testing
- Transitive-Closure Spanners
- Property Testing on Product Distributions
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Parameterized Property Testing of Functions
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- A Note on Tolerant Testing with One-Sided Error
- Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
- Approximating the Distance to Monotonicity of Boolean Functions
- Testing juntas nearly optimally
- An improved constant-time approximation algorithm for maximum~matchings
- Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
- Testing unateness nearly optimally
- L p -testing
- A polynomial lower bound for testing monotonicity
- Testing versus Estimation of Graph Properties
- Estimating the distance to a monotone function
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
- Testing monotonicity
- On disjoint chains of subsets
