∼Daniel Kral 教授演講摘要∼

日期 星期 時間 演講者 單位 演講地點 演講題目
93.12.13 一 11:10-12:00 Daniel Kral Technical University of Berlin, Germany 理4011 Three optimal algorithms for balls of three colors
摘要

We study a game played by two players, Paul and Carol. Carol fixes a coloring of n balls with three colors. Paul cannot see the colors of the balls. At each step, he chooses a pair of balls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. Paul's goal is to minimize the number of questions he asks to reach his goal.

Problems of this type are well-motivated from the communication comlexity and their analysis usually requires neat combinatorial arguments. During the talk, optimal deterministic and probabilistic strategies for the Partition problem and an asymptotically optimal probabilistic strategy for the Plurality problem will be presented.

  • 其它理論科學中心演講: 北區、 新竹、 南區
    •