Erasure-Resilient Property Testing
From MaRDI portal
Publication:4608990
DOI10.1137/16M1075661zbMath1390.68757arXiv1607.05786OpenAlexW2963601640MaRDI QIDQ4608990
Kashyap Dixit, Nithin Varma, Abhradeep Thakurta, Sofya Raskhodnikova
Publication date: 29 March 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.05786
Related Items
Erasures versus errors in local decoding and property testing ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Testing Lipschitz functions on hypergrid domains
- Monotonicity testing and shortest-path routing on the cube
- Property testing lower bounds via communication complexity
- Information theory in property testing and monotonicity testing in higher dimension
- On growing random binary trees
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- On the strength of comparisons in property testing
- Tolerant property testing and distance approximation
- Two-sided error proximity oblivious testing
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- Approximating the distance to monotonicity in high dimensions
- On Sample-Based Testers
- On Proximity-Oblivious Testing
- Testing Convexity of Figures Under the Uniform Distribution
- Property testing and its connection to learning and approximation
- The height of a random binary search tree
- An analytic approach to the height of binary search trees II
- Testing monotonicity over graph products
- Monotonicity testing over general poset domains
- A note on the height of binary search trees
- On Testing Convexity and Submodularity
- Tolerant testers of image properties
- Erasure-resilient property testing
- The Power and Limitations of Uniform Samples in Testing Properties of Figures
- Robust Characterizations of Polynomials with Applications to Program Testing
- Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
- Transitive-Closure Spanners
- Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
- Testing Closeness of Discrete Distributions
- Estimating the distance to a monotone function
- Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
- Some 3CNF Properties Are Hard to Test
- Estimating the Longest Increasing Sequence in Polylogarithmic Time
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Proximity Oblivious Testing and the Role of Invariances
- Testing problems with sublearning sample complexity
- Testing monotonicity
- On disjoint chains of subsets
