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

Date and Time: Tuesday, May 05, 2020, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Anders Martinsson

Matroid-restricted coin-weighing

Coin-weighing with a spring scale is a classical problem in information theory. In this problem, we are tasked with determining which among a collection of n coins are counterfeit by weighing subsets of coins. For each weighing, we get told how many coins in the chosen subset are counterfeit. A simple entropy argument shows that at least n/log(n+1) weighings are necessary to recover counterfeit coins, and various strategies are known to achieve this up to a constant factor. Motivated by recent advancements on Mastermind, we here consider a restricted version of coin-weighing, where only certain subsets of coins are permitted to be measured. We show that it is possible to achieve the analogous entropy lower bound up to a constant factor whenever the permissible sets form a matroid.

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

Previous talks by year:   2024  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