Professor SHIMON EVEN

The George Farkas Chair in Computer Science

Computer Science Department
Technion - Israel Institute of Technology
Technion city, Haifa 32000, Israel.
Phones: Work: +972-4-8294166
Fax: +972-4-8221128
Email: even@cs.technion.ac.il

The Henry Taub Award, 1992. Outstanding Teacher, Technion, 1982 and 1999. Salmon Simon Mani Award for Excellence in Teaching, 1996. ETH Distinguished Lecturer, 1994. Keynote speaker, ESA'95. Invited speaker, CIAC' 97. NJIT Distinguished Lecturer, 1997. Visiting Scientist at Bell Labs, Lucent Technologies 1996-97 and Summer 1998. Program Committee Member, STOC '97. Editorial board of the Journal of Algorithms and Theory of Computer Systems. Visiting Scientist at Bellcore, Morristown NJ, 1990. Chairman of the Computer Science Department, Technion, 1979-80 and 1986-89.


Studies

1959 - B.Sc., Electrical Engineering, Technion - I.I.T.

1961 - M.A., Mathematics - University of North Carolina, Chapel Hill, NC, USA.

1963 - Ph.D., Applied Mathematics - Harvard University, Cambridge, MA, USA.


Former Research Area:
Switching and Automata Theory, Combinatorial Algorithms, Complexity Theory, Cryptography.

Current Research Areas:
Graph Algorithms, Interconnection and Sorting Networks, Circuit Layout.

Some Former Graduate Students:

Baruch Awerbuch
Gideon Ehrlich
Alon Itai
Yehoshua Perl
Yossi Shiloach

Reuven Bar-Yehuda
Fanica Gavril
Oded Kariv
Sergio Rajsbaum
Yacov Yacobi

Alex Biyukov
Oded Goldreich
Aharon Kupershtok
Michael Rodeh

Present Graduate Students

Vladimir Yanovsky

Maria Zapolotsky

Books

Algorithmic Combinatorics, Macmillan, 1973.

Graph Algorithms, Computer Science Press, 1979.

Some Former Publications

S. Even, "Test for Unique Decipherability", IEEE Trans. on Infor. Th., Vol. IT-9, No. 2, 1963, pp. 109-112.

W.L. Eastman, S. Even and I.M. Isaacs, "Bounds for the Optimal Scheduling of n Jobs on m Processors", Management Science, Vol. 11, No. 2, 1964, pp. 268-279.

S. Even, "Test for Synchronizability of Finite Automata and Variable Length Codes", IEEE Trans. on Infor. Th., Vol. IT-10, No. 3, 1964, pp. 185-189.

S. Even, "On Information Lossless Automata of Finite Order", IEEE Trans. on Electronic Computers, Vol. EC-14, No. 4, 1965, pp. 561-569.

A. Lempel , S. Even and I. Cederbaum, "An Algorithm for Planarity Testing of Graphs". In Theory of Graphs, International Symp., Gordon and Breach, 1967, pp. 215-232.

A. Pnueli, A. Lempel and S. Even, "Transitive Orientation of Graphs and Identification of Permutation Graphs", Canadian J. of Math., Vol. 23, No. 1, 1971, pp. 160-175.

F. Commoner, A.W. Holt, S. Even and A. Pnueli, "Marked Directed Graphs", J. of Comp. and Sys. Sci., Vol. 5, No. 5, 1971, pp. 511-523.

S. Even, A. Pnueli and A. Lempel, "Permutation Graphs and Transitive Graphs", J. of the Asso. for Comp. Mach., Vol. 19, No. 3, 1972, pp. 400-410.

S. Even, "An Algorithm for Determining whether the Connectivity of a Graph is at least k", SIAM J. on Comp., Vol. 4, No. 3, 1975, pp 393-396.

S. Even and R.E. Tarjan, "Network Flow and Testing Graph Connectivity", SIAM J. on Comp., Vol. 4, No. 4, 1975, pp. 507-518.

S. Even, A. Itai and A. Shamir, "On the Complexity of Timetable and Integral Multi-Commodity Flow Problems", SIAM J. on Comp., Vol. 5, No. 4, 1976, pp. 691-703.

S. Even and R.E. Tarjan, "Computing an ST Numbering", Theoretical Comp. Sci., Vol. 2, 1976, pp. 339-344.

S. Even and R.E. Tarjan, "A Combinatorial Problem which is Complete in Polynomial Space", J. of the Asso. For Comp. Mach., Vol. 23, No. 4, 1976, pp. 710-719.

S. Even and M. Rodeh, "Economical Encoding of Commas between Strings", Communications of the ACM, Vol. 21, Issue 4, 1978, pp. 315-317.

S. Even and Y. Shiloach, "An On-Line Edge-Deletion Problem" J. of the Asso. For Comp. Mach., Vol. 28, No. 1, 1981, pp.1-4.

S. Even, M. Rodeh and V. Pratt, "Linear Algorithm for Data Compression via String Matching", J. of the Asso. For Comp. Mach., Vol. 28, No. 1, 1981, pp.16-24.

R. Bar-Yehuda and S. Even, "A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem", J. of Algor., Vol. 2, 1981, pp. 198-203.

D. Dolev, S. Even and R.M. Karp, "On the Security of Ping-Pong Protocols", Info. and Control, Vol. 55, 1982, pp. 57-68.

S. Even, O. Goldreich and Y. Yacobi, "Electronic Wallet". In Advances in Cryptography: Proc. of CRYPTO’83, D. Chaum (ed.), Plenum Press, 1984, pp. 383-386.

S. Even and A. Paz, "A Note on Cake Cutting", Disc. App. Math., Vol. 7, 1984, pp. 285-296.

S. Even, A. Selman and Y. Yacobi, "The Complexity of Promise Problems with Applications to Public-Key Cryptography", Info. and Control, Vol. 61, No.2, 1984, pp. 159-173.

S. Even, O. Goldreich and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Vol. 28, No. 6, 1985, pp. 637-647.

R. Bar-Yehuda and S. Even, "A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem", Annals of Disc. Math., Vol. 25, 1985, pp. 27-46.

S. Even and O. Goldreich, "On the power of Cascade Ciphers", ACM Trans. on Comp. Sys., Vol. 3, No. 2, 1985, pp.108-116.

S. Even and H. Gazit, "Updating Distances in Dynamic Graphs", Methods of Oper. Res.,Vol. 49, 1985, pp. 371-387.

B. Awerbuch and S. Even, "Reliable Broadcast Protocols in Unreliable Networks", Networks, Vol. 16, 1986, pp. 381-396.

S. Even, "Secure Off-Line Electronic Fund Transfer Between Nontrusting Parties". In Smart Card 2000: The Future of IC Cards, D. Chaum and I. Schaumuller-Bichl (eds.), North Holland, 1989, pp. 57-66.

S. Even and A. Litman, "On the Capabilities of Systolic Systems", Math. Sys. Th., Vol. 27, 1994, pp. 3-28.

S. Even and S. Rajsbaum, "Unison, Canon and Sluggish Clocks in Networks Controlled by a Synchronizer", Math. Sys. Th., Vol. 28, 1995, pp. 421-435.

S. Even, S. Micali and O. Goldreich, "On-Line/Off-Line Digital Signatures", J. of Cryptology, Vol. 9, No. 1, 1996, pp. 35-67.

Some Publications of the last 5 years

S. Even and S. Rajsbaum, "The Use of a Synchronizer Yields Maximum Computation Rate in Disctributed Networks", Th. of Computing Systems, Vol.30, 1997, pp. 447-474.

S. Even, A. Litman and P. Winkler, "Computing with Snakes in Directed Networks of Automata", J. of Algor., Vol. 24, 1997, pp. 158-170.

S. Even and Y. Mansour, "A Construction of a Pseudorandom Cipher from a Single Pseudorandom Permutation", J. of Cryptology, Vol. 10, 1997, 151-161.

S. Even and A. Litman, "Layered Cross Product --- A Technique to Construct Interconnection Networks", Networks, Vol. 29, 1997, pp. 219-223.

S. Even, G. Itkis and S. Rajsbaum, "On Mixed Connectivity Certificates Algorithms", Theoretical Comp. Sci., Vol. 203, 1998, pp. 253-269.

A. Avior, T. Calamoneri, S. Even, A. Litman and A.L. Rosenberg, "A Tight Layout of the Butterfly", Th. of Computing Systems, Vol. 31, 1998, pp. 475-487.

G. Even and S. Even, "Embedding Interconnection Networks in Grids via the Layered Cross Product", Networks, Vol. 36, No. 2, 2000, pp. 91-95.

S. Even and R. Kupershtok, "Laying Out the Interconnection of the Transpose Bijection", to appear in Th. of Computing Systems.

S. Bhatt, S. Even, D. Greenberg and R. Tayar, "Traversing Directed Eulerian Mazes". In Graph Theoretic Concepts in Computer Science, Proceedings of WG'2000, U. Brandes and D. Wagner (eds), Lecture Notes in Computer Science No. 1928, pp. 35-46, Springer, 2000.

S. Even, "Area Efficient Layouts of the Batcher Sorting Networks", Networks, Vol. 38, No. 4, 2001, pp. 199-208.

S. Even and R. Kupershtok, Layout Area of the Hypercube. An extended abstract appeared in Proc. of the Thirteenth Ann. ACM-SIAM Symp. on Discrete Algorithms, 2002, pp. 366-371. Click here to download Postscript File