Almost optimal proper learning and testing polynomials
From MaRDI portal
Publication:6109015
DOI10.1007/978-3-031-20624-5_19arXiv2202.03207OpenAlexW4312577457MaRDI QIDQ6109015
Publication date: 26 July 2023
Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.03207
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- On learning multivariate polynomials under the uniform distribution
- Efficiently testing sparse \(\text{GF}(2)\) polynomials
- Property testing lower bounds via communication complexity
- Learning sparse multivariate polynomials over a field with queries and counterexamples.
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Self-testing/correcting with applications to numerical problems
- Queries and concept learning
- On PAC learning algorithms for rich Boolean function classes
- Efficient Sample Extractors for Juntas with Applications
- Applying Coding Theory to Sparse Interpolation
- Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
- A theory of the learnable
- On Learning Ring-Sum-Expansions
- Learning functions represented as multiplicity automata
- Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
- Robust Characterizations of Polynomials with Applications to Program Testing
- A Brief Introduction to Property Testing
- lgorithmic and Analysis Techniques in Property Testing
- On Optimal Learning Algorithms for Multiplicity Automata
- Introduction to Property Testing
- Learning Behaviors of Automata from Multiplicity and Equivalence Queries
This page was built for publication: Almost optimal proper learning and testing polynomials
