## Colloquium

#### Upcoming Seminar

September 10,
4:10 PM
in
Physics 123*Probabilistically Checkable Proofs and the PCP Theorem*

John Wilmes '10, Ph.D. candidate, Department of Mathematics, University of Chicago

Most Thursday afternoons during the academic year, the Reed College Department of Mathematics hosts a math talk. The talks are directed to our mathematics majors but are usually accessible on a variety of levels. Refreshments are served before the talks.

### 2015-16 Schedule

#### Fall

**4:10-5:00** in **Physics 123** (unless marked otherwise). Directions to Reed.

Sept 3 | Meeting with majors. No talk this week. |
---|---|

Sept 10 | Probabilistically Checkable Proofs and the PCP TheoremJohn Wilmes '10, Ph.D. candidate, Department of Mathematics, University of Chicago The mathematical proofs one usually encounters are fragile: a single error anywhere can render them invalid. Checking the correctness of such a proof requires careful reading of every line. However, this fragility is not a necessary feature of proofs in general. One of the most surprising advances in theoretical computer science is the construction of Probabilistically Checkable Proofs (PCPs), proofs whose correctness can be guaranteed with arbitrarily high confidence by spot-checking a few random locations. In fact, the PCP Theorem says, loosely, that any reasonable proof can be rewritten as a reasonably-sized PCP. In this talk, I'll discuss how to formalize the notion of a proof, give a precise statement of the PCP Theorem, and explain some elements of its proof. |

Sept 17 | Student Research PapersJosh Gancher, Alex Ledger; Ricardo Rojas-Echenique; Riley Thornton |

Sept 24 | TBDPuck Rombach, Department of Mathematics, UCLA |

Oct 1 | TBDJesse Walker, Intel |

Oct 8 | TBD |

Oct 15 | TBDAnurag Singh, Department of Mathematics, University of Utah |

Oct 22 | Fall break |

Oct 29 | TBDGireeja Ranade, Microsoft Research |

Nov 5 | TBDMartina Morris, Department of Sociology and Statistics, University of Washington |

Nov 12 | TBD |

Nov 19 | TBDAlex Malozemoff, Ph.D. Candidate at the University of Maryland |

Nov 26 | Thanksgiving. No talk this week. |

Dec 3 | TBDEugenia Cheng, School of Mathematics and Statistics, University of Sheffield |

#### Spring

**4:10-5:00** in **Eliot 314** (unless marked otherwise). Directions to Reed.

*Seminar schedule coming soon.*