Wykład z informatyki im. Mariana Rejewskiego, Jerzego Różyckiego, Henryka Zygalskiego 2012

Data: czwartek, 29.11.2012, godz. 15:30

Prelegent: prof. Johan Håstad

Tytuł: Lazy verification of proofs and hard problems

Abstrakt: 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.

Wideo

Program

Prelegent

Johan Håstad jest wybitnym szwedzkim profesorem informatyki teoretycznej najbardziej znanym z jego osiągnięć w teorii złożoności obliczeniowej. Od 1992 roku jest profesorem informatyki teoretycznej w Royal Institute of Technology (KTH) w Sztokholmie, Szwecja. Jest także, między innymi: członkiem Królewskiej Szwedzkiej Akademii Nauk (od 2001); członkiem zarządu School of Computer Science and Communication, KTH (2005-2011); wicedyrektorem centrum Center for Industrial and Applied Mathematics, CIAM (od 2006); członkiem Nevanlinna Prize Committee, ICM (2006); członkiem zarządu Stockholm Mathematics Center (od 2009). Mimo zdecydowanie teoretycznego charakteru swoich badań jest także współautorem patentu związanym z elektronicznymi transakcjami. Johan Håstad był także członkiem komitetów programowych najważniejszych konferencji z informatyki teoretycznej i kryptologii: 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. Redaktor w takich czasopismach jak: Computational Complexity (od 1991); Theory of Computing (od 2004); Random Structures and Algorithms (od 2008); ACM Transactions on Computation Theory (od 2008); Information Processing Letter (1990-1993); SIAM Journal on Computing (1991-1999) oraz Journal of the ACM (1997-2003). Jest również członkiem komitetu naukowego Electronic Colloquium on Computational Complexity.

Johan Håstad dwukrotnie otrzymał najbardziej prestiżową nagrodę w informatyce teoretycznej - Gödel Prize (1994 oraz 2011). Inne wyróżnienia to między innymi: ACM doctoral dissertation award (1986); Chester Carlson’s research prize (1990); Göran Gustafsson prize in mathematics (1999). Johan Håstad był także zaproszony do wygłoszenia odczytu na ICM, Berlin, 1998 oraz wykładu plenarnego w czasie ECM, Stockholm, 2004. W 2008 roku Johan Håstad uzyskał prestiżowy ERC grant przeznaczony dla najlepszych naukowców Europy (ponad 2 miliony Euro) na badania w 2009-2013.