Theoretical Computer Science

1. Front Matter

   PDF

2. The Reduced Automata Technique for Graph Exploration Space Lower Bounds

   • Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, Sébastien Tixeuil

   Pages 1-26

3. Concurrent Zero-Knowledge with Timing, Revisited

   • Oded Goldreich

   Pages 27-87

4. Fair Bandwidth Allocation Without Per-Flow State

   • Richard M. Karp

   Pages 88-110

5. Optimal Flow Distribution Among Multiple Channels with Unknown Capacities

   • Richard Karp, Till Nierhoff, Till Tantau

   Pages 111-128

6. Parceling the Butterfly and the Batcher Sorting Network

   • Ami Litman

   Pages 129-142

7. An Application Intersection Marketing Ontology

   • Xuan Zhou, James Geller, Yehoshua Perl, Michael Halper

   Pages 143-163

8. How to Leak a Secret: Theory and Applications of Ring Signatures

   • Ronald L. Rivest, Adi Shamir, Yael Tauman

   Pages 164-186

9. A New Related Message Attack on RSA

   • Oded Yacobi, Yacov Yacobi

   Pages 187-195

10. A Tale of Two Methods

    • Reuven Bar-Yehuda, Dror Rawitz

    Pages 196-217

11. Dinitz’ Algorithm: The Original Version and Even’s Version

    • Yefim Dinitz

    Pages 218-240

12. Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems

    • Christian Glaßer, Alan L. Selman, Liyu Zhang

    Pages 241-253

13. On Promise Problems: A Survey

    • Oded Goldreich

    Pages 254-290

14. A Pebble Game for Internet-Based Computing

    • Grzegorz Malewicz, Arnold L. Rosenberg

    Pages 291-312

15. On Teaching Fast Adder Designs: Revisiting Ladner & Fischer

    • Guy Even

    Pages 313-347

16. On Teaching the Basics of Complexity Theory

    • Oded Goldreich

    Pages 348-374

17. State

    • Arnold L. Rosenberg

    Pages 375-398

18. Back Matter

    PDF

On May 1, 2004, the world of theoretical computer science su?ered a stunning loss: Shimon Even passed away. Few computer scientists have had as long, s- tained, and in?uential a career as Shimon. Shimon Even was born in Tel-Aviv in 1935. He received a B.Sc. in Elect- cal 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 insti- tions: the Weizmann Institute and the Technion. In 1969 he established at the Weizmann the ?rst computer science education program in Israel, and led this program for ?ve 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.

• Computer
• NP-completeness
• algorithms
• approximation algorithms
• automata
• complexity
• complexity theory
• compute
• computer science
• fair bandwidth allocation
• graph algorithms
• graph exploration
• max-flow algorithms
• ring signatures
• theoretical computer science
• algorithm analysis and problem complexity

From the reviews:

"Shimon Even was … considered a superb teacher that had great influence on his listeners and students. Overall, the book is a very fitting tribute to the legacy of Shimon Even. … The editors attempted to a wide range of research contribution in the first part of the book accessible to a wide range of researchers by using both experts and nonexperts as reviewers. They succeeded in this attempt. The papers are accessible to anybody with some background in theoretical computer science." (Burkhard Englert, Computing Reviews, December, 2006)

• Weizmann Institute of Science, Rehovot, Israel

  Oded Goldreich

• Dept. of Computer Science, Univ. of Massachusetts, Amherst, USA

  Arnold L. Rosenberg

• University at Buffalo, USA

  Alan L. Selman

Policies and ethics