Wolfgang Pauli Institute (WPI) Vienna 


Home  WPI in a nutshell  Practical Information  Events  People  WPI Projects 
Login  Thematic Programs  Pauli Fellows  Talks  Research Groups 
 

Fomin Fedor V.  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Fri, 2. Sep 11, 9:00 
"Protrusions in graphs and their applications"  
A protrusion in a graph is a subgraph of constant treewidth that can be separated from the graph by removing a constant number of vertices. We discuss combinatorial properties of graphs implying existence of large protrusions and give a number of algorithmic applications of protrusions.  

Marquis Pierre  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Fri, 2. Sep 11, 11:00 
"A Few Words about Knowledge Compilation"  
My talk will be about knowledge compilation, a research topic studied in AI for more than twenty years, and which is concerned with preprocessing some pieces of information in order to improve some tasks of interest, computationally speaking. In this talk, after an introduction to knowledge compilation, I will focus on two important points: the definition of compilable problems (roughly, those for which computational improvements via preprocessing can be "guaranteed") and the design of a knowledge compilation map (a multicriteria evaluation of representation languages which can be used as target languages for knowledge compilation).  

Yeo Anders  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Fri, 2. Sep 11, 14:00 
"Simultaneously Satisfying Linear Equations Over F_2: Parameterized Above Average"  
In this talk we will mainly be considering the parameterized problem MaxLin2AA. In MaxLin2AA, we are given a system of variables x_1,... ,x_n and equations of the form x_{i_1}*x_{i_2}*... *x_{i_r} = b, where {x_{i_1},x_{i_2},...,x_{i_r}} is a subset of {1,2,...,n} and all x_i and b belong to {1, 1}. Furthermore each equation has a positive integral weight, and we want to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). In this talk we begin by (briefly) explaining what it means to parameterize a problem above average and why this seems a natural parameterization. We will motivate why MaxLin2AA is of interest and outline how to obtain a kernel with at most O(k^2 log k) variables, which solves an open problem of Mahajan et al. (2006). Finally we will mention a number of open problems and conjectures.  

Biere Armin  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Fri, 2. Sep 11, 16:30 
"Preprocessing and Inprocessing Techniques in SAT"  
SAT solvers are used in many applications in and outside of Computer Science. The success of SAT is based on the use of good decision heuristics, learning, restarts, and compact data structures with fast algorithms. But also efficient and effective encoding, preprocessing and inprocessing techniques are important in practice. In this talk we give an overview of old and more recent inprocessing and preprocessing techniques starting with ancient pure literal reasoning and failed literal probing. Hyperbinary resolution and variable elimination are more recent techniques of this century. We discuss blockedclause elimination, which gives a nice connection to optimizing encodings and conclude with our recent results on unhiding redundancy fast.  
Note:  

Jansen Bart  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Sat, 3. Sep 11, 9:00 
"Kernelization for a Hierarchy of Structural Parameters"  
There are various reasons to study the kernelization complexity of nonstandard parameterizations. Problems such as Chromatic Number are NPcomplete for a constant value of the natural parameter, hence we should not hope to obtain kernels for this parameter. For other problems such as Long Path, the natural parameterization is fixedparameter tractable but is known not to admit a polynomial kernel unless the polynomial hierarchy collapses. We may therefore guide the search for meaningful preprocessing rules for these problems by studying the existence of polynomial kernels for different parameterizations. Another motivation is formed by the Vertex Cover problem. Its natural parameterization admits a small kernel, but there exist refined parameters (such as the feedback vertex number) which are structually smaller than the natural parameter, for which polynomial kernels still exist; hence we may obtain better preprocessing studying the properties of such refined parameters. In this survey talk we discuss recent results on the kernelization complexity of structural parameterizations of these important graph problems. We consider a hierarchy of structural graph parameters, and try to pinpoint the best parameters for which polynomial kernels still exist.  

Chakraborty Sourav  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Sat, 3. Sep 11, 11: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.  

Lokshtanov Daniel  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Sat, 3. Sep 11, 14:00 
"Generalization and Specialization of Kernelization"  

Fellows Michael R.  Vienna University of Technology, 1040 Vienna, Gußhausstr. 2529, EI 9 Hlawka Hörsaal, ground floor  Sun, 4. Sep 11, 9:30 
"Kernelization and the Larger Picture of Practical Algorithmics, in Contemporary Context "  
The natural relationship between Parameterized Complexity and heuristics has been a subject of papers and talks since the beginnings of parameterized complexity, and has been especially recognized within the WorKer kernelization community. In the Journal of Computer and System Sciences (January 2011) celebrating Richard Karp's 2008 Koyoto Prize, and elsewhere, Karp proposes a general program, closely related to the standard FPT technique of iterative compression, as a structured approach to heuristic algorithm design, for problems in computational molecular biology and genetics. This talk will discuss Karp's general program in light of the parameterized complexity framework, and survey the contemporary context of programmatic thinking about the deployment of mathematics to serve practical computing, in which preprocessing (kernelization) has, of course, both a central and a leveraged role.  

Impressum  webmaster [Printable version] 