skip to content

Valiants Shift problem: A reduction to a problem about graph guessing games

Wednesday 9th May 2012 - 14:00 to 15:00
INI Seminar Room 1
The talk will survey a number of results that were partly developed during my visit at the Newton Institute. I will show that Valiant's Shift problem/conjecture - which has been open for more than 30 years - naturally reduce to questions about guessing games. In the talk I will also provide a new perspective on information bottlenecks in Boolean Circuits/Communication Networks.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons