**Rusins Martins FREIVALDS**

Professor Rusins Martins FREIVALDSHead of Division of
Discrete Mathematics Phone: +371 722 6997, +371 26563358 |

** **

* Born: *November 10, 1942, Cesvaine, 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.

* Languages: *Latvian, Russian, English, German

Education:

- University of Latvia (Faculty of Physics and Mathematics), 1965
- Postgraduate, Institute of Mathematics, University of Latvia, 1970
- 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
- Dr.habil.math. (Doctor of Science in former USSR), Moscow State University, Russia, 1985

Experience

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

abroad:

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

Honours and Awards:

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

Professional Activities and Memberships:

- Member, Supervisory Council, Latvian Academy of Sciences, 1994-1996
- Member, Senate, University of Latvia, 1993-
- Member, Latvian Council of Science Expert Commission for Mathematics and Physics, 1993-
- Member, Working Group WG 1.4 of International Federation for the Information Processing, 1995-
- Chair of Program Committee, Workshop on
*Randomized Algorithms,*Brno, Czech Republic, 1998 - Member of Program Committees:

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

*-* International Symposium Fundamentals of Computation Theory, Bucharest, Rumania,
1998

- Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, 1998

- International Symposium on Theoretical Aspects of Computer Science, Lubeck, Germany,
1997

- International Symposia on Mathematical Foundations of Computer Science, Prague,
Czechoslovakia, 1992; Rytro, Poland, 1989; Bratislava, Slovakia, 1997

- International Colloquia "Automata, Languages and Programming", Paderborn,
Germany, 1996, Lund, Sweden, 1993

- 2nd European Conference "Computational Learning Theory", Barcelona, Spain,
1995

- Workshop "Computational Learning Theory"*, *Santa Barbara, USA, 1992

- International Workshop "Algorithmic Learning Theory", Tokyo, Japan, 1993

Invited Lectures:

- 25th Conference on Current Trends in Theory and Practice of Informatics SOF-SEM'98. Jasna, Slovakia, 1998.
- 22nd International Colloquium Automata, Languages and Programming. Szeged, Hungary, 1995.
- 3rd Annual Workshop on Computational Learning Theory. Rochester, USA, 1990
- Symposium on Algorithms, Tokyo, Japan, 1990
- Symposia on Mathematical Foundations of Computer Science: High Tatras, Czechoslovakia, 1986, 1981; Jadvisin, Poland, 1974
- Symposia on Fundamentals of Computer Science: Linkoping, Sweden, 1983; Kazan, Russia, 1988
- USSR Conferences on Mathematical Cybernetics: Saratov, 1985; Irkutsk, 1987
- USSR Conference on Mathematical Logics, Kishinev, 1978

Courses:

University of Latvia:

- Complexity of Algorithms, 1972-
- Linear Algebra, 1974-1975
- Theory of Numberings, 1975-1976
- Theory of Algorithms, 1992-
- Main Notions of Mathematics, 1993-
*http://www.latnet.lv/LU/MII/MII_staff/rusins/main/index.htm* - Data Protection and Cryptography, 1994-
*http://www.latnet.lv/LU/MII/MII_staff/rusins/crypt.htm* - Algorithms. Automata and Formal Languages,1, 1994-
- Algorithms. Automata and Formal Languages,2, 1994-

Recent/Representative Publications:

- R.Freivalds, D.Taimina, E.B.Kinber. Fundamentals of Computers. 1986, Kiev: Radianska
Skola Press,
*?*pp*.*(in Russian) - R.Freivalds (Ed.) Randomized Algorithms. Proceedings of the International Workshop
Randomized Algorithms, Brno, Czech Republic, August 27-28, 1998, Aachen University Press,
?
*.* - R.Freivalds. On synthesis in the limit indices of total recursive functions in various
computable numberings.-
*Dokladi AN SSSR,*1974, vol.219, 4, pp.812-814 (in Russian) - R.Freivalds. Methods and languages to prove the power of probabilistic machines.
Proceedings of IFIP Congress'83
*Information Processing'83*, Elsevier, 1983, pp.157-162 - R.Freivalds. Inductive inference of recursive functions: qualitative theory.-
*Lecture Notes in Computer Science,*Springer, 1991, vol.502, pp.77-110. - R.Freivalds, E.B.Kinber, C.H.Smith. On the impact of forgetting on learning machines.-
*Journal of the ACM,*1995, vol.42, 6, pp.1146-1168. - K.Apsitis, R.Freivalds, C.H.Smith. On duality in learning and the selection of learning
teams.-
*Information and Computation,*1996, vol.129, 1, pp.53-62. - A.Ambainis, R.Freivalds, C.H.Smith. General inductive inference types based on
linearly-ordered sets.-
*Lecture Notes in Computer Science,*Springer, 1996, vol.1046, pp.243-256. - R.Freivalds, S.Jain. Kolmogorov numberings and minimal identification.-
*Theoretical Computer Science,*1997, vol.188, 1-2, pp.175-194. - R.Bonner, R.Freivalds, J.Lapins, A.Lukjanska. Non-stochastic languages being projections
of 2-tape quasideterministic languages.-
*Lecture Notes in Computer Science,*Springer, 1998, vol.1450, pp.213-219. - R.Freivalds. Models of computation, Riemann hypothesis, and classical mathematics. -
*Lecture Notes in Computer Science,*Springer, 1998, vol.1521, pp.89-106. - J.Barzdins, R.Freivalds, and C.H.Smith. Towards axiomatic basis of Inductive Inference.
–
*Lecture Notes in Computer Science,*2001, vol.2138, pp.1-13 - A.Ambainis, K.Apsitis, R.Freivalds, C.H.Smith. Hierarchies of probabilistic and team
FIN-identification. –
*Theoretical Computer Science*, 2001, vol.261, pp.91-117. - R.Freivalds, C.H.Smith. Category, measure, inductive inference: A triality theorem and
its applications. –
*Lecture Notes in Computer Science*, 2002, vol.2286, pp.386-399. - R.Bonner, R.Freivalds. Quantum learning by finite automata. –
*Proceedings of International Workshop on Quantum Computation and Learning,*2002, May 25-26, Riga, Latvia. (Eds. R.Bonner and R.Freivalds), pp. 99-111. - A.Ambainis. R.Freivalds. Boolean function with a low polynomial degree. -
*Proc. Latv.Acad. Sci., B,*2003, vol. 57, N 3/4, pp.74-80. - R.Freivalds, M.Golovkins, A.Kikusts. On the properties of probabilistic reversible
automata. –
*Proceedings of SOFSEM 2004: Theory and Practice of Computer Science*(eds. P.van Emde Boas at al.), Prague: MatFyzPress, 2004, vol.2, pp.75-84. - R.Freivalds, M.Miyakawa, I.G.Rosenberg. Complexity of decision trees for Boolean
functions. –
*Proceedings of Internat. Conference on VLSI*, 2003, pp.253-258. - R. Freivalds. Knot Theory, Jones Polynomial and Quantum Computing. -
*Lecture Notes in Computer Science,*2005, vol.3618, pp.15-25 - R.Freivalds. Language recognizable by quantum finite automata. –
*Lecture Notes in Computer Science*, Springer, 2006, vol.3845, pp.1-14.

Research Projects:

- R.M.Freivalds (Head of Project). Randomized Methods in Inductive Inference.
*Latvian Council of Science*(1990-1993) - R.M.Freivalds (Head of Project). Mathematical Principles of Randomized Algorithms in
Inductive Inference.
*Latvian Council of Science (*1994-1996) - R.M.Freivalds (Head of Project). Complexity of Randomized Algorithms.
*Latvian Council of Science*(1997- 1999) - R.M.Freivalds (Head of Project). Co-operative Research in Inductive Inference for the
University of Maryland and the University of Latvia.
*National Science Foundation*(1992-1998) - R.M.Freivalds (Head of Project). Joint Research in Computer Science for the University
of Lund and the University of Latvia.
*Academy of Sweden*(1994-1995) - R.M.Freivalds (Head of Project). Joint Research in Computer Science for the Malardalens
University and the University of Latvia.
*Academy of Sweden*(1997-2000) - R.M.Freivalds (Head of Project). Quantum Automata and Their Capabilities.
*Latvian Council of Science*(2001 -2004) - R.M.Freivalds (Head of Project). Quantum Algorithms and their Complexity.
*Latvian Council of Science*(2005 - )

*Last update:30-10-2007 12:45:22*