Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs

László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996
PublisherAssociation for Computing Machinery
Pages603-611
Number of pages9
ISBN (Electronic)0897917855
DOIs
StatePublished - Jul 1 1996
Externally publishedYes
Event28th Annual ACM Symposium on Theory of Computing, STOC 1996 - Philadelphia, United States
Duration: May 22 1996May 24 1996

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129452
ISSN (Print)0737-8017

Other

Other28th Annual ACM Symposium on Theory of Computing, STOC 1996
CountryUnited States
CityPhiladelphia
Period5/22/965/24/96

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs'. Together they form a unique fingerprint.

  • Cite this

    Babai, L., Gál, A., Kollár, J., Rónyai, L., Szabó, T., & Wigderson, A. (1996). Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996 (pp. 603-611). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129452). Association for Computing Machinery. https://doi.org/10.1145/237814.238010