Wolfgang Pauli Institute (WPI) Vienna 


Home  WPI in a nutshell  Practical Information  Events  People  WPI Projects 
Login  Thematic Programs  Pauli Fellows  Talks  Research Groups 
Chakraborty Sourav  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, "Kontaktraum", 6th floor  Mon, 1. Jan 01, 0:00 
"Property Testing: Sublinear Algorithms for Promise Problems"  
Deciding weather a graph is $k$colorable is an NPcomplete problem and hence solving this problem is expected to be hard. But if we are given a promise that the graph is either $k$colorable of "far from being $k$coloarble", can we make some intelligent deductions "quickly"? Property testing deals with these kind of questions, where the goal is to solve some promise problems. The efficiency of an algorihtm is measured by the number of input bits that are read. In many cases there are algorithms that can correctly answer with high probability by looking at a tiny fraction (sometimes even constant) of the input bits. In the past two decades this area has been at the forefront of research in theoretical computer science  we will take at look at it.  

Antoniou Grigoris/Bikakis Antonis  Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom von Neumann, ground floor, access through the courtyard  Tue, 12. Apr 11, 17:00 
Distributed Reasoning about Context  
Interest in formalizations of contextual information and intercontextual information flow has steadily increased over the past few years. Intuitively, a multicontext system describes the information available in a number of contexts (such as people, agents, databases, modules) and specifies the information flow between those contexts through mapping rules associating concepts used by different contexts. The imperfect nature of context in key application areas, such as ambient intelligence, mobile and social computing, and the special characteristics of the entities that possess and share the available context information in such systems, render contextual reasoning a very challenging task. In the main part of this talk, we propose a solution by extending multicontext systems with simple ruleased nonmonotonic feature: local defeasible theories, defeasible mappings, and a preference relation on the system contexts. We present this novel representation model, describe an algorithm for distributed query evaluation, give a number of formal properties, and present an argumentation semantics. We also describe specific application scenarios in ambient intelligence and social computing and outline their implementation and evaluation.  

Verheij Bart  Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard  Tue, 31. May 11, 14:00 
The logic of argumentation: what next?  
Argumentation is a process in which arguments and counterarguments are put forward, thereby supporting and attacking positions on the basis of premises. In recent years, the study of the logic of argumentation has flourished, resulting in good understanding of the formal and computational properties of the proposed logical models. Moreover, the logic of argumentation has found applications in medicine, law, critical thinking, software design and artificial intelligence. In this talk, I will give a personal perspective of the developments in the interdisciplinary study of argumentation, and explain what I believe to be important next steps.  

Koivisto Mikko  Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard  Tue, 14. Jun 11, 14:00 
Exponentialtime algorithms for Bayesian networks  
Bayesian networks, also called belief networks, is an extensively studied formalism for representing multivariate probability distributions. A Bayesian network consists of a directed acyclic graph, DAG for short, and local functions that specify the probability distribution of a variable given its parent variables in the DAG. Besides statistical dependencies, Bayesian networks are often used for representing causal relationships among a set of variables. I will talk about two hard computational problems associated with Bayesian networks: inference and structure learning. The inference problem is that of computing a marginal distribution by summing over most of the variables in a given Bayesian network; the fastest known exact algorithms run in time exponential in the treewidth of the underlying graph. In the structure learning problem the task is to find a DAG that maximizes the fit to a given set of data records on the variables, formalized by a decomposable objective function; the acyclicity constraint renders the learning problem NP_hard. The fastest known algorithms resemble the dynamic programming treatment of the traveling salesman problem.  

Liedloff Mathieu  Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard  Tue, 14. Jun 11, 15:00 
A Fast Exact Algorithm for L(2,1)Labeling of Graphs  
In this talk I will present an exponential time algorithm to solve the L(2,1)labeling problem in graphs. Given a graph, an L(2,1)labeling is a mapping from its vertex set into the nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices at distance 2 are different. The aim is to minimize the span of the labeling, i.e. the maximum label used by the labeling.  

Gatterbauer Wolfgang  TU Wien, Institut für Informationssysteme, Meetingroom Menger, Favoritenstraße 911, Stg. 3. 3. Stock, 1040 Wien  Fri, 9. Mar 12, 14:30 
Rules of Thumb for Information Acquisition Rules of Thumb for Information Acquisition from Large and Redundant Data  
We develop an abstract model of information acquisition from redundant data. We assume a random sampling process from data which contain information with bias and are interested in the fraction of information we expect to learn as function of (i) the sampled fraction (recall) and (ii) varying bias of information (redundancy distributions). We develop two rules of thumb with varying robustness. We first show that, when information bias follows a Zipf distribution, the 8020 rule or Pareto principle does surprisingly not hold, and we rather expect to learn less than 40% of the information when randomly sampling 20% of the overall data. We then analytically prove that for large data sets, randomized sampling from powerlaw distributions leads to “truncated distributions” with the same powerlaw exponent. This second rule is very robust and also holds for distributions that deviate substantially from a strict power law. We further give one particular family of powerlaw functions that remain completely invariant under sampling. Finally, we validate our model with two large Web data sets: link distributions to web domains and tag distributions on delicious.com.  

James Delgrande  Seminarroom Gödel (Favoritenstrasse 911, ground floor, access through courtyard  Mon, 5. Nov 12, 16:00 
Revising Horn Theories  
This talk addresses belief revision where the underlying logic is that governing Horn clauses. It proves to be the case that classical (AGM) belief revision doesn't immediately generalise to the Horn case. In particular, a standard construction based on a total preorder over possible worlds may violate the accepted (AGM) postulates. Conversely, Horn revision functions in the obvious extension to the AGM approach are not captured by total preorders over possible worlds. We address these difficulties by first restricting the semantic construction to ``well behaved'' orderings; and second, by augmenting the revision postulates by an additional postulate. This additional postulate is redundant in the AGM approach but not in the Horn case. In a representation result we show that these two approaches coincide. Arguably this work is interesting for several reasons. It extends AGM revision to inferentiallyweaker Horn theories; hence it sheds light on the theoretical underpinnings of belief change, as well as generalising the AGM paradigm. Thus, this work is relevant to revision in areas that employ Horn clauses, such as deductive databases and logic programming, as well as areas in which inference is weaker than classical logic, such as in description logic.  

Impressum  webmaster [Printable version] 