Upcoming events

What knowledge bases know (and what they don't)

Simon Razniewski
Joint Lecture Series
04 Oct 2017, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
Knowledge bases such as Wikidata YAGO or the Google Knowledge Graph are increasingly used in applications like entity resolution structured search or question answering. The correctness of these knowledge bases is generally well understood and at the center of attention in automated construction techniques. About their completeness in contrast most knowledge is anecdotal: Completeness is usually correlated with popularity of topics yet understanding whether a knowledge base has complete information on a specific topic is often difficult.

In this talk I will introduce the problem of understanding the completeness of knowledge bases. I will present three approaches: (i) data-inherent inferences about completeness using association rule mining (ii) extraction of cardinality information from text sources and (iii) various tools we developed to help knowledge base curators and consumers in mapping and understanding the completeness of knowledge bases.

Discrimination in Algorithmic Decision Making: From Principles to Measures and Mechanisms

Muhammad Bilal Zafar
Max Planck Institute for Software Systems
SWS Student Defense Talks - Thesis Proposal
09 Oct 2017, 4:00 pm - 5:00 pm
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111
Algorithmic decision making systems are increasingly being used to assist or even replace human decision making in a large number of application domains. These systems rely on complex learning methods and vast amounts of training data to optimize prediction accuracy. The accuracy of these systems has been shown to even surpass human accuracy in some applications. However there is a growing concern that algorithmic decision making systems can lead even in the absence of intent to discriminatory outcomes.

Incorporating nondiscrimination goals into the design of algorithmic decision making systems (or classifiers) has proven to be quite challenging. These challenges arise mainly due to (i) the computational complexities involved in incorporating nondiscrimination goals and (ii) inadequacy of existing measures to computationally capture discrimination in certain situations. The goal of this thesis is to tackle these two problems.

First we aim to design mechanisms to incorporate two existing measures of discrimination disparate treatment and disparate impact into the design of well-known classifiers. To this end we introduce a novel and intuitive mechanism of decision boundary covariance. This mechanism can be included into the formulation of any convex boundary-based classifier in the form of convex constraints without increasing the classifier's complexity. It also allows for fine-grained control over the degree of (non)discrimination often at a small cost in terms of accuracy.

Second we propose alternative measures of discrimination that can avoid shortcomings of existing measures in certain situations. Our first proposed measure disparate mistreatment is useful in situations when the validity of historical decisions in the training data can be ascertained. The remaining two measures preferred treatment and preferred impact are useful in situations when feature and class distributions of different groups subject to the decision making are significantly different and can additionally help reduce the cost of nondiscrimination. We extend our decision boundary covariance mechanism and incorporate the newly proposed nondiscrimination measures into the formulations of convex boundary-based classifiers this time as convex-concave constraints. The resulting formulations can be solved efficiently using recent advances in convex-concave programming.

Fine-Grained Complexity: Hardness for a Big Data World

Karl Bringmann
Joint Lecture Series
08 Nov 2017, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
For many computational problems we know some polynomial time algorithm say in quadratic time but it is open whether faster algorithms exist. In a big data world it is essential to close this gap: If the true complexity of the problem is indeed quadratic then it is intractable on data arising in areas such as DNA sequencing or social networks. On such data essentially only near-linear time algorithms are feasible. Unfortunately classic hardness assumptions such as P!=NP are too coarse to explain the gap between linear and quadratic time.

Fine-grained complexity comes to the rescue by providing conditional lower bounds via fine-grained reductions from certain hard core problems. For instance it allowed us to rule out truly subquadratic algorithms for the Longest Common Subsequence problem (used e.g. in the diff file comparison tool) assuming a certain strengthening of P!=NP. In this talk we will further discuss applications to Edit Distance Subset Sum and RNA Folding.

Fundamental Algorithmic Problems and Challenges in Dynamical and Cyber-Physical Systems

Joël Ouaknine
Max Planck Institute for Software Systems
Joint Lecture Series
06 Dec 2017, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
Dynamical and cyber-physical systems whose continuous evolution is subject to differential equations permeate vast areas of engineering physics mathematics and computer science. In this talk I consider a selection of fundamental algorithmic problems for such systems such as reachability invariant synthesis and controllability. Although the decidability and complexity of many of these problems are open some partial and conditional results are known occasionally resting on certain number-theoretic hypotheses such as Schanuel's conjecture. More generally the study of algorithmic problems for dynamical and cyber-physical systems draws from an eclectic array of mathematical tools ranging from Diophantine approximation to algebraic geometry. I will present a personal and select overview of the field and discuss areas of current active research.