Professor Rusins Martins FREIVALDS

**Faculty of Computer Science, University of Latvia**

Raina bulv. 29, Riga, LV 1459, Latvia

**Interests: **

**Inductive Inference (Computational Learning Theory)****Randomized Algorithms (Complexity of Computation)****Mathematical Foundations of Computer Science**

Brief Description of Main Research:

**The primary area of my research has always been complexity of computation. In 1975 I proved the very first theorem on advantages of randomized algorithms over deterministic ones. Namely, I have proven that randomized Turing machines can use less running time than deterministic ones to compute certain functions. Recently I have developed new powerful methods to prove lower bounds for time and space complexity of randomized algorithms.**

**I have published various results in Inductive Inference. I have tried to use deep methods of classical mathematics for problems in Theoretical Computer Science. I would like to mention the usage of constructive ordinals to measure the complexity of Inductive Inference, and the usage of Group Theory in Inductive Inference.**

**Recent/Representative Publications** (PDF file)

** **

**Education: **

- Dr.habil.math. (Doctor of Science in former USSR), Moscow State University, Russia, 1985
- Dr.math. (Candidate of Science in former USSR, Ph.D. in Western countries), Institute of Mathematics, Academy of Sciences of USSR, Novosibirsk (Thesis advisor Professor B.A.Trakhtenbrot), 1971
- Postgraduate, Institute of Mathematics, University of Latvia, 1970
- University of Latvia (Faculty of Physics and Mathematics), 1965

**Languages: **Latvian, Russian, English, German

**Professional experience**

**Latvia: **

- Professor, Head of Division of Discrete Mathematics, Faculty of Physics and Mathematics, University of Latvia, since 1992
- Professor, Leading Researcher, Institute of Mathematics and Computer Science, University of Latvia, 1990-1991
- Professor, Deputy Director of Computing Centre, University of Latvia, 1985-1990
- Head of Laboratory, Computing Centre, University of Latvia, 1975-1985
- Researcher, Senior Researcher, Computing Centre, University of Latvia, 1970-1975
- Assistant, Faculty of Physics and Mathematics, University of Latvia, 1965-1966

**abroad: **

- Visiting Professor, Kyoto University, Japan (2009), Cornell University, USA (2005 ), Tsukuba Technical University, Japan (2004), Malardalens University, Sweden (1996); National University of Singapore (1994); University of Bonn, Germany (1994); Electrotechnical Laboratory, Tsukuba, Japan (1993); Humboldt University, Berlin, Germany (1991);
- Visiting Researcher, Kalinin State University, Kalinin, Russia, 1980

**Professional Activities and Memberships: **

- Member, Supervisory Council, Latvian Academy of Sciences, 1994-1996
- Member, Working Group WG 1.4 of International Federation for the Information Processing, since 1995
- Member, Senate, University of Latvia, since 1993
- Member, Latvian Council of Science Expert Commission for Mathematics and Physics, since 1993

Chair of Program Committee:

- 10th Scandinavian Workshop on Algorithm Theory SWAT 2006, (Riga, Latvia,

2006) - 13th International Symposium ”Fundamentals of Computation Theory” (Riga,

Latvia, 2001)

- International workshop ”Quantum Computation and Learning” (Sundbyholms

Slott, Sweden, 2000)

- International workshop ”Quantum Computation and Learning” (Riga, Latvia,

1999)

- International workshop ”Randomized Algorithms” (Brno, Czech Republic, 1998)

Membership in Program Committees:

- The 4th International Conference on Language and Automata Theory and Applications

LATA 2010 (Trier, Germany, 2010)

- The 3rd International Conference on Language and Automata Theory and Applications

LATA 2009 (Tarragona, Spain, 2009) - The 2nd International Conference on Language and Automata Theory and Applications

LATA 2008 (Tarragona, Spain, 2008)

- The 13th International Conference on Implementation and Applications of Automata

CIAA 2008 (San Francisco, California, USA, 2008)

- 25th International Symposium on Mathematical Foundations of Computer Science

MFCS 2000 (Bratislava, Slovak Republic, 2000)

- 22nd International Symposium on Mathematical Foundations of Computer Science

MFCS 1997 (Bratislava, Slovak Republic, 1997)

- 12th International Symposium ”Fundamentals of Computation Theory” FCT’99

(Iasi, Rumania, 1999)

- 6th Scandinavian Workshop on Algorithm Theory SWAT’98 (Stockholm, Sweden,

1998)

- 14th International Symposium on Theoretical Aspects of Computer Science

STACS’97 (Lubeck, Germany, 1997)

- 23rd International Colloquium ”Automata, Languages and Programming” ICALP’96

(Paderborn, Germany, 1996)

- Second European Conference ”Computational Learning Theory” (Barcelona,

Spain, 1995)

- 13th World Computer Congress (Hamburg, Germany, 1994)

- 20th International Colloquium ”Automata, Languages and Programming” ICALP’93

(Lund, Sweden, 1993)

- 4th InternationalWorkshop ”Algorithmic Learning Theory” (Tokyo, Japan,1993)

Workshop ”Computational Learning Theory” COLT’92 (Santa Barbara, USA,

1992)

- 17th International Symposium on Mathematical Foundations of Computer Science

MFCS 1992 (Prague, Czechoslovakia, 1992)

- 14th International Symposium on Mathematical Foundations of Computer Science

MFCS 1989 (Rytro, Poland, 1989)

**Invited Lectures: **

- MEMICS 2009, Fifth Doctoral Workshop on Mathematical and Engineering

Methods in Computer Science (Znojmo, Czech Republic, 2009)

- Estonian Theory Days at J¨oulum¨ae, (J¨oulum¨ae, Estonia, 2008)

- 4th Symposium on Stochastic Algorithms, Foundations and Applications SAGA’2007

(Zurich, Switzerland)

- International Symposium ”Mathematical Foundations of Computer Science”

MFCS’2005 (Gdansk, Poland, 2005)

- Tenth International Conference on Implementation and Application of Automata

CIAA’2005, Sophia Antipolis, France

- NATO Advanced Study Institute ”Structural Theory of Automata, Semigroups

and Universal Algebra” (Universit´e de Montr´eal, Canada, July 7-18, 2003)

- Conference ”General Theory of Information Transfer” at the Center for Interdisciplinary

Research (Bielefeld, Germany, November 4-9, 2002)

- Workshop on Quantum Computer Theory (Turin, Italy, 2001)

2nd Bielefeld Workshop on Quantum Information and Complexity (Bielefeld,

Germany, 2000)

- International workshop ”Molecular Computing and Quantum Computing” (Vienna,

Austria, 2000)

- ”Quantum Day” (University of Nice, France, 2000)

Bielefeld Workshop on Quantum Information and Complexity (Bielefeld, Germany,

1999)

- Sixth Fenno-Ugric Symposium on Software Technology (Sagadi, Estonia, 1999)

25th Conference on Current Trends in Theory and Practice of Informatics ”SOFSEM’

98” (Jasna, Slovakia, 1998)

- 22nd International Colloquium ”Automata, Languages and Programming” ICALP’95

(Szeged, Hungary, 1995)

- 3rd Annual Workshop on Computational Learning Theory ( Rochester, USA,

1990 )

- Symposium on Algorithms (later called COCOON) ( Tokyo, Japan, 1990 )

- Symposia on Mathematical Foundations of Computer Science (Gdansk, Poland,

2005; High Tatras, Czechoslovakia, 1986; High Tatras, Czechoslovakia, 1981;

Jadvisin,Poland, 1974 )

- Symposia on Fundamentals of Computer Science ( Linkoping, Sweden, 1983;

Kazan, USSR, 1988)

- USSR conferences on Mathematical Cybernetics ( Saratov, 1985; Irkutsk, 1987

- USSR conference on Mathematical Logics (Kishinew, 1978)

**Courses: **

University of Latvia:

- 2010- GOOGLE search algorithms
- 2006- Elliptic curve cryptography
- 2004- Quantum computers
- 2003- Game theory
- 1994- Algorithms. automata and formal languages, 2
- 1994- Algorithms. automata and formal languages, 1
- 1994- Data protection and cryptography
- 1993- Main notions of mathematics
- 1992- Theory of algorithms
- 1975-1976 Theory of numberings
- 1974-1975 Linear algebra
- 1972- Complexity of algorithms

**Honours and Awards: **

- Prize
*Best Professor of all departments*at the 1st Poll in the

University of Latvia, 2007 - The Latvian Academy of Sciences and Joint Stock Company "Grindex" Prize, 2003
- Grand Medal of the Latvian Academy of Sciences, 2003
- The Latvian Academy of Sciences Eizens Arins prize for a cycle of a papers
*Effective Probable Algorithms*, 2000 - Full Member, Latvian Academy of Sciences, 1992
- Corresponding Member, Latvian Academy of Sciences, 1992
- Honorary Scientist of Latvian SSR, 1986
- Member, European Association of Theoretical Computer Science, 1979
- Latvian YCL Prize for the work
*Theory of Inductive Inference*, 1976