The query complexity of finding local minima in the lattice
type: Item
instance of: scholarly article
title: The query complexity of finding local minima in the lattice
zbMATH Open document ID: 1005.68079
author: Amos Beimel
author: Felix Geller
author: Eyal Kushilevitz
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q32
zbMATH DE Number: 1853213
MaRDI profile type: Publication
full work available at URL: inco.2001.3065
OpenAlex ID: W2073950383
cites work: Learning regular sets from queries and counterexamples
cites work: Queries and concept learning
cites work: Learning conjunctions of Horn clauses
cites work: Learning read-once formulas with queries
cites work: Malicious omissions and errors in answers to membership queries
cites work: Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle
cites work: Q4228462
cites work: Fast learning of \(k\)-term DNF formulas with queries.
cites work: Exact learning Boolean functions via the monotone theory
cites work: Simple learning algorithms using divide and conquer
cites work: Q4230376
cites work: Asking questions to minimize errors
cites work: On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
cites work: How many queries are needed to learn?
cites work: A simple algorithm for learning O(log n)-term DNF
cites work: Lower bound methods and separation results for on-line learning models
cites work: Q4231923
cites work: Inference of finite automata using homing sequences
cites work: Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$
cites work: Learning sparse multivariate polynomials over a field with queries and counterexamples.
DOI: 10.1006/INCO.2001.3065
Recommended article: On the deterministic complexity of searching local maxima
Recommended article: On the query complexity of finding a local maximum point.
Recommended article: Complexity aspects of local minima and related notions
Recommended article: On the complexity of finding a local minimizer of a quadratic function over a polytope
Recommended article: The local minima in the lattice-simplex covering problem
Recommended article: Q3059322
Recommended article: Q5002725
Recommended article: Local search and the local structure of NP-complete problems
Recommended article: Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
description: scientific article; zbMATH DE number 1853213