You are here: TUCS > RESEARCH > Distinguished Lectures > Johan Håstad
TUCS Distinguished Lecture
Friday, April 4, 2014 at 13.15
ICT Building, Auditorium Lambda
Coffee served from 12:45
Click here for the video on Youtube.
Johan Håstad, KTH - Royal Institute of Technology, Sweden: "How hard it is to find a good solution?"
Host: Ion Petre, Åbo Akademi University
Abstract: Suppose we are given an optimization problem where the quality of a proposed solution can be evaluated efficiently. The natural instinct is to try find the best solution but in some cases this leads to infeasible amounts of computation. To study when this happens leads to the classical theory of NP-completeness that was initiated in the 1970'ies and mostly completed before 1990. The most famous NP-complete problem is the Traveling Salesman Problem. The first part of the lecture will review these classical results.
When it is too computationally expensive to find the best solution one naturally turns to finding good solutions. This is often formalized as finding a solution which is within a small predetermined factor of optimal and our understanding of these questions have seen substantial progress in the last decades.
It turns that for some problems it is possible to find very good such approximate solutions quite efficiently while in some other cases even very weak approximation remains infeasible. In the second part of the lecture we give some highlight results of both types.
Biography: Johan Håstad is a professor in theoretical computer science at the Royal Institute of Technology in Stockholm, Sweden. He received his Bachelor of Science from Stockholm University in 1981, his Master of Science from Uppsala University in 1984 and his PhD from MIT in 1986 under the supervision of Shafi Goldwasser. He was appointed Associate Professor at the Royal Institute of Technology in Stockholm, Sweden in 1988 and obtained a full professorship at the same place in 1992. He also held visiting positions at MIT and at the Princeton Institute for Advanced Study. He is a member of the Swedish Royal Academy of Sciences since 2001 and a fellow of the American Mathematical Society since 2012.
Johan Håstad has research interests within several subareas of Theory of Algorithms and Complexity theory, in particular complexity theory, lower bounds, cryptography and pseudorandomness, randomized algorithms and approximation algorithms. He has, in recent years, mainly focused on the approximability of NP-hard optimization problems.
Johan Håstad was the recipient of the Gödel Prize in 1994 and 2011. He was also the recipient of the ACM Doctoral Dissertation Award in 1986, of the Göran Gustafsson prize in mathematics (1999), and of the Chester Carlson research prize (1994). He was an invited speaker at the International Congress of Mathematicians (1998) and a plenary speaker at the European Congress of Mathematics (2004).
The TUCS Distinguished Lecture Series is a forum for public lectures by outstanding national and international researchers in all aspects of computing, coming both from academia and industry. All lectures are free and open to the public.
Welcome!