Tel-Aviv University - Computer Science Colloquium
Sunday, June 13, 14:15-15:15
at 14:00 For the Butterfly of $N$ input/output {\em vertices} we present a layout on the square grid of area $\frac{1}{2}N^2 + o(N^2)$. A lower bound of the same order is proved. The encompassing rectangle which defines the area is $45\degr$ slanted w.r.t.\ the grid axes and the input/output vertices are not on the boundary of this rectangle.
For the Butterfly of $M$ input/output {\em edges} we present a layout of area $\frac{1}{2}M^2 + o(M^2)$. In this layout the input edges are on the l.h.s.\ of the upright encompassing rectangle and the output edges are on its r.h.s.\ Again this is also a lower bound.
Both layouts are scalable. i.e. if one allocates for each switch a square of $a \times a$ area, the layouts remain of area $\frac{1}{2}N^2 + o(N^2)$ and $\frac{1}{2}M^2 + o(M^2)$, respectively, where the value of $a$ affects only the $o(N^2)$ and $o(M^2)$ terms. Both layouts are free of knock-knees.
(Joint work with Ye. Dinitz, R. Kupershtok and M. Zapolotsky)
Bio:
Shimon Even is a graduate of the EE department, in the Technion, 1959, and a Ph.D. from Harvard University, 1963. He was a faculty member at Harvard, in the Math department of the Technion, in the Weizmann Institute, where he started the first program leading to a degree in computer science in Israel (1969), and is a professor of computer science in the Technion since 1974. He was twice the Dean of the computer science faculty in the Technion.
Shimon was on the team of 3 which designed Elbit 100 in 1965. It was the first commercial minicomputer in the world and the first successful commercial computer made in Israel.
Shimon taught at TAU as well, during the years 1970-75. He started there the courses on Algorithmic Combinatorics (A and B), and the course on automata and formal languages.
His research interests are in algorithms (which he has been teaching since 1967), interconnection networks and their layouts and cryptography (which he has been teaching since 1981). He published 2 books, authored or coauthored over 100 papers and 9 patents. He supervised tens of graduate students including 12 doctorates, and currently is supervising 4 doctorate students.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html