Relative-error testing of conjunctions and decision lists
From MaRDI portal
Cites work
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- A polynomial lower bound for testing monotonicity
- A theory of the learnable
- Almost Optimal Testers for Concise Representations.
- An O(n) queries adaptive tester for unateness
- Analysis of Boolean Functions
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Boolean unateness testing with \(\widetilde{O}(n^{3/4})\) adaptive queries
- Computational complexity and property testing. On the interplay between randomness and computation
- Distribution-free property testing
- Distribution-free testing for halfspaces (almost) requires PAC learning
- Distribution-free testing lower bound for basic Boolean functions
- Efficient sample extractors for juntas with applications
- scientific article; zbMATH DE number 7559095 (Why is no real title available?)
- Introduction to Property Testing
- Monotonicity testing over general poset domains
- New algorithms and lower bounds for monotonicity testing
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- Property testing and its connection to learning and approximation
- Property testing. Problems and techniques
- Self-testing/correcting with applications to numerical problems
- Testing Basic Boolean Formulae
- Testing Halfspaces
- Testing monotonicity
- Tight bounds for the distribution-free testing of monotone conjunctions
This page was built for publication: Relative-error testing of conjunctions and decision lists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346488)
