The query complexity of finding local minima in the lattice

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

Mathematics Subject Classification ID

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?

This page was built for publication: The query complexity of finding local minima in the lattice