Date: thursday, 29.11.2012, 15:30
Speaker: prof. Johan Håstad
Title: Lazy verification of proofs and hard problems
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.
Video
Program
| 29.11.2012 r. | |
| 10:00 | Laying flowers under the cryptologists' memorial plate in Collegium Minus |
| 15:00 | Meeting at the faculty profesors' club |
| 15:30 | Johan Håstad Lazy verification of proofs and hard problems Hall A of Faculty of Mathematics and Computer Science |
Speaker
Johan Hastad is a distinguished Swedish theoretical computer scientist most known for his work on computational complexity theory. He is a professor in theoretical computer science at the Royal Institute of Technology in Stockholm, Sweden since 1992. He is also, among others: a member of the Royal Swedish Academy of Sciences (since 2001), member of the board of the school of Computer Science and Communication at KTH (2005-2011), vice director of SSF-center Center for Industrial and Applied Mathematics, CIAM (since 2006), member of the Nevanlinna Prize Committee, ICM (2006), chairman of the board of Stockholm Mathmatics Center (since 2009). Despite a theoretical character of his work, he is also a coauthor of a patent related to electronic transactions. Johan Hastad has also been a programme committee member of the most prestigious conferences on theoretical computer science and cryptology: Eurocrypt 1989, SWAT 1990, STACS 1991, STOC 1992, ICALP 1993, FOCS 1994, ESA 1996, CRYPTO 1998, Approx 1998, ICALP 2002, CRYPTO 2002, STOC 2003, Computational Complexity 2003, FOCS 2004, Eurocrypt 2005, Random 2005, Theory of Cryptography Conference 2006, ICALP 2006, Approx 2006, SWAT 2008, ESA 2008, Computational Complexity 2009 (chair), Theory of Cryptography Conference 2010, Crypto 2010, ITCS 2012. Editor in journals such as: Computational Complexity (since 1991); Theory of Computing (since 2004); Random Structures and Algorithms (since 2008); ACM Transactions on Computation Theory (since 2008); Information Processing Letter (1990-1993); SIAM Journal on Computing (1991-1999) and Journal of the ACM (1997-2003). He is also a member of the scientific board of Electronic Colloquium on Computational Complexity.
Johan Hastad has twice been a recipient of the most prestigious reward in theoretical computer science - the Gödel Prize (1994 and 2011). His other distinctions include: the ACM Doctoral Dissertation Award (1986), Chester Carlson’s research prize (1990), Göran Gustafsson prize in mathematics (1999). Johan Hastad has also been an invited speaker at the ICM, Berlin, 1998, and a plenary speaker at the ECM, Stockholm, 2004. In 2008 Johan Hastad has obtained a prestigious ERC grant for best scientists in Europe (over 2 million Euro) for reasearch in 2009-2013.
