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
N1 - Publisher Copyright:
© 1996 ACM.
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 -