BDD/ZDD-based enumeration techniques and real-life applications

Professor
Graduate School of Information Science and Technology
Hokkaido University
Sapporo, Japan

 

Webpage

Tutorial - Thursday, 28 September 2017 at 16:45 in room BC 420

Abstract:

BDD (Binary Decision Diagram) is a classical data structure for representing a Boolean function. BDD-based algorithms were developed mainly for VLSI logic design in early 1990s. ZDD (Zero-suppressed BDD) is a variant of BDD, customized for representing a set of combinations, often appear in solving combinatorial problems. BDDs and ZDDs have become more widely known since D. Knuth intensively discussed them in his famous series of books in 2009. Although a quarter of a century has passed since the original idea of BDD-based operations by R. Bryant, there are still many interesting research topics ongoing. One of the most important topics is a fast algorithm of constructing a ZDD which enumerates all the paths in a given graph structure, presented by Knuth. This work is important because many kinds of practical problems are efficiently solved by some variations of this algorithm.

In this talk, I will give an overview of the brief history and the basic techniques on BDDs/ZDDs. We then look over some recent research topics to show "the power of enumeration" for solving real-life applications.

About the speaker:

Shin-ichi Minato is a Professor at Large-Scale Knowledge Processing Laboratory, Graduate School of Information Science and Technology, Hokkaido University. His research topics include efficient representations and manipulation algorithms for large-scale discrete structure data. He received the B.E., M.E., and D.E. degrees in Information Science from Kyoto University in 1988, 1990, and 1995, respectively. He had been working at NTT Laboratories since 1990 until March 2004. He was a Visiting Scholar at Computer Science Department of Stanford University in 1997. He was a Senior Researcher of NTT Network Innovation Laboratories in 1999. From 1999 to 2000, he concurrently served as Visiting Lecturer at Shonan-Fujisawa Campus of Keio University.

He joined Hokkaido University as an Associate Professor at Algorithm Laboratory in 2004, and has been a Full Professor since October 2010. He has been leading the  Large-Scale Knowledge Processing Laboratory since 2015. Prof. Minato is currently the Research Director of JSPS KAKENHI(S) Discrete Structure Manipulation System Project and will hold this position until 2020. He also holds several adjunct researcher and visiting professor positions at numerous Japanese institutions.

He is a senior member of  IEICE, a senior member of IPSJ, and a member of IEEE and JSAI.