CISE Seminar: Tuvi Etzion, Technion – Israel Institute of Technology
Date: Wednesday, November 20, 2024
Time: 1:00pm – 2:00pm
Location: 665 Commonwealth Ave., CDS 1101
Tuvi Etzion
Professor of Computer Science
Technion – Israel Institute of Technology
The de Bruijn Graph and Its Sequences – the Graph Who Always Reinvent Itself
The de Bruijn graph was defined in 1946 by Nicolaas Govert de Bruijn to count the number of closed sequences in which each binary n-tuple is contained exactly once in a window of length n. The graph and its sequences have found many applications in diverse areas during the last eighty years. Mathematical theory was developed throughout the years for mathematical interest. The first main application application of the graph and its sequences was in space and wireless communication. Interconnection networks which were considered as a model for parallel computations used the graph as a framework for a network with processors to transfer information. The human genome project which was started towards the end of the eighties of the 20th century also used paths of the de Bruijn graph for DNA sequencing which is part of the genome assembly. It was considered in the nineties to built a Viterbi decoder for the Galileo mission of NASA. A two-dimensional generalization of the sequences has found applications in pattern recognition. Finally, today it has a few applications in the rapidly developing area of DNA storage.
The talk will cover the diverse generalizations and applications of the graph throughout the last eighty years. Special attention will be given to its applications to the topics which combine some elements from biology.
Tuvi Etzion was born in Tel Aviv, Israel, in 1956. He received the B.A., M.Sc., and D.Sc. degrees from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1984, respectively. In 1984 he held a position in the Department of Computer Science at the Technion, where he is currently the Bernard Elkin Chair in Computer Science. From 1985 to 1987 he was Visiting Research Professor with the Department of Electrical Engineering — Systems, the University of Southern California, Los Angeles. During the summers of 1990 and 1991 he was visiting Bellcore, Morristown, New Jersey. From 1994 to 1996, he was a Visiting Research Fellow with the Computer Science Department, Royal Holloway University of London, Egham, England. He also had several visits to the Coordinated Science Laboratory at University of Illinois in Urbana-Champaign from 1995 to 1998, two visits to HP Bristol during the summers of 1996 and 2000, a few visits to the Department of Electrical Engineering, University of California at San Diego from 2000 to 2022, several visits to the Mathematics Department at Royal Holloway University of London, from 2007 to 2022, a few visits to the School of Physical and Mathematical Science (SPMS), Nanyang Technological University and to the department of Industrial Systems Engineering and Management the National University of Singapore, Singapore, from 2016 to 2019, and from 2022 to 2024, and a few visits to Jiaotong University, Beijing, from 2017 to 2024. His research interests include applications of discrete mathematics to problems in computer science and information theory, coding theory, coding for storage, and combinatorial designs.
Professor Etzion was an Associate Editor for Coding Theory for the IEEE Transactions on Information Theory from 2006 till 2009. From 2004 to 2009, he was an Editor for the Journal of Combinatorial Designs. From 2011 he is an Editor for Designs, Codes, and Cryptography, and an Editor for Advances of Mathematics in Communications from 2013. He has been an Editor-in-Chief for Journal of Combinatorial Theory, Series A, since 2021.
Faculty Host: Ari Trachtenberg
Student Host: Beste Oztop