The query complexity of finding local minima in the lattice

DOI10.1006/INCO.2001.3065MaRDI QIDQ1854471zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

Cites work

• scientific article; zbMATH DE number 1256727 (Why is no real title available?)
• scientific article; zbMATH DE number 1256689 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• A simple algorithm for learning O(log n)-term DNF
• Asking questions to minimize errors
• Exact learning Boolean functions via the monotone theory
• Fast learning of \(k\)-term DNF formulas with queries.
• How many queries are needed to learn?
• Inference of finite automata using homing sequences
• Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
• Learning conjunctions of Horn clauses
• Learning read-once formulas with queries
• Learning regular sets from queries and counterexamples
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• Lower bound methods and separation results for on-line learning models
• Malicious omissions and errors in answers to membership queries
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Queries and concept learning
• Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle
• Simple learning algorithms using divide and conquer

Cited in

(3)

• The query complexity of witness finding
• On the query complexity of finding a local maximum point.
• The query complexity of witness finding

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)