You are here: TUCS > RESEARCH > Distinguished Lectures > Rusins Freivalds
TUCS Distinguished Lecture
Friday, March 27, 2015 at 13.15
ICT Building, Auditorium Gamma
Click here for the video on Youtube.
Prof. Rusins Freivalds, Institute of Mathematics and Computer Science, University of Latvia: "Ultrametric Algorithms and Their Complexity"
Host: Juhani Karhumäki, University of Turku
Abstract:We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much. Our results in this paper show that, for some problems (decision trees, learning of recursive functions) ultrametric algorithms can have smaller complexity than even nondeterministic algorithms.
Biography: Prof. Rusins Freivalds received his PhD in 1971 from the Institute of Mathematics, Novosibirsk, and his DSc in 1976 from Moscow University. He is since 1992 Dr.habil.math. Prof. Freivalds is a member of the Academy of Sciences of Latvia since 1992, a member of the European Association for Theoretical Computer Science since 1979. He has been working at the Institute of Mathematics and Computer Science since 1970.
Prof. Freivalds’s primary area of research has always been complexity of computation. In 1975 he proved the very first theorem on advantages of randomized algorithms over deterministic ones. A typical feature of his research is the use of deep methods of classical mathematics for problems in theoretical computer science. He has given invited talks on his research in complexity of computation and inductive inference in many top international conferences. Computer education is another interest of his, which has resulted in educational TV shows, books, including one published in a million copies.
Prof. Freivalds’s achievements have been well recognized by the international research community. He received the Latvian YCL Prize for the work on Theory of Inductive Inference in 1976. He is a Honorary Scientist of Latvian SSR, 1986. He received the Latvian Academy of Sciences Eizens Arins prize for a cycle of a papers, Effective Probable Algorithms, 2000, the Grand Medal of the Latvian Academy of Sciences, 2003 and the Latvian Academy of Sciences and Joint Stock Company "Grindex" Prize, 2003.
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!