Distribution-free property testing

DOI10.1007/B11961MaRDI QIDQ5900942zbMATH OpenOpenAlexFDO

Authors Shirley Halevy, Eyal Kushilevitz

Publication date 26 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b11961

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Distribution-Free Property-Testing
• Distribution-free testing algorithms for monomials with a sublinear number of queries
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Distribution-free testing for monomials with a sublinear number of queries
• Distribution-free testing lower bound for basic Boolean functions

Cited in

(21)

• Fast approximate PCPs for multidimensional bin-packing problems
• Tolerant property testing and distance approximation
• On multiple input problems in property testing
• Distribution-free testing lower bound for basic Boolean functions
• On the average-case complexity of property testing
• Distribution-Free Property-Testing
• Distribution-free testing algorithms for monomials with a sublinear number of queries
• Distribution-Free Testing Lower Bounds for Basic Boolean Functions
• Erasure-Resilient Property Testing
• Property Testing on Product Distributions
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
• Testing convexity properties of tree colorings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
• Relative-error testing of conjunctions and decision lists
• Information theory in property testing and monotonicity testing in higher dimension
• Distribution-free connectivity testing for sparse graphs
• Property-preserving data reconstruction

This page was built for publication: Distribution-free property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900942)