Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, November 25, 2021, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Anders Martinsson

Additive query games

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login