Skip to content



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

Riis, S (Queen Mary, University of London)
Wednesday 09 May 2012, 14:00-15:00

Seminar Room 1, Newton Institute


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.


[pdf ] [ppt ]


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.

Back to top ∧