Mathematics Department

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

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.

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 3Meeting with majors. No talk this week.
Sept 10Probabilistically Checkable Proofs and the PCP Theorem
John 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 17Student Research Papers
Josh Gancher, Alex Ledger; Ricardo Rojas-Echenique; Riley Thornton
Sept 24TBD
Puck Rombach, Department of Mathematics, UCLA
Oct 1TBD
Jesse Walker, Intel
Oct 8TBD
Oct 15TBD
Anurag Singh, Department of Mathematics, University of Utah
Oct 22Fall break
Oct 29TBD
Gireeja Ranade, Microsoft Research
Nov 5TBD
Martina Morris, Department of Sociology and Statistics, University of Washington
Nov 12TBD
Nov 19TBD
Alex Malozemoff, Ph.D. Candidate at the University of Maryland
Nov 26Thanksgiving. No talk this week.
Dec 3TBD
Eugenia 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.