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: +97248294166
Fax: +97248221128
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 199697 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, 197980 and 198689.
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 
Reuven BarYehuda 
Alex Biyukov 
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. IT9, No. 2, 1963, pp. 109112.
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. 268279.
S. Even, "Test for Synchronizability of Finite Automata and Variable Length Codes", IEEE Trans. on Infor. Th., Vol. IT10, No. 3, 1964, pp. 185189.
S. Even, "On Information Lossless Automata of Finite Order", IEEE Trans. on Electronic Computers, Vol. EC14, No. 4, 1965, pp. 561569.
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. 215232.
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. 160175.
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. 511523.
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. 400410.
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 393396.
S. Even and R.E. Tarjan, "Network Flow and Testing Graph Connectivity", SIAM J. on Comp., Vol. 4, No. 4, 1975, pp. 507518.
S. Even, A. Itai and A. Shamir, "On the Complexity of Timetable and Integral MultiCommodity Flow Problems", SIAM J. on Comp., Vol. 5, No. 4, 1976, pp. 691703.
S. Even and R.E. Tarjan, "Computing an ST Numbering", Theoretical Comp. Sci., Vol. 2, 1976, pp. 339344.
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. 710719.
S. Even and M. Rodeh, "Economical Encoding of Commas between Strings", Communications of the ACM, Vol. 21, Issue 4, 1978, pp. 315317.
S. Even and Y. Shiloach, "An OnLine EdgeDeletion Problem" J. of the Asso. For Comp. Mach., Vol. 28, No. 1, 1981, pp.14.
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.1624.
R. BarYehuda and S. Even, "A LinearTime Approximation Algorithm for the Weighted Vertex Cover Problem", J. of Algor., Vol. 2, 1981, pp. 198203.
D. Dolev, S. Even and R.M. Karp, "On the Security of PingPong Protocols", Info. and Control, Vol. 55, 1982, pp. 5768.
S. Even, O. Goldreich and Y. Yacobi, "Electronic Wallet". In Advances in Cryptography: Proc. of CRYPTO’83, D. Chaum (ed.), Plenum Press, 1984, pp. 383386.
S. Even and A. Paz, "A Note on Cake Cutting", Disc. App. Math., Vol. 7, 1984, pp. 285296.
S. Even, A. Selman and Y. Yacobi, "The Complexity of Promise Problems with Applications to PublicKey Cryptography", Info. and Control, Vol. 61, No.2, 1984, pp. 159173.
S. Even, O. Goldreich and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Vol. 28, No. 6, 1985, pp. 637647.
R. BarYehuda and S. Even, "A LocalRatio Theorem for Approximating the Weighted Vertex Cover Problem", Annals of Disc. Math., Vol. 25, 1985, pp. 2746.
S. Even and O. Goldreich, "On the power of Cascade Ciphers", ACM Trans. on Comp. Sys., Vol. 3, No. 2, 1985, pp.108116.
S. Even and H. Gazit, "Updating Distances in Dynamic Graphs", Methods of Oper. Res.,Vol. 49, 1985, pp. 371387.
B. Awerbuch and S. Even, "Reliable Broadcast Protocols in Unreliable Networks", Networks, Vol. 16, 1986, pp. 381396.
S. Even, "Secure OffLine Electronic Fund Transfer Between Nontrusting Parties". In Smart Card 2000: The Future of IC Cards, D. Chaum and I. SchaumullerBichl (eds.), North Holland, 1989, pp. 5766.
S. Even and A. Litman, "On the Capabilities of Systolic Systems", Math. Sys. Th., Vol. 27, 1994, pp. 328.
S. Even and S. Rajsbaum, "Unison, Canon and Sluggish Clocks in Networks Controlled by a Synchronizer", Math. Sys. Th., Vol. 28, 1995, pp. 421435.
S. Even, S. Micali and O. Goldreich, "OnLine/OffLine Digital Signatures", J. of Cryptology, Vol. 9, No. 1, 1996, pp. 3567.
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. 447474.
S. Even, A. Litman and P. Winkler, "Computing with Snakes in Directed Networks of Automata", J. of Algor., Vol. 24, 1997, pp. 158170.
S. Even and Y. Mansour, "A Construction of a Pseudorandom Cipher from a Single Pseudorandom Permutation", J. of Cryptology, Vol. 10, 1997, 151161.
S. Even and A. Litman, "Layered Cross Product  A Technique to Construct Interconnection Networks", Networks, Vol. 29, 1997, pp. 219223.
S. Even, G. Itkis and S. Rajsbaum, "On Mixed Connectivity Certificates Algorithms", Theoretical Comp. Sci., Vol. 203, 1998, pp. 253269.
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. 475487.
G. Even and S. Even, "Embedding Interconnection Networks in Grids via the Layered Cross Product", Networks, Vol. 36, No. 2, 2000, pp. 9195.
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. 3546, Springer, 2000.
S. Even, "Area Efficient Layouts of the Batcher Sorting Networks", Networks, Vol. 38, No. 4, 2001, pp. 199208.
S. Even and R. Kupershtok, Layout Area of the Hypercube. An extended abstract appeared in Proc. of the Thirteenth Ann. ACMSIAM Symp. on Discrete Algorithms, 2002, pp. 366371. Click here to download Postscript File