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.

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.

- 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.

- 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.

- 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.