The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

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

Abstract

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.

Presentation

[pdf ] [ppt ]

Video

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 ∧