Unconditional hardness results and a tricky coin weighing puzzle

13 October 2015
16:30
Raphaël Clifford
Abstract

It has become possible in recent years to provide unconditional lower bounds on the time needed to perform a number of basic computational operations. I will briefly discuss some of the main techniques involved and show how one in particular, the information transfer method, can be exploited to give  time lower bounds for computation on streaming data.

I will then go on to present a simple looking mathematical conjecture with a probabilistic combinatorics flavour that derives from this work.  The conjecture is related to the classic "coin weighing with a spring scale" puzzle but has so far resisted our best efforts at resolution.

  • Combinatorial Theory Seminar