IC Colloquium : Lazy verification of proofs and hard problems
Event details
| Date | 15.10.2012 |
| Hour | 16:15 › 17:30 |
| Speaker | Johan Håstad, KTH Royal Institute of Technology |
| Location | |
| Category | Conferences - Seminars |
Abstract
Verifying a proof is often a tedious task requiring the verifier to read the entire proof and check each step. In this talk we discuss Probabilistically Checkable Proofs (PCPs) which can be verified by random spot-checks looking at very small parts of the proof, rejecting any proof of an incorrect statement with good probability.
In some situations it is possible to only read three (or even sometimes two) bits of the proof and still only be fooled to accept a proof for an incorrect statement with probability about one half. The purpose of the talk is to give a high level discussion of the existence of such proofs. These results turn out to have surprising implications for the approximability of some NP-hard optimization problems and some of these implications will also be described.
Biography
Professor Johan Håstad is the director of the Theory group in the School of Computer Science and Communication at the KTH Royal Institute of Technology. He is a member of the Royal Swedish Academy of Science. He received his BS in Mathematics at Stockholm University, and his MS in Mathematics at Uppsala University. A graduate of the Massachusetts Institute of Technology with a Ph.D. in Mathematics, he won the ACM Doctoral Dissertation Award in 1986, the Gödel prize for "Håstad's switching lemma" in 1994, and his second Gödel prize for his groundbreaking work on inapproximability results in 2011.
Verifying a proof is often a tedious task requiring the verifier to read the entire proof and check each step. In this talk we discuss Probabilistically Checkable Proofs (PCPs) which can be verified by random spot-checks looking at very small parts of the proof, rejecting any proof of an incorrect statement with good probability.
In some situations it is possible to only read three (or even sometimes two) bits of the proof and still only be fooled to accept a proof for an incorrect statement with probability about one half. The purpose of the talk is to give a high level discussion of the existence of such proofs. These results turn out to have surprising implications for the approximability of some NP-hard optimization problems and some of these implications will also be described.
Biography
Professor Johan Håstad is the director of the Theory group in the School of Computer Science and Communication at the KTH Royal Institute of Technology. He is a member of the Royal Swedish Academy of Science. He received his BS in Mathematics at Stockholm University, and his MS in Mathematics at Uppsala University. A graduate of the Massachusetts Institute of Technology with a Ph.D. in Mathematics, he won the ACM Doctoral Dissertation Award in 1986, the Gödel prize for "Håstad's switching lemma" in 1994, and his second Gödel prize for his groundbreaking work on inapproximability results in 2011.
Links
Practical information
- Informed public
- Free
- This event is internal
Organizer
- Host : Prof. Ola Svensson
Contact
- Christine Moscioni or Simone Muller