The query complexity of finding local minima in the lattice
From MaRDI portal
Publication:1854471
DOI10.1006/inco.2001.3065zbMath1005.68079OpenAlexW2073950383MaRDI QIDQ1854471
Amos Beimel, Eyal Kushilevitz, Felix Geller
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2001.3065
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Learning sparse multivariate polynomials over a field with queries and counterexamples.
- Fast learning of \(k\)-term DNF formulas with queries.
- Learning regular sets from queries and counterexamples
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Lower bound methods and separation results for on-line learning models
- Learning conjunctions of Horn clauses
- Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle
- Simple learning algorithms using divide and conquer
- Malicious omissions and errors in answers to membership queries
- A simple algorithm for learning O(log n)-term DNF
- Asking questions to minimize errors
- Queries and concept learning
- Inference of finite automata using homing sequences
- Exact learning Boolean functions via the monotone theory
- Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
- Learning read-once formulas with queries
- How many queries are needed to learn?
