BEGIN:VCALENDAR CALSCALE:GREGORIAN PRODID:-//Ximian//NONSGML Evolution Calendar//EN VERSION:2.0 BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:m5085btk0e6eqq4u181scv22k4@google.com SEQUENCE:4 LAST-MODIFIED:20091028T110927 SUMMARY:Jonathan Hellwig - Suche nach häufigen Sequenzmustern STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081114T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081114T130000 TRANSP:OPAQUE DESCRIPTION:Das hier untersuchte Problem wird als Häufige-Sequenzen Problem bezeichnet und besteht darin in einer Menge von Sequenzen (Sequenz-Datenbank) alle (Sub-)Sequenzen\, die öfter als ein vorher bestimmter Schwellenwert vorkommen\, zu finden. Dabei wird gezählt in wie vielen Sequenzen der Datenbank eine (Sub-)Sequenz vorkommt unabhängig davon\, wie oft diese in den einzelnen Sequenzen der Datenbank vorkommt.\nIm gängigen Verständnis ist eine Sequenz eine Menge von Elementen in einer festen Reihenfolge\, z. B. ist ein Wort eine Sequenz von Buchstaben. In dem hier untersuchten Problem bestehen die Elemente der Sequenzen wiederum aus Mengen von Elementen\, die Itemsets genannt werden.\nWeiterhin wird hier auf der Gesamtzahl aller Items\, die in den Itemsets einer Sequenz vorkommen können\, eine Ordnung angenommen\, nach der die Items in einem Itemset angeordnet sind. In einem Itemset tritt jedes Item höchstens einmal auf.\nWenn man aus einer Sequenz Items löscht\, ohne die Reihenfolge der übrigen Items zu verändern erhält man eine Subsequenz dieser Sequenz. Werden alle Items eines Itemsets gelöscht\, so kann es ganz weggelassen werden.\nEs wird gezeigt\, dass das Häufige-Sequenzen Entscheidungsproblem NP-vollständig ist. Von verschiedenen Algorithmen\, die zur Lösung des Häufige-Sequenzen Problem entwickelt wurden\, wird der SPAM-Algorithmus näher vorgestellt und gezeigt\, dass dieser Algorithmus polynomial delay erfüllt\, d. h. zwischen jeder Ausgabe einer häufigen Sequenz vergeht Polynomzeit in der Größe der Eingabe.\nIn weiteren Untersuchungen sollen Varianten des Häufige-Sequenzen Problems betrachtet werden\, z. B. als Parametrisierungs- und Optimierungsprobleme. CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:5uouct4127gpnl3fe7d2ja4fjo@google.com LAST-MODIFIED:20091022T135602 DESCRIPTION:For every relational structure B\, the (non-uniform) constraint satisfaction problem associated to B\, CSP(B)\, is the following computational problem: given a relational structure A\, is there a homomorphism from A to B?. The complexity of the problem CSP(B) varies depending on the election of the structure B. In the last few years much effort has been invested in the project of classifying the computational complexity of CSP(B)\, for every B. An useful tool in this study has been the consideration of the logics that can express CSP(B). Perhaps the best illustration of this approach is the fact that a good number of the tractable cases of the problem identified so far can be explained\, in an uniform way\, as those CSP(B) definable in Datalog. During the first half of the talk we shall survey the connection between definability in several fragments of Datalog and the existence of obstruction sets. During the second half of the talk we shall focus on those structures with an obstruction set consisting only of trees\, where we shall present some recent results. SUMMARY:Víctor Dalmau (Barcelona\, Spain) - Constraint Satisfaction\, Logic\, and Dualities STATUS:CONFIRMED PRIORITY:5 DTSTART:20081017T090000Z DTEND:20081017T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:3lnedfgc37uqu50s873s7702lo@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Holger Dell - Algebraic Reductions (in the Coloured Tutte Polynomial) STATUS:CONFIRMED PRIORITY:5 DTSTART:20080425T090000Z DTEND:20080425T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:vcaeldhefsita5m9bhgv7ps4fk@google.com LAST-MODIFIED:20091028T111038 SUMMARY:Holger Dell (HU Berlin) - Complexity and Approximability of the Cover Polynomial STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071116T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071116T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:ert61vendukbkra62615t2b0lo@google.com LAST-MODIFIED:20091028T110936 SUMMARY:Marc Thurley - SAT Solvers and Width-Bounded Resolution STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081031T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081031T130000 TRANSP:OPAQUE DESCRIPTION:Modern SAT solvers have seen huge efficiency gains over the last decade. Being well optimized implementations of the DPLL algorithm they are widely used in many applications. Among these are\, for example\, microporocessor verification and bounded model checking\, which often require the solution of inputs with hundreds of thousands of variables.\n\nThe fact that SAT solvers are indeed able to handle such situations apparently conflicts with the well known intractability of the SAT problem. Recent approaches by Beame\, Kautz\, Sabharwal and Bacchus\, Hertel\, Pitassi and Van Gelder have tried to get a proof complexity theoretic account of this phenomenon.\n\nIn a different direction we propose a more algorithmic view\, relating efficient solvability by a SAT solver to bounded width resolution. Among other things this enables us to show that SAT solvers are able to handle CNF formulas of bounded treewidth in polynomial time.\n\nThis is joint work with Albert Atserias. CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ATTENDEE;CN=Mitarbeiterseminar Logik in der Informatik;RSVP=FALSE; PARTSTAT=ACCEPTED;ROLE=REQ-PARTICIPANT;X-UID=0:mailto: 28c074ohvkqngj13v90i72kb3s@group.calendar.google.com CREATED:20091022T135602 UID:taqriudu6nnt5rhkq9m4oj28ks@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Frederic Dorn (HU Berlin) - Catalan structure and dynamic programming STATUS:CONFIRMED PRIORITY:5 DTSTART:20071026T090000Z DTEND:20071026T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:qkadcbeq4mj58lebbtbom5d2q8@google.com SEQUENCE:3 LAST-MODIFIED:20091028T110908 SUMMARY:Moritz Müller (Freiburg) - Lower bounds for gap amplifications STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081212T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081212T130000 TRANSP:OPAQUE DESCRIPTION:Recently Fortnow and Santhanam showed that NP-hard problems do not have so-called distillations unless the polynomial hierarchy collapses. This lemma has proven useful in many respects. For example Bodlaender\, Downey\, Fellows and Hermelin based on it a method to exclude polynomial kernelizations for parameterized problems. The talk presents refinements of the lemma making it useful also in other respects. Concerning PCP systems the lemma can be used to establish lower bounds on the number of new variables that have to be introduced in gap amplifications for SAT. Another application concerns Buhrmans and Hitchcocks recent lower bound on the density of NP-hard problems. CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-993726071.861 SEQUENCE:5 LAST-MODIFIED:20091028T110032 SUMMARY:Daniel Kirsten - Distanzdesertautomaten und das Sternhöhenproblem DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091029T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091029T130000 TRANSP:OPAQUE CLASS:PUBLIC ATTENDEE;CUTYPE=UNKNOWN;ROLE=REQ-PARTICIPANT;PARTSTAT=ACCEPTED;RSVP=FALSE; CN=Holger Dell:mailto:dell@informatik.hu-berlin.de END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:a6qvqr7ofaeftpn3okqbip6ius@google.com SEQUENCE:3 LAST-MODIFIED:20091028T111024 SUMMARY:Dietrich Kuske (Universität Leipzig) - Hamiltonsche Pfade in automatische Graphen und verwandte Probleme STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080124T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080124T130000 TRANSP:OPAQUE DESCRIPTION:Abstract:\nHamiltonsche Pfade in automatische Graphen und verwandte Probleme\n(gemeinsame Arbeit mit Markus Lohrey)\n\nAutomatische Graphen sind gegeben durch zwei endliche Automaten\, die\ndie Menge der Knoten bzw. die Menge der Kanten erkennen (hierfuer wird\nein synchroner Zweiband-Automat verwendet). Daher stellen sie eine\nEinschraenkung der rekursiven Graphen dar\, bei denen Turingmaschinen\nverwendet werden.\n\nWie in der Theorie der rekursiven Graphen ueblich fragen wir\, wie sich\nEigenschaften des automatischen Graphen in den Automaten\nwiederspiegeln. Dabei zeigen wir:\n\n- die Existenz eines Hamiltonpfades in einem planaren automatischen\n Graphen von beschraenktem Grad ist $\\Sigma_11$-vollstaendig (fuer\n rekursive Graphen wurde dies von Hirst und Harel gezeigt)\n\n- die Existenz eines unendlichen Astes in einem automatischen\n Nachfolgerbaum ist $\\Sigma_11$-vollstaendig (fuer rekursive\n Nachfolgerbaeume ist dies ein klassisches Ergebnis von Kleene)\n\n- die Existenz einer unendlichen Clique in einem automatischen\n Graphen\, eines unendlichen Astes in einem automatischen Ordnungsbaum\n bzw. einer ko-unendlichen Ueberdeckung in einem automatischen\n bipartiten Graphen sind entscheidbar (diese Fragen sind\n $\\Sigma_11$-vollstaendig fuer rekursive Graphen). Diese\n Entscheidbarkeitsergebnisse werden erzielt\, indem wir ein geeignetes\n Fragment der Logik zweiter Stufe betrachten und dessen\n Entscheidbarkeit zeigen.\n CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1229176622.912 SEQUENCE:3 LAST-MODIFIED:20091022T135602 DESCRIPTION:Klassische Approximierbarkeit und parametrische Komplexitätstheorie verfolgen beide das Ziel\, schwere (NP-harte) Probleme handhabbar zu machen. Nichtsdestotrotz existieren Probleme wie das disjunkte Kreiseproblem für gerichtete Graphen\, die sich diesen Versuchen widersetzen. Ich definiere parametrische Approximierbarkeit\, um solch \"hartnäckige\" Probleme zu attackieren. Ich werde den Begriff der fpt Approximationsalgorithmen einführen und Varianten dieser Definition vorstellen. Neben ersten Approximierbarkeits- und Nichtapproximierbarkeitsergebnissen für diese neue Klasse von Approximationsalgorithmen werde ich darauf eingehen\, dass das disjunkte Kreiseproblem als ein natürliches\, schweres Problem fpt approximierbar ist. Schließlich werde ich die Ergebnisse auf eine Variante des disjunkten Pfadeproblems in gerichteten Kreisen übertragen und weitere effizient lösbare Spezialfälle dieses Problems vorstellen. SUMMARY:Magdalena Grüber - Parametrische Approximierbarkeit PRIORITY:5 DTSTART:20090605T090000Z DTEND:20090605T111500Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:d1bjadbm0ofuafi8ntc9tjbk68@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Dániel Marx\, Budapest University of Technology and Economics - Movement Problems STATUS:CONFIRMED PRIORITY:5 DTSTART:20080611T090000Z DTEND:20080611T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:av3cho3fs5lpe4iia59qabt3rg@google.com LAST-MODIFIED:20091022T135602 DESCRIPTION:Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet\, auf endlichen Strukturen\, ist bekanntermaßen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen\, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen\, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen\, wie Constraint Satisfaction Problems (CSP):\n\nIm Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern\, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen\, dass Datalog auf linearen Ordnungen (auch dichte und diskrete\, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist.\n\nFür die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen\, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme\, die sich ohne Rekursion lösen lassen.\n\nEin Transfer unserer Methoden auf CSPs zeigt\, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen\, wie bei Datalog. SUMMARY:Götz Schwandtner (Mainz) - Datalog on Infinite Structures LOCATION:Erwin Schrödinger-Zentrum\, Raum 1'303 STATUS:CONFIRMED PRIORITY:5 DTSTART:20081024T090000Z DTEND:20081024T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:pqnj2aroejrqfrb8vumsraq1rc@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Tomer Kotek\, Technion\, Israel - Connection matrices of numeric graph invariants STATUS:CONFIRMED PRIORITY:5 DTSTART:20080507T090000Z DTEND:20080507T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1796002777.177 SEQUENCE:1 LAST-MODIFIED:20091022T135602 SUMMARY:Berit Grußien - Polynomial Time Algorithms for Constraint Satisfaction Problems PRIORITY:5 DTSTART:20090710T090000Z DTEND:20090710T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:q3b5kt22top4mbct2ftel0tup8@google.com LAST-MODIFIED:20091028T110847 SUMMARY:Johannes Fichte - Programmieren mit Strukturen STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090213T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090213T130000 TRANSP:OPAQUE DESCRIPTION:Abstract State Machines (kurz ASMs) sind ein prominenter Vertreter für die Spezifikation und Verifikation von Hard- und Software. In der Logik stellen sie für die Beschreibung von Strukturklassen ein neues\, interessantes Berechnungsmodell zur Verfügung. In dieser Arbeit werden ASMs als eine Art Programmiersprache für Strukturen aufgefasst. Dabei wurden die Programme so entworfen\, dass natürliche Einschränkungen in der Syntax und Semantik das Einfangen von klassischen Komplexitätsklassen auf endlichen\, geordneten Strukturen erlaubt. Im Vortrag wird anhand von altbekannten Logiken gezeigt welche ASM-Programme die Komplexitätsklassen LOGSPACE und PTIME einfangen. CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:7aoaf961h1kckfijvvqtaq5n5s@google.com SEQUENCE:4 LAST-MODIFIED:20091022T135602 DESCRIPTION:Arc consistency is a basic reasoning technique in constraint satisfaction for efficiently detecting unsatisfiable instances\, in a sound but incomplete way. Although incomplete in general\, it is known that arc consistency solves the constraint satisfaction problem on certain constraint languages. In this talk\, I will give an overview of a line of work that studies arc consistency and extensions thereof. In particular\, we attempt to characterize\, for each algorithm\, the constraint languages on which the algorithm works. For many of these algorithms\, algebraic characterizations of the solvable languages can be obtained\; these highly facilitate understanding the power\, limitations\, and robustness of these algorithms.\n\nJoint work with Berit Grussien\, Manuel Bodirsky\, and Victor Dalmau. SUMMARY:Hubie Chen - Arc Consistency and Friends (Universitat Pompeu Fabra\, Barcelona) STATUS:CONFIRMED PRIORITY:5 DTSTART:20090417T090000Z DTEND:20090417T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1034434594.340 LAST-MODIFIED:20091022T135602 SUMMARY:Nicole Schweikardt - Additions-invariantes FO und reguläre Sprachen PRIORITY:5 DTSTART:20090911T090000Z DTEND:20090911T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:52p15r4c4htc8qk2tk43fl1bk0@google.com SEQUENCE:2 LAST-MODIFIED:20091028T111017 SUMMARY:Thore Husfeldt (University of Lund\, Schweden) - Trimmed Moebius inversion and graphs of bounded degree STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080208T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080208T130000 TRANSP:OPAQUE DESCRIPTION:Joint work with Andreas Bjoerklund\, Petteri Kaski\, Mikko Koivisto\nTo appear at STACS 2008\nhttp: //www.cs.lu.se/home/Thore_Husfeldt/papers/trimmedmoebius.pdf CLASS:PUBLIC ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de ATTENDEE;CUTYPE=UNKNOWN;ROLE=REQ-PARTICIPANT;PARTSTAT=ACCEPTED;RSVP=FALSE; CN=Mitarbeiterseminar Logik in der Informatik:mailto: 28c074ohvkqngj13v90i72kb3s@group.calendar.google.com END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:0nkkkoedgddrr66dsb62ca4b94@google.com LAST-MODIFIED:20091022T135602 SUMMARY:László Egri - Linear Datalog ≠ Symmetric Datalog STATUS:CONFIRMED PRIORITY:5 DTSTART:20090402T090000Z DTEND:20090402T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:roearl69m0v97htsm1cakcou3g@google.com LAST-MODIFIED:20091028T111033 SUMMARY:Bastian Laubner (HU Berlin) - Mapping Mathematics with Theory Graphs STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071130T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071130T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de ATTENDEE;CN=Holger Dell;RSVP=FALSE;PARTSTAT=ACCEPTED;ROLE=REQ-PARTICIPANT: mailto:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1577533850.382 SEQUENCE:2 LAST-MODIFIED:20091022T135602 DESCRIPTION:Interval graphs are the intersection graphs of intervals on the reals. In this talk\, I will outline my proof that fixed-point logic with counting (FP+C) captures polynomial-time on the class of all finite interval graphs. As will be shown\, any interval graph possesses structural properties that allow to construct in FP+C a canonical copy of the graph with linearly ordered vertices. By the Immerman-Vardi Theorem\, all PTIME properties can then be defined by a fixed-point formula on this ordered copy. The result is part of a wider project to determine capturing results for graph classes defined by forbidden induced subgraphs. SUMMARY:Bastian Laubner - Capturing PTIME on interval graphs DTSTART:20091023T090000Z DTEND:20091023T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-365779121.187 SEQUENCE:2 LAST-MODIFIED:20091022T135602 SUMMARY:Mark Weyer - Games\, unravellings\, tree decompositions\, ... and consistencies for CSP PRIORITY:5 DTSTART:20090717T090000Z DTEND:20090717T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:5itfrh7ia3aun9oakcsthekabc@google.com SEQUENCE:2 LAST-MODIFIED:20091028T111043 SUMMARY:Johann A. Makowsky (Technion IIT\, Haifa) - Why is the chromatic polynomial a polynomial? STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071108T150000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071108T170000 TRANSP:OPAQUE CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:lhhdqgfitg9fh221586daqhgls@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Berit Grußien - A Quadratic Running Time Algorithm for Majority Constraints STATUS:CONFIRMED PRIORITY:5 DTSTART:20080627T090000Z DTEND:20080627T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO: CREATED:20091022T135602 UID:KOrganizer-1152744305.796 SEQUENCE:2 LAST-MODIFIED:20091028T110103 SUMMARY:Matthias Mnich - Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091113T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091113T130000 TRANSP:OPAQUE DESCRIPTION:We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above tight lower bound\, which is stated as follows. For a set V of variables and set C of constraints \"u is between v and w\"\, decide whether there is a bijection from V to the set {1\,...\,|V|} satisfying at least |C|/3 + k of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph \"Invitation to Fixed-Parameter Algorithms\". CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:iv062njvot7lj83j4fr622hka4@google.com LAST-MODIFIED:20091028T110901 SUMMARY:Siamak Tazari - Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090123T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090123T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:5v43fe1qle1jl8pl4j5f5uk124@google.com LAST-MODIFIED:20091028T110913 SUMMARY:Andrei Krokhin (Durham) - Maximum constraint satisfaction and supermodular optimisation on lattices STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081205T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081205T130000 TRANSP:OPAQUE DESCRIPTION:The maximum constraint satisfaction problem (Max CSP)\nprovides a unified framework which can express\nmany combinatorial optimisation problems including Max Cut and Max\nk-Sat. An instance of Max CSP consists of a\ncollection of weighted constraints on overlapping sets of variables\,\nand the goal is to find values for the variables that\nmaximise the total weight of simultaneously satisfied constraints. We\nwill consider the problem of determining how exactly\nthe complexity and approximability of Max CSPs depend on the type of\nconstraints allowed in instances. We will discuss\nthe recently discovered strong link between tractability of Max CSPs\nand supermodular functions defined on products of lattices\, and\npresent some classification results based on this link. CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1033924799.120 LAST-MODIFIED:20091117T152845 SUMMARY:Magnus Wahlström - Kernelizability of Min Ones CSPs DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091120T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091120T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:3 DESCRIPTION:The Min Ones Constraint Satisfaction Problems unify problems like Vertex Cover\, Hitting Set and Nearest Codeword\, allowing them to be studied in one framework. An instance (F\,k) of Min Ones CSP(Gamma) consists of a formula F\, given as a conjunction of constraints\, and a number k\, and the question is whether F has a satisfying assignment with at most k true variables. The constraint types are taken from a fixed\, finite set Gamma of boolean relations\, and the complexity of the problem depends on the set Gamma. For example\, if Gamma={(x or y)}\, then we get the problem Vertex Cover\, while another Gamma gives us the more expressive Min Ones 3-SAT problem.\n\nStarting from the well-known kernelizable cases of d-Hitting Set\, it is natural to ask whether the problem always admits polynomial kernelizations. As we show\, this is not the case. We give a property we refer to as mergeability\, and show that if every relation in Gamma is mergeable\, then the problem has a kernel of O(k^(d+1)) vertices\, where d is the maximum arity of a relation in Gamma. On the other hand\, if Gamma contains at least one relation which is not mergeable\, then we use the framework of Fortnow and Santhanam\, and Bodlaender et al.\, to show that the problem admits no polynomial kernelization unless the polynomial hierarchy collapses (excepting the cases of Min Ones CSP(Gamma) which are completely solvable in polynomial time). ATTENDEE;CUTYPE=UNKNOWN;ROLE=REQ-PARTICIPANT;PARTSTAT=ACCEPTED;RSVP=FALSE; CN=Holger Dell:mailto:dell@informatik.hu-berlin.de END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:mail@holger-dell.de CREATED:20091022T135602 UID:KOrganizer-460400107.942 LAST-MODIFIED:20091022T135602 SUMMARY:Anne Pilchowski - Quantitativer Vergleich zweier Arten von Erreichbarkeitsgraphen von Intervall-Petrinetzen PRIORITY:5 DTSTART:20090529T090000Z DTEND:20090529T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:mail@holger-dell.de CREATED:20091022T135602 UID:KOrganizer-1272553881.525 SEQUENCE:1 LAST-MODIFIED:20091022T135602 DESCRIPTION:Partitionsfunktionen stammen ursprünglich aus der statistischen Physik und sind die fundamentalen Größen mit denen sich Phasenübergänge in komplexen physikalischen Systemen beschreiben lassen. Viele Partitionsfunktionen lassen sich als gewichtete Homomorphismenprobleme auf Graphen darstellen wodurch ihre enge Verwandschaft mit einer Reihe wichtiger Graphinvarianten offenbar wird. Beispiele hierfür sind die Zahl der stabilen Knotenmengen eines Graphen und die Zahl der k-Färbungen.\n\nDie Untersuchung der Komplexität dieser Funkionen\, erlaubt also eine vereinheitlichende Beschreibung der Komplexität vieler wichtiger Berechnungsprobleme der statistischen Physik und Graphentheorie. In den vergangenen Jahren sind eine Reihe von Arbeiten zu diesem Thema erschienen\, die den Kenntnisstand sukzessive verallgemeinert haben. In meinem Vortrag werde ich eines der derzeit allgemeinsten Resultate vorstellen. SUMMARY:Marc Thurley - Die Komplexität von Partitionsfunktionen PRIORITY:5 DTSTART:20090619T090000Z DTEND:20090619T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:vnmolrt3mpornkbcl3oo750pnc@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Kord Eickmeyer - Algorithmische Rekonstruktion phylogenetischer Bäume STATUS:CONFIRMED PRIORITY:5 DTSTART:20080606T090000Z DTEND:20080606T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:i2rrfuob84hakvmhpn1kob8j9g@google.com SEQUENCE:3 LAST-MODIFIED:20091028T110924 SUMMARY:Eva Jackolis - Algorithmische Lerntheorie und Definierbarkeit STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081121T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081121T130000 TRANSP:OPAQUE DESCRIPTION:Maschinelle Lernverfahren werden in verschiedenen Bereichen wie Data Mining oder der Künstlichen Intelligenz eingesetzt. Dabei werden für verschiedene Lernprobleme unterschiedliche Algorithmen entworfen\, die meist auf statistischen Methoden beruhen. Ein Lernproblem unter vielen ist die Konzeptlernaufgabe bei der unbekannte Konzepte anhand von Beispielen möglichst genau erlernt werden soll. Im Rahmen der algorithmischen Lerntheorie wird das Konzeptlernen vorgestellt. Der Parameter der Vapnik-Chervonenkis-Dimension wird hierbei eine wichtige Rolle spielen. Denn mithilfe der VC-Dimension können Komplexitätsaussagen hinsichtlich der Konzeptklassen getroffen werden\, und es wird sich ferner herausstellen\, dass mithilfe der VC-Dimension effizient erlernbare Konzeptklassen charakterisiert werden können. Als Abschluss des Vortrages wird das Ergebnis vorgestellt\, dass die VC-Dimension auf der Klasse der Bäume beschränkt ist. CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:9f466a5bldm5j336sn0gih9tn0@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Johannes Fichte - SAT Solving auf Formeln beschränkter Baumweite STATUS:CONFIRMED PRIORITY:5 DTSTART:20080418T090000Z DTEND:20080418T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:k3gt2g9k52st2nd8gi92nb4uf8@google.com LAST-MODIFIED:20091028T111048 SUMMARY:Martin Grohe (HU Berlin) - Relational Joins and Fractional Edge Covers STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071102T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20071102T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:g7pdm48m316nuu1rdgvorvnl18@google.com LAST-MODIFIED:20091028T110932 SUMMARY:Mark Weyer - Boundedness of MSO least fixed points over words is decidable STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081107T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081107T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:mlnpe8i58e1gv89urnmnetrtpo@google.com LAST-MODIFIED:20091028T110853 SUMMARY:Sebastian Müller - Beweissysteme mit Advice STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090130T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20090130T130000 TRANSP:OPAQUE DESCRIPTION:Motiviert durch einen Beweis eines starken Karp-Lipton Kollapses in beschränkter Arithmetik haben Cook und Krajicek 2007 aussagenlogische Beweissysteme mit Advice definiert. Die Beweislängen solcher Systeme korrespondieren\, analog zu den klassischen Systemen von Cook und Reckhow\, mit Kollapskonsequenzen der Polynomiellen Hierarchie.\n\nIch werde einen Überblick über die bisherigen Ergebnisse auf diesem Gebiet geben. Insbesondere werden wir uns der Frage der (p)-Optimalität solcher Systeme innerhalb ihrer eigenen Klasse\, wie auch Simulationseigenschaften gegenüber schwächeren Beweissystemen annehmen. Danach werden wir uns noch kurz mit der (schwierigeren) Frage der Beschränktheit der Beweislängen solcher Systeme beschäftigen. CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:dsapf5i9h1p7od0e0af3270qc0@google.com LAST-MODIFIED:20091022T135602 DESCRIPTION:In this talk I will overview the very recent results obtained by Daniel Marx\, Barry O'Sullivan and myself. In particular our main technical result states that given a graph $G$\, terminals $s$ and $t$\, and a parameter $k$\, there is an FPT algorithm that transforms $G$ into another graph $G^*$ of treewidth depending on $k$ that retains all minimal $s-t$ separators of size at most $k$. Moreover\, the subgraphs of $G$ and $G^*$ induced by each of these separators are isomorphic.\n\nWe observe that for many constrained separation problems the above result enables transformation from the original instance to the instance with a restricted treewidth and that this allows to show the fixed-parameter tractability of these problems by applying the well known Courcelle's theorem. Moreover\, using the transformation proposed by Reed et al.\, this technique can be extended to the constrained bipartization problems.\n\nTo demonstrate the power of the above methodology\, we resolve a number of open problems in the area of parameterized complexity. For example\, we show that the problem of checking existence of an independent set of size exactly $k$ whose removal makes the graph bipartite is FPT thus resolving an open problem posed in 2001 by Diaz et al (MFCS 2001).\n\nThe above overview will be preceded by a very brief introduction to the area of parameterized complexity and an intuitive description of the Courcelle's Theorem in order to make the talk accessible to a general Theoretical Computer Science audience that is not necessary familiar with this machinery.\n\nThe paper presenting the results covered by the talk is available at:\nhttp: //arxiv.org/PS_cache/arxiv/pdf/0902/0902.3780v1.pdf\n SUMMARY:Igor Razgon - Treewidth reduction for constraint separation and bipartization problems STATUS:CONFIRMED PRIORITY:5 DTSTART:20090424T090000Z DTEND:20090424T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-8511662.260 SEQUENCE:1 LAST-MODIFIED:20091022T135602 DESCRIPTION:Wir führen eine alternative Charakterisierung der Komplexität von Graphen ein und zeigen deren Äquivalenz zur klassischen Baumweite. Über eine Rekursionsformel für diese Charakterisierung entwickeln wir dann einen rekursiven Algorithmus zur exakten Baumweitenberechnung.\n\nFür praktische Anwendungen sind Heuristiken zur Bestimmung von Schranken für die Baumweite jedoch deutlich besser geeignet\, da ansonsten enorm hohe Laufzeiten zu erwarten sind. Wir betrachten einige ausgewählte Ergebnisse von umfangreichen Berechnungen auf Zufallsgraphen sowie verschiedenen praktischen Graphinstanzen. SUMMARY:Lukas Moll - Praktische Baumweitenberechnung PRIORITY:5 DTSTART:20090703T090000Z DTEND:20090703T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:ksh3jiq2u8oc08beraqgarmfao@google.com SEQUENCE:3 LAST-MODIFIED:20091028T110918 SUMMARY:Etienne Lozes (Cachan\, France) - A reachable star STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081128T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20081128T130000 TRANSP:OPAQUE DESCRIPTION:Separation Logic is both an assertion language that may express some properties of memory states\, and a Hoare-like proof system for programs manipulating pointers\, the former being intensively used in the latter. This logic has been actively popularized by the \"London Massive\" team (Peter O'Hearn\, Hongseok Yang\, Cristiano Calcagno\, Dino Di Stefano).\n\nIn the first part of my presentation\, I will present a personnal\, brief survey on pointer programs verification\, and introduce the essentials of the separation logic approach. The second part will be more personnal and technical\, I will focus on the assertion language and review some of our recent results on decidability and expressiveness issues.\n\nOn the decidability side\, I will present decidable classes that are not (yet) handled by the automatic tools developed by the \"London Massive\" team : data-aware logics\, and unrestricted first-order quantification. These results allow to prove\, for instance\, that merging two ordered lists gives an ordered list.\n\nOn the expressiveness side\, I will explain the roles played by the two specific separation logic connectives : separating conjunction and magic-wand (joint work with Stéphane Demri and Remi Brochenin). It will be presented in particular that the magic-wand subsumes the separating conjunction\, and provides an expressive power equivalent to *full* second-order logic. Of other interest is that separating conjunction alone fits into *monadic* second-order logic\, the strict inclusion being still a conjecture\, although it is known that it encodes MSO over words. CLASS:PUBLIC END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-2103692823.226 SEQUENCE:1 LAST-MODIFIED:20091022T135602 SUMMARY:Mark Weyer - Baumweitechniken für FO^k PRIORITY:5 DTSTART:20090626T090000Z DTEND:20090626T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:clogca6dnrjkviidakuhcna884@google.com LAST-MODIFIED:20091028T111028 SUMMARY:Mark Weyer (HU Berlin) - Classifying configurations' complexities STATUS:CONFIRMED PRIORITY:5 DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080118T110000 DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080118T130000 TRANSP:OPAQUE CLASS:PUBLIC SEQUENCE:1 END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z ORGANIZER;CN=Holger Dell:MAILTO:dell@informatik.hu-berlin.de CREATED:20091022T135602 UID:KOrganizer-1702660997.396 SEQUENCE:2 LAST-MODIFIED:20091022T135602 DESCRIPTION:We introduce a simple\, yet very effective\, technique to obtain (sub)-exponential fixed-parameter algorithms on graphs of bounded local treewidth or excluding a fixed graph H as a minor\, such as planar graphs\, bounded-genus graphs\, or linklessly embeddable graphs. Our algorithm has the curious running time of O*(2^\\sqrt{k log n})\, where n is the size of the input and k is the number of vertices or edges in the solution. For *any* c > 0\, this running time is at most O(2^(k/c) + n^c). It follows that: any problem that admits our technique (i) can be solved in O*((1+\\epsilon)^k)-FPT time for any \\epsilon > 0\; (ii) can be solved in true Subexponential FPT time if it admits any subexponential kernel. Our technique can be directly applied to a variety of problems\, such as Steiner tree\, (directed) subgraph isomorphism\, (directed) subgraph with a property\, (directed) longest path\, vertex cover\, independent set\, dominating set\, and many more. Also\, for some problems one can still apply some variation of our technique\; we demonstrate this on the example of the maximum-leaf spanning tree problem. SUMMARY:Siamak Tazari - A New Technique for Subexponential FPT\nAlgorithms in Minor-Closed Graph Classes PRIORITY:5 DTSTART:20090612T090000Z DTEND:20090612T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VEVENT DTSTAMP:20091022T134353Z CREATED:20091022T135602 UID:3ggdtghhij71v4g2aho7fp5mio@google.com LAST-MODIFIED:20091022T135602 SUMMARY:Isolde Adler - Compactness of tree-width and other hypergraph invariants STATUS:CONFIRMED PRIORITY:5 DTSTART:20080516T090000Z DTEND:20080516T110000Z TRANSP:OPAQUE END:VEVENT BEGIN:VTIMEZONE TZID:/softwarestudio.org/Tzfile/Europe/Berlin X-LIC-LOCATION:Europe/Berlin BEGIN:STANDARD TZNAME:CET DTSTART:19701031T020000 RRULE:FREQ=YEARLY;INTERVAL=1;BYDAY=-1SU;BYMONTH=10 TZOFFSETFROM:+0200 TZOFFSETTO:+0100 END:STANDARD BEGIN:DAYLIGHT TZNAME:CEST DTSTART:19700328T030000 RRULE:FREQ=YEARLY;INTERVAL=1;BYDAY=-1SU;BYMONTH=3 TZOFFSETFROM:+0100 TZOFFSETTO:+0200 END:DAYLIGHT END:VTIMEZONE END:VCALENDAR