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 - Funding Information:
“Part of this work was done while two of the authors, R6nyai, were visiting the University of Chicago. t Department of Computer Science, University IL 60637-1504. E-mail: laci@cs .uchicago. edu $Institute for Advanced Study, Princeton N.J. 0s540. pannimath. ias. edu. – Research 93045s0. $Department of Mathematics, University Utah, Salt Lake City, UT S4112. E-mail: kollsrtiath. utah. edu. – Research in part hy NSF Grants DMS-S707320 and DMS-9102S66. gcomp”ter and Automation Institute, Hungarian Academy Sciences, Budapest, Ligym&nyosi u. 11, Hungary H-1111. mail: lajos~nyest . ilab. sztaki .hu. Research supported by Hungarian National Foundation Scientific Research T016503. IIDepartment of Mathematics, The Ohio State University, bus, ohio 43210. Email: szabote@rnath. ohio-state. edu . “Institute of Computer Science, Hebrew University, Jerusalem, Israel. Currently visiting the Institute for Advanced Study, Princeton, N. J. 0S540 and Princeton University. Research supported by the Sloan Foundation, American-Israeli BSF grant 92-00106, and the Wolfson Research Awards, administered by Israel Academy of Sciences. Email: avi~cs .huji. ac. il
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 -