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

Last night I was ordering a file cabinet drawer and stumbled on my PhD thesis that I have not looked at for many years now.

I was listing through yellowish pages and remembered the time they were written - from the beginning to the end it took 10 years which are now hidden in 69 pages.

It all started when I first met Prof. Freivalds under strange circumstances - on a bus in Latgale, region of Latvia. It was May 1980 and in Soviet Union, Latvia then was part of, 35th anniversary of the end of WWII was celebrated. University of Latvia track and field team proposed to do the run from Latvia's border with Russia till Blīdene. I was still a runner at that time and participated in this run across Latvia. Since it was highly politicized event, for each part of the run there was assigned some senior member from the University of Latvia to be present. When I finished one of my parts of the run, I was getting on a bus that was following us and was greeted by a man who said: - You should stop running around, and should start serious work. - It was Rūsiņš Freivalds.

- What do you mean by that?- I was surprised.

- You should do serious mathematics.

- Well, I tried, but it did not work, - I shortly explained my previous two failed attempts which were not my fault but which made me think that I cannot do any math research.

- You have a potential , come to my seminars, - he was brief. - We are meeting every Tuesday afternoon.

I graduated from University of Latvia cum laude as a math and math education major but knew nothing about what kinda research Freivalds and his group were doing, I knew nothing about  theoretical computer science. I was teaching math classes in university for prospective math teachers, was high school math teacher myself, and had a half-time job on a grant about mathematical methods in nuclear physics. 

When I returned back to work after our week-long run I told my grant PI Harijs Bondars that I was invited to go to Freivalds seminars. Harijs looked at me and said: - You would be a fool not to go.

So - I did not want to be a fool and went, just to realize that I do feel like a fool there - not understanding much and having no background in computer science.

Prof. Freivalds required weekly meetings with him, so I can catch up on what courses I had missed as an undergraduate - algorithm theory, automata theory... He usually explained a new notion, then assigned me about 4-5 problems, and I had a week to work on them. I am not sure that he even knew that in US this is called Moore Method, neither do I. For me it was his method of teaching mathematics. 

In fall 1980 I had a semester in Moscow State University which was meant for university instructors "to raise qualification". Prof. Freivalds made a list of classes taught by famous mathematicians  which I had to attend. I also had a long reading list since being in Moscow I had a privilege to access Nauchno Technicheskaja Biblioteka - in those days it was the only library in Soviet Union where I could read some mathematical journals. To lighten my fate Prof. Freivalds also suggested to read  Mathematical Intelligencer which was available in that library only. He himself often had a business in Moscow because he was working on his own dissertation; he had PhD but in order to become full professor in Soviet Union one had to defend "doctor dissertation". I was living in a dorm, and people there at front desk became suspicious of me getting "photo telegrams" in some strange language with weird symbols - in those pre e-mail times that was the way for Prof. Freivalds to let me know what should I do next or  that he will be in Moscow and we should meet in some metro station - he chose ones where we could not miss each other, the ones without transfers, and then we could talk on his way to the airport.

When I came back to Riga and had to apply to graduate school in order to continue teaching in university, I told the Chair of the Department I was working in that Prof. Freivalds will be my thesis adviser. The Chair almost screamed at me: - You are too stupid to work with him! You will never be able to finish your thesis.

Now I really had to prove that I am not a fool, and so my work with Prof. Freivalds started. And this is how I remember him when he was talking seriously about mathematics. (The photo is not mine, I borrowed it from web, taken last May in Kyoto).

This morning I woke, as usual checked my e-mail, and there was one short line - Your adviser Prof. Freivalds died.
I could not believe it. I thought it was a mistake. It was just recently when we exchanged e-mails, I sent him birthday wishes; he told me that he is in Paris on his way back to Riga from Canada, that was Thursday, and next day was a terror act in Paris, and I wrote to him - I hope you are safe, and not in Paris anymore. He answered - still in Paris, but safe. Just a week ago Academia.org sent me a message that Rūsiņš Freivalds has marked me as a co-author on of our joint papers, and I have to accept that. I knew he was working. I am no more in Riga but we kept e-mail contact, were meeting when I was in Riga, and he had come to visit us in Ithaca several times. The first one was in 2002 when he came with a group of his students (there were several more such visits).

It was in January but I could still show some of our beautiful waterfalls around Cornell campus between their busy schedule of meetings and seminars in Computer Science Department.

 Prof. Freivalds with Ellie Hartmanis - we were all invited to the dinner at Prof. Hartmanis home.

Rūsiņš Freivalds and Anil Nerode

In summer 2005 Freivalds came to Ithaca alone, without students. He was a visiting researcher at Cornell and lived with us. Every morning he would go to his office and work until 4-5pm. Only after that David and I could take him out somewhere in country. Freivalds told me that the summer in Cornell was very valuable for him - the opportunity to do what he loved most of all - to do mathematics without any distractions.

One weekend I managed to convince him to come with me and showed U-pick blueberries wich was something new for him.

Rūsiņš acknowledged that he is very much a city person, however he did enjoy picking blueberries and was proud how much he picked. 

When going to conferences he was also trying to see around as much as possible. He was teaching his students that they should learn as much as possible about places they were visiting. He said that one should see variety of places - here are two examples of him visiting Wax Museum in Las Vegas.

Today I was trying to find pictures he was sending me from various places he was visiting, but somehow found only this one - from his first trip to Paris. 

Rūsiņš Freivalds was very happy when his work was acknowledged, not that he would have lack of that. I think it was mostly because he was trying to prove that his mind is still full with new ideas, the age had not slowed him down. Research Gate counts 208 publications for Freivalds. Rūsiņš once told me that he would like to reach 200, so he did it. I was arguing with him that instead of those numerous short publications and his results scattered all over the place, he should write a book. He said the time will come and he will. We even once had a plan to write a book together about big ideas in mathematics, but ...

I was looking for another photo where we could be seen together - 

 found this one - from November 2003 - after Freivalds received the highest Award from Latvian Academy of Sciences.

and the one from May 1985 - it was my first computer science conference which I attended with my adviser

Latvian internet news slowly starting to announce that Prof. Freivalds has passed away. I am looking at computer screen and still cannot believe that there will be no e-mails from rusinsf@latnet.lv 

Suddenly the world has turned black and white -  then and now. 

I will miss you. 

Edited on January 9.
Prof. Freivalds always regarded to Andris Ambainis as "my all times best student". Here is what Andris Ambainis posted in memory of his professor on Facebook:
Rusins Freivalds, one of the leading Latvian computer scientists of his generation, passed away today from a heart attack, at the age of 73. He was also my first research supervisor and played a major role in my development as a researcher.
Freivalds learned theoretical computer science in Novosibirsk, Russia (3500 km east of Latvia). During his studies at the University of Latvia, he had the opportunity to spend two years in Novosibirsk which, at that time, was one of 2-4 leading computer science research organizations in the Soviet Union. Akademgorodok (Academic Town), on the outskirts of Novosibirsk, was a quiet place without many distractions and, at the same time, it was a place for top-class research organizations. There, he started working with Boris Trachtenbrot, one of leading Soviet computer scientists, who supervised his Ph.D. dissertation.
After returning from Novosibirsk, Freivalds, together with other Latvians who studied in Novosibirsk (most notably, Jānis Bārzdiņš) established a research tradition in computer science at the University of Latvia. In fact, most of the faculty at our Faculty of Computing are academic descendents (students or students of students) of one of them!
Worldwide, Freivalds is best known for his probabilistic algorithm for testing matrix multiplication, invented in 1977. Finding faster algorithms for matrix multiplication is a major research challenge. 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 is now a part of standard textbooks on probabilistic algorithms and is taught in courses in many universities. I think it was also mentioned as an important inspiration by Manuel Blum in his Turing Award lecture.
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. A lot of this work is now superseded by later results but, in 1970s, he was one of the pioneers of a new research field and this was a cutting edge research.
Being in Soviet Union, it was quite non-trivial for him to keep up with the research developments in the West. When I worked with him, Soviet Union was gone but I saw English-language books that were copied by him from a library in Moscow by taking a photograph of every page of the book - this was the only way how he could obtain a copy. And I heard stories of how he was only allowed to travel outside the Soviet Union once in two years. Freivalds used this to go to MFCS (Mathematical Foundations of Computer Science) conferences in Czechoslovakia and Poland and tried to keep up with what was happening on the other side of the Iron Curtain as much as possible.
I started attending Freivalds' seminar in my first weeks at the University of Latvia, as a first year undergraduate. Working with undergraduates and trying to introduce them to research was extremely important for Freivalds. And being able to find research questions that were explainable to an undergraduate student like me (a smart person but without much background knowledge) was one of his talents.
I ended up working together with Freivalds for 5 years, until I finished my Masters'. We worked on a number of topics, primarily in inductive inference (a recursion-theoretic theory of learning) but also in communication complexity and complexity of finite automata. When I look at my list of publications, I can count 15 papers from this period, some of which we wrote together and some were written by just myself but on topics suggested by Freivalds.
This research experience built my skills as a researcher and made me recognizable outside Latvia. It was the main reason why I was admitted to Ph.D. program in computer science at Berkeley and went on to do things that I have done.
It is remarkable that Freivalds was also the first person who suggested quantum computing to me. In 1993, he came back from a conference (FOCS'93), showed me one of the very early papers on quantum computing and said "This is the thing to work on!". And that was in 1993, before Shor's factoring algorithm was discovered!
I did not do any original work on quantum computing at that time because there was nobody else around in Latvia who would know something about it. Neither did Freivalds. But it is highly remarkable that he saw the potential of it, before the rest of the world realized it.
By coincidence, I took a course on quantum computing at Berkeley in 1997. And, when I came back to Latvia for Winter break, I talked with Freivalds and discovered that he has started working on it too. We collaborated on quantum computing research for the next 5 years and it was helpful for both of us. I also helped with mentoring some of his students in quantum computing. And, besides being interesting as research, this also helped me to maintain connection to Latvia. One of several connections to Latvia which lead me to coming back to Latvia in 2007.
Freivalds was an excellent teacher. In 2006, University of Latvia students voted him to be the "Teacher of the Year" for all of the natural sciences. And my teaching methods have certainly borrowed from him quite a bit. (By coincidence, another person who has been a major influence on my teaching style is prof. Agnis Andžāns who trained myself and other Latvian students for mathematics olympiads. He did his Ph.D. in theoretical computer science with Freivalds and there is quite a bit of similarities between their styles.)
Freivalds is one of a very small number of people who have influenced my life trajectory in a fundamental (possibly, life-changing) way. I am not sure where I would be without him as an advisor as an undergraduate. I am very thankful to him for guiding me.

edited January 24, 2016
in 2002 when Andris Ambainis was at the Institute for Advanced Studies I drove Rūsiņš Freivalds from Ithaca to Princeton to visit him.

in front of IAS