Lecture: Mathias Niepert

Mathias Niepert, IU Computer Science Department, will give the following talk: On Implication Problems for Disjunctive Constraints.

Wednesday, January 28
4:00 p.m.
Chemistry 033

Abstract:
Implication problems occur in many areas of computer science. Examples include, of course, logic, but also database systems (constraints), data mining (association rules), and reasoning under uncertainty (conditional independence). We provide a general framework for implication problems based on the observation that many can be reduced to an implication problem for additive constraints on specific classes of real-valued functions. Furthermore, we provide inference systems and properties of classes of real-valued functions which imply the soundness and completeness of these systems. We present computational complexity results for an important class of implication problems for which a finite axiomatization exists. We also derive properties of classes of real-valued functions that imply the non-existence of finite, complete axiomatizations.