Almost Optimal Testers for Concise Representations.
From MaRDI portal
Publication:6084348
DOI10.4230/lipics.approx/random.2020.5arXiv1904.09958OpenAlexW2990634459MaRDI QIDQ6084348
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/1904.09958
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficiently testing sparse \(\text{GF}(2)\) polynomials
- Property testing. Current research and surveys
- Learning regular sets from queries and counterexamples
- Selection of relevant features and examples in machine learning
- Self-testing/correcting with applications to numerical problems
- Adaptive versus nonadaptive attribute-efficient learning
- Exact learning of juntas from membership queries
- Learning functions of \(k\) relevant variables
- Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
- Efficient Sample Extractors for Juntas with Applications
- Testing Halfspaces
- Property testing and its connection to learning and approximation
- Tight Bounds for Testing k-Linearity
- Distribution-Free Property-Testing
- Testing Reed–Muller Codes
- Testing ±1-weight halfspace
- A theory of the learnable
- Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions
- Distribution-free Junta Testing
- An ~O(n) Queries Adaptive Tester for Unateness
- Testing Basic Boolean Formulae
- Robust Characterizations of Polynomials with Applications to Program Testing
- Optimal Testing of Reed-Muller Codes
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Testing juntas nearly optimally
- lgorithmic and Analysis Techniques in Property Testing
- A polynomial lower bound for testing monotonicity
- Introduction to Property Testing
- A o(n) monotonicity tester for boolean functions over the hypercube
- Testing Fourier Dimensionality and Sparsity
- Testing monotonicity
This page was built for publication: Almost Optimal Testers for Concise Representations.
