Delayed Binary Search, or Playing Twenty Questions with a Procrastinator |
| |
Authors: | Ambainis Bloch Schweizer |
| |
Affiliation: | Computer Science Division, University of California, Berkeley, CA 94720, USA. ambainis@cs.berkeley.edu., US Department of Mathematics and Computer Science, Adelphi University, Garden City, NY 11530, USA. sbloch@adelphi.edu., US Barclays Global Investors, 45 Fremont Street, San Francisco, CA 94105, USA. dls@aya.yale.edu., US
|
| |
Abstract: | We study the classic binary search problem, with a delay between query and answer. For all constant delays, we give matching upper and lower bounds on the number of queries. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|