Monday, March 14, 2016

Folding Paper: Visual Art meets Mathematics

Last Monday was real treat to listen MIT Professor Erik Demaine talking how his math and art interests have intertwined. Demaine joined the MIT faculty in 2001 at age 20, reportedly the youngest professor in the history of the Massachusetts Institute of Technology.
Erik was born in Halifax, Nova Scotia, and from the age 7 to 12 he was travelling with his father artist Martin Demaine - homeschooling at that time worked perfectly. They both learned a lot from the communities they lived over those 5 years. At the age 12 Erik enrolled in college and 2 years later he had completed his bachelors degree.

Demaine's PhD dissertation was a seminal work in computational origami which later was incorporated into the book which is also in my home library and I had a chance it to be signed by the author.
Erik's work had sparked great interest around the world - just look at the list of his collaborators....




Some skeptics may ask what is the practical use of this fun with origami. Erik has an answer - his latest work has practical applications - it is about so called "thick folding" - usually paper thickness is counted as almost negligible but in reality and with other materials thickness is significant factor.

Origami ideas can grow out of curiosity = one of them - Maze Folding. Is it possible to fold any maze? Yes. Artistic outcome of this is fun algorithm how to fold - YES with the shadow showing NO - so - is it yes or no?
I remember this work from the exhibit "Measure for Measure" (2011) in Central Booking when it was still in DUMBO (I had my crocheted manifold pieces in the same show.)
Computational algorithms for geometric origami is cool thing to learn - Erik Demaine can teach a lot and also to spark ideas. Videos of his lectures are available from his webpage.
One of the hobbies of father-son team is to come up with various fonts that correspond with their artistic and mathematical interests. As Erik said - they taught each other - father taught Erik to be an artist, Erik taught his father to become a mathematician.
Question from the audience - what are those two last fonts? Erik smiles - they are juggling fonts, I do not have juggling balls with me... But there is Allen Knutson, one time world record holder in passing 12 balls,  in audience - and he always has juggling balls with him, he often uses when lecturing mathematics. So Erik has an opportunity to demonstrate how to juggle each letter of the alphabet.

There are old stories about folding paper sheet so that with one cut you can make some figures.
Even famous magician Houdini was interested in this kind of magic.
This lead to Fold and Cut Problem.

Traditional origami is all about folding stright lines. Erik and Martin Demaine's were puzzled - how about folding curves? They discovered the legacy of David Huffman and perfected it in their own way. It is an interesting history of Curved Origami Sculptures.









In origami sky is the limit. These days father-son team with the help of others are interested in folding the glass.



What else can be folded? More and more books are being digitized which makes printed books ...well, often to be discarded. Artists are taking over and trying to recycle them in creative ways. Of course, origami masters Demaines have their own challenge - for example, to fold a dictionary that you read one language in one diraection but the translation is on the other side of the crease.

Thank you for the great talk, Erik!

Saturday, February 27, 2016

Explanatory Objects


Wednesday morning Ithaca was fully wrapped in fog and continuous rain, not much of its beauty to see through windows of Clark Hall on Cornell Campus. It was a nice contrast against this grey backdrop on the windowsills of 609 Clark to study colorful objects brought for a little pop-up exhibit by artist Martha Lewis.
Martha was visiting Cornell Physics Department, invited by Itai Cohen for just a day which was packed with lots of meetings but the very first one was her talk Explanatory Objects. Martha says about her work :
My paintings contain technology-based elements purloined from engineering diagrams, architectural floor plans, electrical blueprints, maritime charts and other types of informational drawing. These images get combined into sprawling hybrid constructs, frequently using formats derived from carpet designs, modernist painting, and religious diagrams such as Mandalas and Tantric drawings.
Martha was trained as a painter but her work has stepped out of two-dimensionality in order to explore ideas. I would say that her "explanatory objects" are representations of the ideas she is exploring, visualization of this understanding be it an old mechanics book, astronomical manuscript, engineering diagram or just a title of an academic lecture that has intrigued her. Martha is very open to new ideas in science and exploring various ways to use them in her art - artist books, paintings in crumbled paper, installations... 






I first met Martha when she was curating an exhibit Yarn Theory in PS122 Gallery, New York, in 2009. Her idea then how to exhibit my work was very clever and to this day one of the most successful ones:
My crocheted series Manifolds are attached to the wall. (photo D. Guida)
In Martha's busy schedule we both could find only the time to have a breakfast together Thursday morning before Martha was leaving - thanks, Martha, for our talk and for your generous sharing of ideas and inspirations. Hope one day finally to make it to your studio in New Haven :-) But for now I will listen to your radio show Live Culture

I thought that with the topic of explanatory objects fits well a mention of a new work by Hamid Naderi Yeganeh - how to draw butterflies using circles.

Monday, January 4, 2016

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