Date
Tue, 13 Oct 2015
16:30
Location
L6
Speaker
Raphaël Clifford
Organisation
University of Bristol

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.

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 14:57.