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)
Freivalds, one of European pioneers of theoretical computer science,
passed away on January 4, 2016 at the age of 73.
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).
is best known for his probabilistic algorithm for testing matrix
multiplication, invented in 1977
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.
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
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.
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.
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.
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).
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).
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.
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).