Events

Upcoming events

On Rationality of Nonnegative Matrix Factorization

James Worrell
University of Oxford
SWS Distinguished Lecture Series
02 May 2017, 10:30 am - 1:30 pm
Saarbrücken building E1 5, room 002
simultaneous videocast to Kaiserslautern building G26, room 112
The nonnegative rank of a nonnegative m x n matrix M is the smallest number d such that M can be written as the product M = WH of a nonnegative m x d matrix W and a nonnegative d x n matrix H.  The notions of nonnegative rank and nonnegative matrix factorization have a wide variety of applications including bioinformatics computer vision communication complexity document clustering and recommender systems. A longstanding open problem is whether when M is a rational matrix the factors W and H in a rank decomposition M=WH can always be chosen to be rational.  In this talk we resolve this problem negatively and discuss consequences of this result for the computational complexity of computing nonnegative rank.

This is joint work with Dmitry Chistikov Stefan Kiefer Ines Marusic and Mahsa Shirmohammadi.

Digital Knowledge: From Facts to Rules and Back

Daria Stepanova
MPI-INF - D5
Joint Lecture Series
03 May 2017, 12:15 pm - 3:15 pm
Saarbrücken building E1 5, room 002
Knowledge Graphs (KGs) are huge collections of primarily encyclopedic facts which are automatically extracted from the Web. Prominent examples of KGs include Yago DBPedia Google Knowledge Graph. We all use KGs when posing simple queries like "capital of Saarland" to Google. Internally such queries are translated into machine readable representations which are then issued against the KG stored at the backend of the search engine. Instead of syntactically relevant Web pages the actual answer to the above query "Saarbrücken" is then output to the user as a result.

However since KGs are automatically constructed they are often inaccurate and incomplete. In this talk I will investigate how deductive and inductive reasoning services could be used to address these crucially important issues. More specifically first I will present an approach for repairing inconsistencies in hybrid logical systems that can be built on top of KGs. Second I will describe a method for inductive learning of rules with exceptions from KGs and show how these are applied for deriving missing facts.

Digital Knowledge: From Facts to Rules and Back

Daria Stepanova
MPI-INF - D5
Joint Lecture Series
03 May 2017, 12:15 pm - 3:15 pm
Saarbrücken building E1 5, room 002
Knowledge Graphs (KGs) are huge collections of primarily encyclopedic facts which are automatically extracted from the Web. Prominent examples of KGs include Yago DBPedia Google Knowledge Graph. We all use KGs when posing simple queries like "capital of Saarland" to Google. Internally such queries are translated into machine readable representations which are then issued against the KG stored at the backend of the search engine. Instead of syntactically relevant Web pages the actual answer to the above query "Saarbrücken" is then output to the user as a result.

However since KGs are automatically constructed they are often inaccurate and incomplete. In this talk I will investigate how deductive and inductive reasoning services could be used to address these crucially important issues. More specifically first I will present an approach for repairing inconsistencies in hybrid logical systems that can be built on top of KGs. Second I will describe a method for inductive learning of rules with exceptions from KGs and show how these are applied for deriving missing facts.

Recent events

Securing enclaves with formal verification

Andrew Baumann
Microsoft Research, Redmond
SWS Colloquium
26 Apr 2017, 4:00 pm - 6:00 pm
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 112
Moore's Law may be slowing but perhaps as a result other measures of processor complexity are only accelerating. In recent years Intel's architects have turned to an alphabet soup of instruction set extensions such as MPX SGX MPK and CET as a way to sell CPUs through new security features. SGX in particular promises powerful security: user-mode "enclaves" protected against both physical attacks and privileged software adversaries. To achieve this SGX's designers implemented an isolation mechanism approaching the complexity of an OS microkernel in the ISA using an inscrutable mix of silicon and microcode. However while CPU-based security mechanisms are harder to attack they are also harder to deploy and update and already a number of significant flaws have been identified. Worse the availability of new SGX features is dependent on the slowing deployment of new CPUs.

In this talk I'll describe an alternative approach to providing SGX-like enclaves: decoupling the underlying hardware mechanisms such as memory encryption address-space isolation and attestation from a privileged software monitor which implements enclaves. The monitor's trustworthiness is guaranteed by a machine-checked proof of both functional correctness and high-level security properties. The ultimate goal is to achieve security that is equivalent or better than SGX while decoupling enclave features from the underlying hardware.

Comprehensive deep linking for mobile apps

Oriana Riva
Microsoft Research, Redmond
SWS Colloquium
10 Apr 2017, 10:30 am - 12:30 pm
Kaiserslautern building G26, room 112
simultaneous videocast to Saarbrücken building E1 5, room 005
Web deep links are instrumental to many fundamental user experiences such as navigating to one web page from another bookmarking a page or sharing it with others. Such experiences are not possible with individual pages inside mobile apps since historically mobile apps did not have links equivalent to web deep links. Mobile deep links introduced in recent years still lack many important properties of web deep links. Unlike web links mobile deep links must be explicitly built into apps by developers cover a small number of predefined pages and are defined statically to navigate to a page for a given link but not to dynamically generate a link for a given page. Another problem with state-of-the-art deep links is that once exposed they are hard to discover thus limiting their usage in both first and third-party experiences.

In this talk I'll give an overview of two new deep linking mechanisms that address these problems. First we implemented an application library that transparently tracks data- and UI-event-dependencies of app pages and encodes the information in links to the pages; when a link is invoked the information is utilized to recreate the target page quickly and accurately. Second using static and dynamic analysis we prototyped a tool that can automatically discover links that are exposed by an app; in addition it can discover many links that are not explicitly exposed. The goal is to obtain links to every page in an app automatically and precisely.

Graph Decomposition Problems in Image Analysis

Björn Andres
D2
Joint Lecture Series
05 Apr 2017, 12:15 pm - 3:15 pm
Saarbrücken building E1 5, room 002
A large part of image analysis is about breaking things into pieces. Decompositions of a graph are a mathematical abstraction of the possible outcomes. Breaking things (like an image itself) into pieces in a controlled way is hard. Optimization problems whose feasible solutions define decompositions of a graph are a mathematical abstraction of this task. One example is the correlation clustering problem whose feasible solutions relate one-to-one to the decompositions of a graph and whose objective function puts a cost or reward on neighboring nodes ending up in distinct components. This talk shows work by the Combinatorial Image Analysis research group that applies this problem and proposed generalizations to diverse image analysis tasks. It sketches the algorithms introduced by the group for finding feasible solutions for large instances in practice solutions that are often superior in the metrics of application-specific benchmarks. Finally it sketches the algorithm introduced by the group for finding lower bounds and points to new findings and open problems of polyhedral geometry in this context.

Archive