[CPM-SPIRE-L] Danny Breslauer

[Galil, Zvi]

Hello CPMers and SPIRErs,

As you know, Kunsoo and Pino are working on a collection of pieces of people writing about Danny.
So far we have about 10 pieces. We need more.
Some of you wrote beautifully as a response to the terrible news.
Perhaps you can write something similar and send it to Kunsoo and Pino (copied).
Deadline is the end of January but if needed we will extend it.

See below my piece.

zvi

zvi


Zvi Galil, Georgia Tech

I first met Danny in the late 1980s at Tel Aviv University. He was a high school student taking courses at the university, usually spending his time in the computer unit. He became known as a whiz kid, a fantastic programmer.

Danny took my algorithms course, did very well, and immediately started working with me on parallel string matching. This led to a beautiful result -- an O(loglogn) optimal parallel algorithm for string matching. We then learned that Omer Berkman, Baruch Schieber, and Uzi Vishkin had produced similar results for other problems. The combined abstract appeared in STOC 1989, and our string matching result appeared in SICOMP 1990. The result is still the best known parallel algorithm for string matching, though the preprocessing portion has been improved.

The string matching result was more than sufficient for a master thesis. There was a minor problem: Danny had to earn both his high school diploma (via matriculation examination) and B.S. degree prior to completing the master’s degree. He completed all three at about the same time, at the age of 20.

From the beginning it was clear that Danny was extremely bright, but also that he did things in his own unconventional way, quite different from everybody else.

I took Danny to Columbia for Ph.D. studies. He continued to work on stringology and produced several nice results. The most impressive one was an Omega(loglogn) lower bound for parallel string matching. It implied that our algorithm was the best possible in the comparison model. It is still an open problem if one can do better in the case of special alphabets, like an alphabet of constant size. This result led to a STOC paper in 1991 and a SICOMP paper in 1992.

As I mentioned above, Danny was an incredible programmer. This turned out to be a mixed blessing. The good part was that he could easily make good money. He worked for companies. He completed projects for them quickly, and they paid him very well. From their perspective, the alternative was to hire a software company that would charge much more and usually take much longer. During his studies at Tel Aviv University and Columbia, Danny also worked on such projects.

After three years, Danny had enough results for a good thesis. I and his fellow students suggested to him to stay another year and make it stronger. In the early ’90s the academic job market was not good. But Danny insisted, and I let him finish his Ph.D. He was 24. There was a small delay since Danny had to pass two of the qualifiers (almost all students complete the qualifiers in their first year or two). Danny decided to work and make money. In several occasions, he had temporary academic jobs. He kept working on research with quite a number of people. He also worked for two or three companies, the last being Google. But it did not last long. My guess is that Danny was smarter than his managers.

I kept in touch with Danny throughout the years. When I stepped down as president of Tel Aviv University and briefly ventured into research in 2009, we worked together on streaming algorithms for string matching. We tried to understand a FOCS paper about it. We actually never understood it, but it turned out we did not have to since we improved it. The result was a real-time algorithm for streaming string matching that later appeared in a conference and a journal.

I met Danny several times in the Bay Area. Each time I go to the Bay Area, I stay with Cosimo Spera in San Francisco. We run four miles in Crissy Field, two miles to the Golden Gate Bridge and two miles back. Cosimo was a friend of Danny’s, and occasionally the three of us would go out to dinner. The last time I saw Danny was in Venice in June 2016 at the conference in memory of Alberto Apostolico. Alberto was also a friend of Danny, and they wrote a number of papers together.

All of his life Danny had health issues. We knew this, though we didn’t know details and never thought they were serious. Danny kept working on research and kept publishing. Last month we got from Gadi Landau the terrible news, the message from Iris, Danny's sister. We were shocked.

We will always remember Danny as very bright, nice, and gentle, with a good sense of humor.