SAS

Abstract

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.