The story of superconcentrators – the missing link

Add to your list(s) Download to your calendar using vCal

• Koucky, M (Academy of Sciences of the Czech Republic)
• Wednesday 04 July 2012, 11:00-12:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

This talk has been canceled/deleted

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.