## Abstract

The existence of extremal combinatorial objects, such as Ramsey graphs and expanders, is often shown using the probabilistic method. It is folklore that pseudo-random generators can be used to obtain explicit constructions of these objects, if the test that the object is extremal can be implemented in polynomial time. In this talk, we pose several questions geared towards initiating a structural approach to the relationship between extremal combinatorics and computational complexity. One motivation for such an approach is to understand better why circuit lower bounds are hard. Another is to formalize connections between the two areas, so that progress in one leads automatically to progress in the other.

Original language | English |
---|---|

Title of host publication | PROGRAMS, PROOFS, PROCESSES |

Editors | F Ferreira, B Lowe, E Mayordomo, LM Gomes |

Place of Publication | BERLIN |

Publisher | Springer-Verlag GmbH |

Pages | 372-375 |

Number of pages | 4 |

ISBN (Print) | 978-3-642-13961-1 |

Publication status | Published - 2010 |

Event | 6th Conference on Computability in Europe (CiE 2010) - Ponta Delgada Duration: 30 Jun 2010 → 4 Jul 2010 |

### Conference

Conference | 6th Conference on Computability in Europe (CiE 2010) |
---|---|

City | Ponta Delgada |

Period | 30/06/10 → 4/07/10 |