Wednesday, April 12, 2017
10:30 AM
703 Computer Studies Building
Tim Kopp
University of Rochester
Symmetry Exploitation for Inference in Relational Theories

Relational theories are a powerful representational tool for expressing problems in a vast array of domains from planning and circuit verification to link prediction and social networks. Many systems, such as Markov Logic Networks, theorem provers, model counters, verifiers, and more, use relational theories to express their problem domains. Early algorithms for inference over relational theories relied on viewing the problem at the level of propositional atoms. However, a great deal of recent research has been on lifting these algorithms to exploit the structure that exists in these problems at higher levels. In this work, I give techniques for exploiting the symmetrical structure that is common in problems expressed as relational theories. I give formal definitions of classes of symmetries, algorithms for discovering and exploiting them, and empirical results that speak to the efficacy of these methods.

Reception to follow in the Graduate Student Lounge at 5:00pm