TY - GEN

T1 - Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs

AU - Babai, László

AU - Gál, Anna

AU - Kollár, János

AU - Rónyai, Lajos

AU - Szabó, Tibor

AU - Wigderson, Avi

PY - 1996/7/1

Y1 - 1996/7/1

N2 - This paper contains two main results. The first is an explicit construction of bipartite graphs which do not contain certain complete bipartite subgraphs and have maximal density, up to a constant factor, under this constraint. This construction represents the first significant progress in three decades on this old problem in extremal graph theory. The construction beats the previously known probabilistic lower bound on density. The proof uses the elements of commutative algebra and algebraic geometry (theory of ideals, integral extensions, valuation rings). The second result concerns monotone span programs. We obtain the first superpolynomial lower bounds for explicit functions in this model. The best previous lower bound was Ω(n5/2) by Beimel, Gal, Paterson (FOCS'95); our analysis exploits a general combinatorial lower bound criterion from that paper. We give two proofs of superpolynomial lower bounds; one based on the construction in the first part, the other based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. A third result demonstrates the power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae1.

AB - This paper contains two main results. The first is an explicit construction of bipartite graphs which do not contain certain complete bipartite subgraphs and have maximal density, up to a constant factor, under this constraint. This construction represents the first significant progress in three decades on this old problem in extremal graph theory. The construction beats the previously known probabilistic lower bound on density. The proof uses the elements of commutative algebra and algebraic geometry (theory of ideals, integral extensions, valuation rings). The second result concerns monotone span programs. We obtain the first superpolynomial lower bounds for explicit functions in this model. The best previous lower bound was Ω(n5/2) by Beimel, Gal, Paterson (FOCS'95); our analysis exploits a general combinatorial lower bound criterion from that paper. We give two proofs of superpolynomial lower bounds; one based on the construction in the first part, the other based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. A third result demonstrates the power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae1.

UR - http://www.scopus.com/inward/record.url?scp=0029711425&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029711425&partnerID=8YFLogxK

U2 - 10.1145/237814.238010

DO - 10.1145/237814.238010

M3 - Conference contribution

AN - SCOPUS:0029711425

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 603

EP - 611

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

T2 - 28th Annual ACM Symposium on Theory of Computing, STOC 1996

Y2 - 22 May 1996 through 24 May 1996

ER -