Andris Ambainis has kindly allowed me to post on this blog the obituary of Rūsiņš Freivalds he wrote for the February issue of the Bulletin of the EATCS. It is a fitting tribute to the importance of Rūsiņš's  lifetime work for TCS in general and for Latvian CS. 

Rūsiņš Mārtiņš Freivalds (1942-2016)

Rusins Freivalds, one of European pioneers of theoretical computer science, passed away on January 4, 2016 at the age of 73.

Freivalds was born on November 10, 1942 in Cesvaine, Latvia. He studied at the University of Latvia and, during his studies, he had an opportunity to spend two years in Novosibirsk, one of leading theoretical computer science research groups in the Soviet Union. There, he started working with Boris Trachtenbrot, one of leading Soviet computer scientists, who supervised his Ph.D. dissertation (defended in 1971 at Novosibirsk State University).

Freivalds is best known for his probabilistic algorithm for testing matrix multiplication, invented in 1977 (https://en.wikipedia.org/wiki/Freivalds'_algorithm). Freivalds' discovery was that, given the result of matrix multiplication, one could check its correctness substantially faster than the time for multiplying the matrices with the best algorithm that is known. Freivalds' algorithm was also one of the first probabilistic algorithms which were faster than deterministic algorithms.

Freivalds' algorithm became an inspiration for other researchers who started studying probabilistic algorithms. In particular, Turing Award winner Manuel Blum mentioned it as an important inspiration in his 1995 Turing Award lecture. Now, Freivalds' algorithm is a part of textbooks on probabilistic algorithms and is taught in many universities.

More generally, Freivalds was one of the first to study probabilistic algorithms and to compare the power of algorithms that use random coin flips with algorithms that do not use randomness. His focus was on finding situations in which one could prove that randomness increases the computational power. For example, Freivalds showed that there is a language that can be recognized by a probabilistic 2-way finite automaton but not by a deterministic 2-way finite automaton. He also showed similar results for 1-way automata with multiple heads, pushdown automata and other computational models. Freivalds’ research in this direction in 1970s and 1980s was among the first results of this type.

Freivalds was interested in many research topics and published over 200 research papers. Another major research interest of Freivalds was inductive inference - a mathematical theory which models the process of learning on an abstract level, using computability theory.

Starting from late 1990s, Freivalds worked on quantum computing and quantum automata. Together with Andris Ambains, he showed that quantum automata can use exponentially less space than probabilistic automata. Most recently, he invented ultrametric automata, a model of automata with p-adic transition probabilities, winning a Best Paper Award at Turing-100 conference in Manchester.

Freivalds supervised 19 Ph.D. dissertations and a number of M.Sc. and B.Sc. theses, including Andris Ambainis (known as a leading quantum computing expert) and Daina Taimina (known for her crocheted models of hyperbolic planes). He was very active in introducing undergraduate students to theoretical computer science and bringing them to research conferences, teaching them to enjoy both research and cultural events (for example, opera or popular science museums).

A number of those undergraduates went on to do their Ph.D., either with him, or other faculty members at the University of Latvia or different universities abroad (including Berkeley, Yale, University of Maryland and University of Waterloo).

Freivalds was an excellent teacher and popularizer of theoretical computer science in Latvia. He was an engaging lecturer who was keen on showing connections between different subfields of mathematics and theoretical computer science. In 2006, University of Latvia students voted him to be the "Teacher of the Year" for all of the natural sciences. Through his teaching and student supervision, he left a major influence on theoretical computer science in Latvia.

Freivalds was highly recognized both in Latvia and internationally. In 2003, he received the Grand Medal of the Latvian Academy of Science (the highest Latvian award for lifetime achievement in research). Freivalds was a member of Academia Europeae and gave a number of invited talks at highly recognized international conferences (such as ICALP - International Colloqium on Automata, Languages and Programming and MFCS - Mathematical Foundations of Computer Science).