In this self-contained talk I will describe few combinatorial results that were initiated by problems from several application areas. These results include the following: (1) the use of the Cycle Lemma in deriving statistics about several classes of trees (this includes, as a start, a very simple proof for the Catalan number of binary trees), (2) a new characterization of tree medians, (3) an algorithm for generation of permutations, (4) a result about the volume of discrete spheres, and (5) a combinatorial problem that resulted in a paper with Paul Erdős.

About Shmuel Zaks

Shmuel Zaks received his BSc (cum laude) and MSc in Mathematics from the Technion, Israel, in 1971 and 1972, and PhD in Computer Science from the University of Illinois at Urbana-Champaign, USA, in 1979. He then joined the Department of Computer Science in the Technion, Haifa, Israel, where he is a Professor and the incumbent of the Joan Callner-Miller Chair in Computer Science. He has been a visiting profesor in numerous universities (including MIT, La Sapienza University and University of l’Aquila (Italy), University of Liverpool (UK), Hong Kong University of Science & Technology, Carleton University (Canada), and Universidad Rey Juan Carlos), and research centers (including IBM Research Centers in New York and Zurich, INRIA Sophia Antipolis and IRISA (France) and Create-Net (Italy)). Professor Zaks was on the program committees of over 30 conferences, chair of DISC 1992 and SIROCCO 2007, member of the steering committees of DISC and SIROCCO, and chair of the steering committee of DISC. He is the author of over 150 journal and conference papers, and supervised over 20 graduate and post-doctoral students. He has been working on several Theoretical Computer Science topics: Graph and Combinatorial Algorithms, Discrete Mathematics and Combinatorics, Distributed Computing, ATM Networks, and Theory of Networking.

His research in recent years concentrates on Algorithmic studies concerning Optical Networks; these include design and analysis of algorithms, complexity and parameterized complexity, approximability, and on-line algorithms. During his visit to IMDEA he plans to pursue his studies on optical networks, and in particular to collaborate on various algorithmic issues in the context of several on-going networking projects of IMDEA.

Personal Site

This event will be conducted in English