Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 25, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Anders Martinsson
In 1960, Shapiro and Fine asked how many weighings on an exact scale is needed to find all counterfeits out of n coins, assuming real and fake coins have distinct weights. In the following decade, multiple strategies were discovered to solve this problem optimally up to constant factors. Generalized Mastermind was proposed by Chvátal in 1983 as an extension of this problem. The problem of determining the optimal strategy for this game remained open until recently in joint work with Pascal Su. In this talk I will present new research on a framework to approach general information theoretic games over the integers. Our main result states that any such game has a "fast" solution if it can be reduced in a certain sense to a sum of smaller copies of itself. This can be seen as analogous to the master theorem for divide-and-conquer recurrences. As a consequence, we are able to give new concise proofs for existence of fast solutions to coin-weighing and Mastermind by identifying the corresponding reductions.
Automatic MiSe System Software Version 1.4803M | admin login