skip to content

The story of superconcentrators – the missing link

Presented by: 
M Koucky Academy of Sciences of the Czech Republic
Wednesday 4th July 2012 - 11:00 to 12:00
INI Seminar Room 1
In 60's and 70's directed graphs with strong connectivity property were linked to proving lower bounds on complexity of solving various computational problems. Graphs with strongest such property were named superconcentrators by Valiant (1975). An n-superconcentrator is a directed acyclic graph with n designated input nodes and n designated output nodes such that for any subset X of input nodes and any equal-sized set Y of output nodes there are |X| vertex disjoint paths connecting the sets. Contrary to previous conjectures Valiant showed that there are n-superconcentrators with O(n) edges thus killing the hope of using them to prove lower bounds on computation. His n-superconcentrators have depth O(log n). Despite this setback, superconcentrators found their way into lower bounds in the setting of bounded-depth circuits. They provide asymptotically optimal bounds for computing many functions including integer addition, and most recently computing good error-correctin g codes. The talk will provide an exposition of this fascinating area.
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