marina@ai.toronto.edu (Marina Haloulos) (12/21/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Thursday 11 January 1990
Dr. Prabhakar Raghavan
IBM Research, Yorktown Heights
"Computing with Unreliable Information"
We consider the problem of computing by _n_o_i_s_y _d_e_c_i_s_i_o_n _t_r_e_e_s: these are
decision trees in which each node gives the wrong answer with some
probability <1/2.
For boolean decision trees, we give tight results on the depth of noisy
decision trees for computing various threshold functions, and for parity.
These results exhibit a somewhat surprising variation in noisy tree depth
for problems that have the same decision tree depth in the absence of
noise.
For comparison problems, we give tight bounds for sorting, selection and
related problems. We will describe what our algorithms have to do with
the NBA tournament and with Chess championships.
Joint work with Uri Feige, David Peleg and Eli Upfal.