### 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 Ω(n^{5/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 formulae^{1}.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996 |

Publisher | Association for Computing Machinery |

Pages | 603-611 |

Number of pages | 9 |

ISBN (Electronic) | 0897917855 |

DOIs | |

State | Published - Jul 1 1996 |

Externally published | Yes |

Event | 28th Annual ACM Symposium on Theory of Computing, STOC 1996 - Philadelphia, United States Duration: May 22 1996 → May 24 1996 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F129452 |

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Philadelphia |

Period | 5/22/96 → 5/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

*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