marina@ai.toronto.edu (Marina Haloulos) (01/13/90)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Thursday 25 January 1990
Professor Silvio Micali
MIT, Laboratory for Computer Science
"Card Games are Universal"
We show that card games are not just examples of games with partial
information, but they are _c_o_m_p_l_e_t_e for this class. Namely,
_E_v_e_r_y _g_a_m_e _w_i_t_h _p_a_r_t_i_a_l _i_n_f_o_r_m_a_t_i_o_n _c_a_n _b_e _e_n_c_o_d_e_d _a_n_d _p_l_a_y_e_d _b_y
_s_h_u_f_f_l_i_n_g _a _r_e_g_u_l_a_r _d_e_c_k _o_f _c_a_r_d_s.
Joint work with Joe Kilian.