Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.

Lszl Babai, Anna Gl, Jnos Kollr, Lajos Rnyai, Tibor Szab, Avi Wigderson

Browse the full STOC paper archive.