A book in memory of Shimon Even


			Shimon Even was born in Israel on June 15th, 1935. He died on May 1st, 2004. In addition to his pioneering research contributions (most notably to Graph Algorithms and Cryptography), Shimon is known for having been a highly influential educator. He played a major role in establishing computer science education in Israel (e.g., at the Weizmann Institute and the Technion). He served as a source of professional inspiration and as a role model for generations of young students and researchers.

A book commemorating Shimon Even was published in the Festschrift series of Springer's LNCS (as Vol 3895, March 2006). The book contains research contributions and surveys by former students and close collaborators of Shimon.

Title: Theoretical Computer Science - Essays in Memory of Shimon Even

Editors: Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman

Brief Summary: This volume commemorates Shimon Even, one of founding fathers of Computer Science in Israel, who passed away on May 1, 2004. The volume contains research contributions, surveys and educational essays in theoretical computer science, written by former students and close collaborators of Shimon. In accordance with Shimon's style and principles, the essays address natural computational problems and are intended to be accessible to most researchers in theoretical computer science.

The book's preface (which follows) contains a short eulogy to Shimon and the list of essays included in the book.

Preface

On May 1, 2004, the world of theoretical computer science suffered a stunning loss: Shimon Even passed away. Few computer scientists have had as long, sustained, and influential a career as Shimon.

Shimon Even was born in Tel-Aviv in 1935. He received a B.Sc. degree in Electrical Engineering from the Technion in 1959, an M.A. in Mathematics from the University of Northern Carolina in 1961, and a Ph.D. in Applied Mathematics from Harvard University in 1963. He held positions at the Technion (1964-67 and 1974-2003), Harvard University (1967-69), the Weizmann Institute (1969-74), and the Tel-Aviv Academic College (2003-04). He visited many universities and research institutes, including Bell Laboratories, Boston University, Cornell, Duke, Lucent Technologies, MIT, Paderborn, Stanford, UC-Berkeley, USC and UT-Dallas.

Shimon Even played a major role in establishing computer science education in Israel and led the development of academic programs in two major institutions: the Weizmann Institute and the Technion. In 1969 he established at the Weizmann the first computer science education program in Israel, and led this program for five years. In 1974 he joined the newly formed computer science department at the Technion and shaped its academic development for several decades. These two academic programs turned out to have a lasting impact on the evolution of computer science in Israel.

Shimon Even was a superb teacher, and his courses deeply influenced many of the students attending them. His lectures, at numerous international workshops and schools, inspired a great number of students and researchers. His books, especially his celebrated Graph Algorithms, carried his educational message also to computer scientists who were not fortunate enough to meet him in person. As a mentor to aspiring researchers, Shimon was almost without peer, nurturing numerous junior researchers and advising many graduate students, who went on to have their own successful research careers.

Shimon Even was a pioneer in the areas of graph algorithms and cryptography, and his research contributions to these areas influenced the course of their development. Shimon was famous for not confining his interests to a few topics, but choosing rather to work in such diverse areas as switching and automata theory, coding theory, combinatorial algorithms, complexity theory, distributed computing, and circuit layout. In each of these areas, he produced high-quality, innovative research for more than four decades.

Shimon was the purest of pure theoreticians, following his nose toward research problems that were ``the right'' ones at the moment, not the faddish ones. His standards were impeccable, to the point where he would balk at employing any result whose proof he had not mastered himself. His integrity was unimpeachable: he would go to great lengths to defend any principle he believed in.

Shimon had a great passion for computer science as well as a great passion for truth. He valued simplicity, commitment to science, natural questions and carefully prepared expositions. By merely following his own way, Shimon influenced numerous researchers to adopt his passions and values. We hope that this is reflected in the current volume.

This volume contains research contributions and surveys by former students and close collaborators of Shimon. We are very pleased that Reuven Bar-Yehuda, Yefim Dinitz, Guy Even, Richard Karp, Ami Litman, Yehoshua Perl, Sergio Rajsbaum, Adi Shamir, and Yacov Yacobi agreed to send contributions. In accordance with Shimon's style and principles, the focus of these contributions is on addressing natural problems and being accessible to most researchers in theoretical computer science. The contributions are of three different types, reflecting three main scientific activities of Shimon: original research, technical surveys, and educational essays.

The contributions

The contributions were written by former students and close collaborators of Shimon. In some cases the contributions are co-authored by researchers who were not fortunate enough to be close to Shimon or even to have met him in person. Below we comment on particular aspects of each contribution that we believe Shimon would have appreciated

Original research

Needless to say, everybody likes original research, and Shimon was no exception. We believe that Shimon would have been happy with the attempt to make these research contributions accessible to a wide range of researchers (rather than merely to experts in the area). In order to promote this goal, these contributions were reviewed both by experts and by non-experts.

P. Fraigniaud, D. Ilcinkas, S. Rajsbaum and S. Tixeuil: An Overview of Space Lower Bounds for Graph Exploration via Reduced Automata. Shimon liked connections between areas, and the areas of graph algorithms and of automata theory were among his favorites.
O. Goldreich: Concurrent Zero-Knowledge With Timing, Revisited. Shimon would have joked at Oded's tendency to write long papers.
R.M. Karp: Fair Bandwidth Allocation Without Per-Flow State. Shimon would have like the fact that the starting point of this work is a practical problem, and that it proceeds by distilling a clear computational problem and resolving it optimally.
R.M. Karp, T. Nierhoff and T. Tantau: Optimal Flow Distribution Among Multiple Channels with Unknown Capacities. This paper has the same flavor as the previous one, and Shimon would have liked it for the very same reason.
A. Litman: Parceling the Butterfly and the Batcher Sorting Network. Shimon would have liked the attempt to present a new complexity measure that better reflects the actual cost of implementations.
Y. Perl, X. Zhou, J. Geller, and M. Halper: An Application Intersection Marketing Ontology. Shimon would have liked the fact that simple insights of graph theory are used for a problem that is very remote from graph theory.
R.L. Rivest, A. Shamir and Y. Tauman: How to Leak a Secret - Theory and Application of Ring Signatures. Shimon would have like the natural (``daily'') problem addressed in this paper as well as the elegant solution provided to it.
O. Yacobi with Y. Yacobi: A New Related Message Attack on RSA. Shimon would have enjoyed seeing a father and son work together.

Technical surveys

Shimon valued the willingness to take a step back, look at what was done (from a wider perspective), and provide a better perspective on it. We thus believe that he would have been happy to be commemorated by a volume that contains a fair number of surveys.

R. Bar-Yehuda and D. Rawitz: A Tale of Two Methods. Shimon liked stories, and he also liked the techniques surveyed here. Furthermore, he would have been excited to learn that these two techniques are in some sense two sides of the same coin.
Y. Dinitz: Dinic's Algorithm - The Original Version and Even's Version. Shimon is reported to have tremendously enjoyed Dinitz's lecture that served as a skeleton to this survey.
C. Glasser, A.L. Selman, and L. Zhang: Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems. This survey focuses on one of the applications of promise problems, which was certainly unexpected in 1984 when Shimon Even, together with Alan Selman and Yacov Yacobi, introduced this notion.
O. Goldreich: On Promise Problems. This survey traces the numerous and diverse applications that the notion of promise problems found in the two decades that have elapsed since the invention of the notion.
G. Malewicz and A.L. Rosenberg: A Pebble Game for Internet-Based Computing. Shimon liked elegant models, and would have been interested to see pebble games used to model an Internet-age problem.

Educational essays

Shimon liked opinionated discussions and valued independent opinions that challenge traditional conventions. So we are sure he would have enjoyed reading these essays, and we regret that we cannot have his reaction to them.

G. Even: On Teaching Fast Adder Designs: Revisiting Ladner & Fischer. Shimon would have been very proud of this insightful and opinionated exposition of hardware implementations of the most basic computational task.
O. Goldreich: On Teaching the Basics of Complexity Theory. Shimon would have appreciated the attempt to present the basics of complexity theory in a way that appeals to the naive student.
A.L. Rosenberg: State. Shimon would have supported the campaign, launched in this essay, in favor of the Myhill-Nerode Theorem.

See the book's TOC (and links to all papers).

To the main memorial page for Shimon Even or back to Oded Goldreich's homepage.