Rusins Freivalds


Professor Rusins Martins FREIVALDS

Faculty of Computer Science, University of Latvia
Raina bulv. 29, Riga, LV 1459, Latvia




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)




Languages: Latvian, Russian, English, German




Professional experience


Professional Activities and Memberships:

Chair of Program Committee:

Membership in Program Committees:



Invited Lectures:





University of Latvia:



Honours and Awards: