Theoretical Computer Science

by Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alan L.

• ISBN13: 9783540328803
• ISBN10: 3540328807
• Format: Paperback
• Copyright: 2006-04-15
• Publisher: Springer-Verlag New York Inc

Summary

This volume commemorates Shimon Even, one of founding fathers of Computer Science in Israel, who passed away on May 1, 2004. This Festschrift 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. To make these research contributions accessible to a wide range of researchers - rather than merely to experts in the area - the contributions have been refereed both by experts and by non-experts. The contributions are of three different types, reflecting three main scientific activities of Shimon: original research, technical surveys, and educational essays.

Table of Contents

The Reduced Automata Technique for Graph Exploration Space Lower Bounds	1	(26)
Pierre Fraigniaud
David Ilcinkas
Sergio Rajsbaum
Sebastien Tixeuil
Concurrent Zero-Knowledge with Timing, Revisited	27	(61)
Oded Goldreich
Fair Bandwidth Allocation Without Per-Flow State	88	(23)
Richard M. Karp
Optimal Flow Distribution Among Multiple Channels with Unknown Capacities	111	(18)
Richard Karp
Till Nierhoff
Till Tantau
Parceling the Butterfly and the Batcher Sorting Network	129	(14)
Ami Litman
An Application Intersection Marketing Ontology	143	(21)
Xuan Zhou
James Geller
Yehoshua Perl
Michael Halper
How to Leak a Secret: Theory and Applications of Ring Signatures	164	(23)
Ronald L. Rivest
Adi Shamir
Yael Tauman
A New Related Message Attack on RSA	187	(9)
Oded Yacobi
Yacov Yacobi
A Tale of Two Methods	196	(22)
Reuven Bar-Yehuda
Dror Rawitz
Dinitz' Algorithm: The Original Version and Even's Version	218	(23)
Yefim Dinitz
Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems	241	(13)
Christian Glaβer
Alan L. Selman
Liyu Zhang
On Promise Problems: A Survey	254	(37)
Oded Goldreich
A Pebble Game for Internet-Based Computing	291	(22)
Grzegorz Malewicz
Arnold L. Rosenberg
On Teaching Fast Adder Designs: Revisiting Ladner & Fischer	313	(35)
Guy Even
On Teaching the Basics of Complexity Theory	348	(27)
Oded Goldreich
State	375	(24)
Arnold L. Rosenberg
Author Index	399