HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE

Department of Computer Science Colloquium
2015 Series

On the Power of Randomization in the Design of Efficient Algorithms

Prof. Juraj Hromkovic
Department of Computer Science
ETH Zurich

Date: March 13, 2015 (Friday)
Time: 4:30 - 5:30 pm
Venue: SCT909, Cha Chi Ming Science Tower, Ho Sin Hang Campus

Abstract
The classical algorithms are fully deterministic which means that the input of the algorithm and the algorithm itself unambiguously determine the sequence of computational steps. The randomized algorithm allows up to time to toss the coin and depending on the outcome to decide how to continue to work in order to find a solution for the given input. In this sense a randomized algorithm may have an unbounded number of different computations on every input. What is the gain of this game? For some problems the best known deterministic algorithms work in exponential time and so cannot be used in applications, but their randomized counterparts are very efficient. It is a big surprise that one can avoid a huge amount of work that cannot be physically performed in the known Universe by switching from deterministic control to a randomized one and paying for that with a negligible risk of computing a wrong solution. In this lecture we show examples of such miraculous effects on examples that do not require any complex mathematical concepts.

Biography
Juraj Hromkovic has been Full Professor of Information Technology and Education at the Department of Computer Science at ETH Zurich since January 2004. Born in Bratislava in 1958, study of computer science at the Comenius University, 1986 PhD, 1989 habilitation, 1990-1994 visiting professor at the University of Paderborn, 1994-1997 professor for parallel computing at Christian Albrechts University Kiel, 1997-2003 professor for algorithmics and complexity at RWTH Aachen. In 2001 elected as the member of the Slovak Academic Society and in 2010 elected as the member of the European Academy. He is a full professor at ETH Zurich since 2004. His research and teaching interests focus on informatics education, algorithmics for hard problems, and complexity theory with special emphasis on the relationship between determinism, randomness and non-determinism. One of his main activities is writing textbooks which make complex recent discoveries and methods accessible for students and practitioners and so contributing to the speed up of the transformation of new paradigmic research results into educational folklore.

********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)

http://www.comp.hkbu.edu.hk/v1/?page=seminars&id=326&lang=tc
Photos