Rusins Martins FREIVALDS
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,
? pp.
- 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
