Faster Symmetry Discovery using Sparsity of Symmetries

Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. However, existing tools suffer quadratic runtime in the number of symmetries explicitly returned and are of limited use on very large, sparse, symmetric graphs. This paper introduces a new symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetries themselves. By avoiding quadratic runtime on large graphs, it improves state-of-the-art runtimes from several days to less than a second.

Speaker Details

Karem A. Sakallah (S’76–M’81–SM’92–F’98) received the B.E. degree in electrical engineering from the American University of Beirut, Beirut, Lebanon, in 1975, and the M.S.E.E. and Ph.D. degrees in electrical and computer engineering from Carnegie Mellon University, Pittsburgh, PA, in 1977 and 1981, respectively.In 1981, he was with the Department of Electrical Engineering at Carnegie Mellon University as a Visiting Assistant Professor. From 1982 to 1988, he was with the Semiconductor Engineering Computer-Aided Design Group at Digital Equipment Corporation in Hudson, MA, where he headed the Analysis and Simulation Advanced Development Team. Since September 1988, he has been with the University of Michigan, Ann Arbor, as a Professor of Electrical Engineering and Computer Science. From September 1994 to March 1995, he was with the Cadence Berkeley Laboratory in Berkeley, CA, on a six-month sabbatical leave. He has authored or coauthored more than 200 papers and has presented seminars and tutorials at many professional meetings and various industrial sites. His current research interests include the area of computer-aided design, Boolean satisfiability, discrete optimization, and hardware and software verification.Since 2006, he has been a member of an advisory board for the Qatar Foundation for Education, Science, and Community Development. During the 2007/2008 academic year he was on sabbatical leave at Carnegie Mellon University’s Qatar campus with a mission to help the Qatar Foundation establish Al-Khwarizmi Institute for Computer and Information Science and Engineering.Dr. Sakallah was an Associate Editor of the IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS from 1995 to 1997 and has served on the program committees of the International Conference on Computer-Aided Design, Design Automation Conference, and the International Conference of Computer Design as well as numerous other workshops. He is currently an Associate Editor of the IEEE TRANSACTIONS ON COMPUTERS. He is a fellow of the IEEE and a member of the ACM and Sigma Xi.

Date:
Speakers:
Karem Sakallah
Affiliation:
University of Michigan