Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant Deterministic and probabilistic binary search in graphs. (English) Zbl 1376.68064 Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 519-532 (2016). Cited in 2 ReviewsCited in 12 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 05C85 Graph algorithms (graph-theoretic aspects) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) Keywords:exponential-time hypothesis; noisy binary search; PSPACE-hardness; quasipolynomial-time algorithms; searching in metric spaces PDFBibTeX XMLCite \textit{E. Emamjomeh-Zadeh} et al., in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 519--532 (2016; Zbl 1376.68064) Full Text: DOI arXiv