On the complexity of finding a local maximum of functions on discrete planar subsets
type: Item
instance of: scholarly article
title: On the complexity of finding a local maximum of functions on discrete planar subsets
zbMATH Open document ID: 1071.68032
DOI: 10.1016/S0304-3975(03)00426-2
author: Anton Mityagin
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2111062
zbMATH Keywords: Computational complexity
zbMATH Keywords: Decision trees
zbMATH Keywords: Local maximum search
MaRDI profile type: Publication
cites work: Sperner's lemma and robust machines
cites work: Sequential Minimax Search for a Maximum
cites work: Search Problems in the Decision Tree Model
cites work: On the query complexity of finding a local maximum point.
cites work: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
cites work: Discrete Isoperimetric Problems
full work available at URL: s0304-3975(03)00426-2
OpenAlex ID: W2028456923
description: scientific article; zbMATH DE number 2111062