Computer Scientists Win Best Paper Award at Turing Centenary Conference

U-M computer science researchers Hadi Katebi, Professor and Associate Chair of CSE Karem A. Sakallah, and Professor Igor Markov have been selected to win a Best Paper Award at The Alan Turing Centenary Conference, which takes place June 22-25, 2012 in Manchester, UK. The conference will be the second major celebration of Alan Turing’s 100th birthday. Alan Turing is viewed as the pivotal figure in the development of Computer Science Theory, Artificial Intelligence, Computer Architecture and Computational Cryptography.

The researchers’ paper, entitled “Graph Symmetry Detection and Canonical Labeling: Differences and Synergies,” describes a faster method for canonical labeling of graphs by first precomputing the graph’s symmetries.

To illustrate how canonical labelling is used, suppose we are given two large molecules, specified as graphs where the vertices represent atoms and edges represent chemical bonds between the atoms. These molecules could be entirely different or could be variants of the same molecule where the atoms are listed in a different order. An important task that can be solved by canonical labeling is to check the equivalence of the two molecules. For example, if one molecule contains an Oxygen atom but the other does not, the task is easy. However, when both molecules contain the same number of atoms of the same types and additionally exhibit many symmetries, the task becomes difficult (see the illustration below). Canonical labeling of graphs orders graph vertices in such a way that if the graphs are equivalent, the ordered graphs match exactly – vertex by vertex and edge by edge.

(Given the example shown, it is interesting to note that Alan Turing also worked out the chemical basis of biological pattern formation.)

Saucy 3 Released

In conjunction with the paper, the researchers have released the source code for a new version of Saucy, a symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetry generators themselves. By avoiding quadratic runtime on large graphs, it improves state-of-the-art runtimes from several days to less than a second. Recent improvements to our algorithm include additional pruning that quickly solves the hard Miyazaki graphs. With the first version released in 2004, Saucy is now at version 3.

Prof. Igor Markov received his Ph.D. in Computer Science from UCLA. His research interests include computers that make computers (software and hardware), secure hardware design, combinatorial optimization with applications to the design, verification and debugging of integrated circuits, as well as in quantum logic circuits. New algorithmic techniques developed by Prof. Markov have been implemented in open-source projects and industry tools, leading to order-of-magnitude improvements in practice. He is a senior member of IEEE and an ACM Distinguished Scientist.

Prof. Karem Sakallah is Associate Chair of Computer Science and Engineering. He received his Ph.D. in Electrical and Computer Engineering from Carnegie Mellon University. His research interests include computer-aided design of electronic systems, Boolean satisfiability, discrete optimization, and hardware and software verification. In 2009, Prof. Sakallah was a co-recipient of the prestigious Computer Aided Verification Award for fundamental contributions to the development of high-performance Boolean satisfiability solvers. His research in satisfiability and hardware verification led to the creation in 2009 of a start-up company, Reveal Design Automation. He is a Fellow of the IEEE.