The query complexity of finding local minima in the lattice
DOI10.1006/INCO.2001.3065zbMATH Open1005.68079OpenAlexW2073950383MaRDI QIDQ1854471FDOQ1854471
Authors: Amos Beimel, Felix Geller, Eyal Kushilevitz 
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
Recommendations
- On the deterministic complexity of searching local maxima
- On the query complexity of finding a local maximum point.
- Complexity aspects of local minima and related notions
- On the complexity of finding a local minimizer of a quadratic function over a polytope
- The local minima in the lattice-simplex covering problem
- Local search: complexity and approximation
- On the probe complexity of local computation algorithms
- Local search and the local structure of NP-complete problems
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Hardness of continuous local search: query complexity and cryptographic lower bounds
Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Learning regular sets from queries and counterexamples
- Learning conjunctions of Horn clauses
- Queries and concept learning
- Learning read-once formulas with queries
- Title not available (Why is that?)
- Exact learning Boolean functions via the monotone theory
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
- Learning sparse multivariate polynomials over a field with queries and counterexamples.
- Fast learning of \(k\)-term DNF formulas with queries.
- Inference of finite automata using homing sequences
- How many queries are needed to learn?
- Asking questions to minimize errors
- A simple algorithm for learning O(log n)-term DNF
- Simple learning algorithms using divide and conquer
- Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle
- Lower bound methods and separation results for on-line learning models
- Malicious omissions and errors in answers to membership queries
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (3)
This page was built for publication: The query complexity of finding local minima in the lattice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854471)
