BEGIN:VCALENDAR
PRODID:-//K Desktop Environment//NONSGML libkcal 4.3//EN
VERSION:2.0
X-WR-CALNAME:LIFsem
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
END:STANDARD
END:VTIMEZONE
BEGIN:VTIMEZONE
TZID:Europe/Berlin
X-LIC-LOCATION:Europe/Berlin
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
END:STANDARD
END:VTIMEZONE
BEGIN:VTIMEZONE
TZID:/softwarestudio.org/Tzfile/Europe/Berlin
X-LIC-LOCATION:Europe/Berlin
BEGIN:STANDARD
TZNAME:CET
DTSTART:19701030T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:19700327T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20110114T092445Z
UID:d20f6fc6-b119-450d-b935-9d227b5a0d28
LAST-MODIFIED:20110114T092445Z
DESCRIPTION:We consider the representation of iterations of finite 
 languages using special nondeterministic finite automata. We define a 
 special equivalence relation for two iterating languages. Using these 
 representation and equivalence relation\, we formulate the hypothesis 
 about the connection between this problem and the P=NP question.
SUMMARY:Boris Melnikov (Togliatti State University\, Russia) - 
 Nondeterministic finite automata and the P=NP question
DTSTART;TZID=Europe/Paris:20110121T110000
DTEND;TZID=Europe/Paris:20110121T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:5
DTSTAMP:20120104T194616Z
UID:ef5df072-47aa-4e8d-98cb-7ba5fcdd3fe9
LAST-MODIFIED:20120104T194616Z
DESCRIPTION:The computational problem graph isomorphism asks whether 
 there is an adjacency and non-adjacency preserving bijection between the 
 vertices of two input graphs. The problem lies in the complexity class 
 NP\, but neither is the problem known to be NP-complete nor has a 
 polynomial-time algorithm been developed. Its complexity status thus 
 remains open.\n\nI will talk about various aspects of the graph 
 isomorphism problem: To this end I will describe the concepts underlying 
 isomorphism algorithms that run fast in practice and explain how some of 
 these concepts can be applied to obtain scalable graph kernels in the 
 area of machine learning. I will also discuss the results that are known 
 concerning the parameterized complexity of the isomorphism problem. \n
SUMMARY:Pascal Schweitzer - Aspects of the Graph Isomorphism Problem: 
 Machine Learning\, Applications\, Practical Algorithms\, and 
 Parameterized Complexity
DTSTART;TZID=Europe/Paris:20120106T110000
DTEND;TZID=Europe/Paris:20120106T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100519T084049Z
UID:20100519T084049Z-4032-2000-1-0@dublin
SEQUENCE:3
LAST-MODIFIED:20100629T090338Z
DESCRIPTION:In this talk I will consider a maximum flow generalization of 
 the Shannon\nSwitching Game: Given is a network\, which consists of a 
 graph G with positive\ninteger capacities c on the edges\, and two 
 designated vertices s and t (the\nsource and sink). Two players\, Maker 
 and Breaker\, alternatingly take turns\nwhere they fix edges and delete 
 edges which have not yet been fixed. The game\nends when all remaining 
 edges are fixed. Maker wins iff in the remaining\nnetwork\, a flow of a 
 given value L can be sent from s to t. We consider the\ndecision problem 
 that asks whether for a given network and integer L\, Maker\nhas a 
 winning strategy.\n\nThe Shannon Switching Game is the special case where 
 L=1\, and in this case the\nproblem can be decided in polynomial time\, 
 as was shown by Lehman (1964).\n\nI will show that the general problem is 
 PSPACE-hard\, even in the special case\nwhere G is a series-parallel 
 (multi-)graph. In the case where every vertex of\nG except possibly s and 
 t has degree at most 3\, the problem can be solved in\npolynomial time. 
 In the case of series-parallel graphs\, I will discuss how\none can 
 define and obtain approximation algorithms for this problem\, and 
 show\nan interesting paradox that applies to more combinatorial games.
SUMMARY:Paul Bonsma - A Maximum Flow Generalization of the Shannon 
 Switching Game
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100625T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100625T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:9f466a5bldm5j336sn0gih9tn0@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:Johannes Fichte - SAT Solving auf Formeln beschränkter 
 Baumweite
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20080418T090000Z
DTEND:20080418T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20110401T124936Z
UID:934dd2cd-5fa1-48ae-9b8f-03eab4d14e5e
LAST-MODIFIED:20110401T124936Z
SUMMARY:Johann A. Makowsky (Technion IIT\, Haifa) - Das Spektrum Problem 
 von H. Scholz (1954) und sein Einfluss auf die Entwicklung der endlichen 
 Modelltheorie
DTSTART;TZID=Europe/Paris:20110415T110000
DTEND;TZID=Europe/Paris:20110415T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:vcaeldhefsita5m9bhgv7ps4fk@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T101038Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:0nkkkoedgddrr66dsb62ca4b94@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:László Egri - Linear Datalog ≠ Symmetric Datalog
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20090402T090000Z
DTEND:20090402T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100518T110035Z
UID:20100518T110035Z-4146-2000-1-0@dublin
SEQUENCE:5
LAST-MODIFIED:20100701T070940Z
DESCRIPTION:A seminal technique of theoretical physics called Wick's 
 theorem\ninterprets the Gaussian matrix integral of the products of the 
 trace of\npowers of Hermitian matrices as the number of labelled maps 
 with a given\ndegree sequence\, sorted by their Euler characteristics. 
 This leads to the\nmap enumeration results analogous to those obtained by 
 combinatorial\nmethods.\n\nMartin Loebl and I showed that the enumeration 
 of graphs embeddable on a\nsurface can be formulated as the Gaussian 
 matrix integral of an ice-type\npartition function\, where the number of 
 planar graphs appears as a leading\nterm.
SUMMARY:Mihyun Kang - The enumeration of planar graphs via the matrix 
 integral method
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100702T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100702T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:k3gt2g9k52st2nd8gi92nb4uf8@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T101048Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100414T125150Z
UID:20100414T125150Z-6060-2000-1-0@dublin
SEQUENCE:4
LAST-MODIFIED:20100421T081251Z
DESCRIPTION:Hypergraph width measures are a class of hypergraph 
 invariants important in studying the complexity of constraint 
 satisfaction problems (CSPs). We generalize the problem of finding\, for 
 a given width-function\, the width of a Hypergraph together with a 
 corresponding optimal tree decomposition. This covers the problems of 
 generalized and fractional hypertree-width by using suitable 
 width-functions. We develop a first exact exponential algorithm for this 
 problem. Showing the connection with tree decompositions of graphs\, we 
 adapt known combinatorial and algorithmic results of the latter and 
 provide a notably enhanced algorithm.
SUMMARY:Lukas Moll - Computing f-hypertree-width and optimal tree 
 decompositions
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100423T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100423T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100415T135526Z
UID:20100415T135526Z-11805-2000-1-4@dublin
SEQUENCE:7
LAST-MODIFIED:20100609T022323Z
DESCRIPTION:Ein Petrinetz erzeugt auf natürliche Weise eine Sprache\, 
 nämlich die\nMenge aller möglichen Schaltsequenzen\, und einen Graph\, 
 nämlich seinen\nErreichbarkeitsgraph. Bei der Synthese von Petrinetzen 
 geht es darum\,\naus einer Sprache bzw. einen Graphen ein Petrinetz zu 
 finden\, das diese\nSprache bzw. diesen Graphen erzeugt.\n\nIn den 90er 
 Jahren wurden erste Ergebnisse erzielt. Die treibenden\nKräfte Badouel\, 
 Bernadinello und Darondeau zeigten unter anderem\, dass\ndie Synthese von 
 Petrinetzen NP-hart ist.\n\nDas von mir vorgestellte Paper von Darondeau 
 (Unbounded Petri Net\nSynthesis\, LNCS 3098\, 2004) behandelt die 
 Synthese unbeschränkter\nPetrinetze unter Einschränkung an die gegebene 
 Sprache bzw. den\ngegebenen Graph. Es stellt sich die Frage danach\, wie 
 stark diese\nEinschränkungen sind. Diese Frage habe ich versucht zu 
 beantworten und\nhabe bereits teilweise Antworten gefunden. Erstaunlich 
 ist\, dass die\nEinschränkungen an die Sprache keine Einschränkungen zu 
 sein scheinen\,\nd.h. Sprachen die von Petrinetzen erzeugt werden 
 erfüllen die von\nDarondeau in diesem Paper angesetzen Voraussetzungen.
SUMMARY:Jörg Bachmann - Synthese von Petrinetzen
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100611T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100611T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20111202T135838Z
UID:c8c72009-695f-46d1-9d1e-2e7698a10e1a
LAST-MODIFIED:20111202T135838Z
DESCRIPTION:We study a family of graph clustering problems where each 
 cluster has to satisfy a certain local requirement. \n\nFormally\, let 
 $mu$ be a function on the subsets of vertices of a graph $G$. In the 
 $(mu\,p\,q)$-PARTITION problem\, the task is to find a partition of the 
 vertices into clusters where each cluster $C$ satisfies the requirements 
 that (1) at most $q$ edges leave $C$ and (2) $mu(C)≤ p$. \n\nOur first 
 result shows that if $\\mu$ is an arbitrary polynomial-time computable 
 monotone function\, then $(mu\,p\,q)$-PARTITION can be solved in time 
 $n^{O(q)}$\, i.e.\, it is polynomial-time solvable for every fixed 
 $q$.\n\nWe study in detail three concrete functions $mu$ (number of 
 nonedges in the cluster\, maximum number of non-neighbours a vertex has 
 in the cluster\, the number of vertices in the cluster)\, which 
 correspond to natural clustering problems.  For these functions\, we show 
 that $(mu\,p\,q)$-PARTITION can be solved in time $2^{O(p)} n^{O(1)}$ and 
 in time $2^{O(q)} n^{O(1)}$\, i.e.\, the problem is fixed-parameter 
 tractable parameterized by $p$ or by $q$.\n
SUMMARY:Dániel Marx - Clustering with Local Restrictions
DTSTART;TZID=Europe/Paris:20111202T110000
DTEND;TZID=Europe/Paris:20111202T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Daniel Kirsten":MAILTO:Daniel.Kirsten@gmx.net
X-MOZ-GENERATION:17
DTSTAMP:20120419T131008Z
UID:b38a42bd-4452-489d-b148-816a56c0856b
SEQUENCE:5
LAST-MODIFIED:20120507T153243Z
DESCRIPTION:We study the complexity of the following \"resolution width 
 problem\": Does a given 3-CNF have a resolution refutation of width k? We 
 prove that the problem cannot be decided in time O(n^((k-3)/12)). This 
 lower bound is unconditional and does not rely on any unproven complexity 
 theoretic assumptions. The lower bound is matched by a trivial upper 
 bound of n^O(k).\n\nWe also prove that the resolution width problem is 
 EXPTIME-complete (if k is part of the input). This confirms a conjecture 
 by Vardi\, who has first raised the question for the complexity of the 
 resolution width problem. Furthermore\, we prove that the variant of the 
 resolution width problem for regular resolution is PSPACE-complete\, 
 confirming a conjecture by Urquhart.\n\nThe lower bounds were obtained 
 via the model theoretic characterization of bounded width resolution as 
 existential pebble game due to Atserias and Dalmau. This improves 
 previous complexity results for the existential pebble game on finite 
 relational structures A and B to the case where the second structure B is 
 fixed.\n
SUMMARY:Christoph Berkholz - Lower bounds for the resolution width 
 problem and existential pebble games
DTSTART;TZID=Europe/Paris:20120511T110000
DTEND;TZID=Europe/Paris:20120511T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100629T110019Z
UID:20100629T110019Z-4203-2000-1-0@dublin
SEQUENCE:4
LAST-MODIFIED:20100629T135303Z
DESCRIPTION:This talk is a continuation of the Graduiertenkolleg lecture 
 of June 28 on the same topic\, but will be 
 self-contained.\n\nDerandomization constitutes a central theme in the 
 theory of computing.\nIt involves the design of efficient deterministic 
 simulations of randomized processes. Polynomial identity testing (PIT) is 
 the fundamental problem of deciding whether a given polynomial identity 
 holds. The problem has a natural and efficient randomized algorithm\, but 
 efficient deterministic algorithms for the general case have remained 
 elusive.\n\nIn the lecture of June 28 we showed a hardness result for the 
 general case. In this talk we will survey known positive results for 
 special cases\, present the key ingredients in the progress that has been 
 made in the past few years\, and show them at work in a simple setting.
SUMMARY:Dieter van Melkebeek - Derandomizing Polynomial Identity Testing
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100716T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100716T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20111202T135501Z
UID:b1d30582-97df-4c00-abfa-c4553dc35012
LAST-MODIFIED:20111202T135501Z
DESCRIPTION:http:
 //www2.informatik.hu-berlin.de/~kirsten/misc/Abstract-Konstantinos-Stavrop
 oulos.pdf
SUMMARY:Konstantinos Stavropoulos - Outerplanar Obstructions for a 
 Feedback Vertex Set
DTSTART;TZID=Europe/Paris:20111007T110000
DTEND;TZID=Europe/Paris:20111007T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20110816T092310Z
UID:89641c24-2a12-4788-9bbe-6d1eaff369f4
LAST-MODIFIED:20110816T092310Z
SUMMARY:Kord Eickmeyer - tba
DTSTART;TZID=Europe/Paris:20110829T120000
DTEND;TZID=Europe/Paris:20110829T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:5uouct4127gpnl3fe7d2ja4fjo@google.com
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:3lnedfgc37uqu50s873s7702lo@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:Holger Dell - Algebraic Reductions (in the Coloured Tutte 
 Polynomial)
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20080425T090000Z
DTEND:20080425T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100415T135052Z
UID:20100415T135052Z-11805-2000-1-0@dublin
SEQUENCE:4
LAST-MODIFIED:20100427T092430Z
DESCRIPTION:Beim Datenaustausch sollen Daten (hier relationale Daten) von 
 einem Format in ein anderes Format gemäß einer vorgegebenen 
 Spezifikation (hier durch eine Menge logischer Formeln) transformiert 
 werden. Anfrageauswertung bezeichnet in diesem Kontext das Problem der 
 Beantwortung von Anfragen\, die über das Zielformat \"sprechen\" (d.h. 
 Anfragen an das Resultat des Datenaustauschs). Dieses Problem ist 
 insofern interessant\, als das Resultat des Datenaustauschs 
 üblicherweise nicht vollständig spezifiziert wird und es daher mehr als 
 eine Möglichkeit geben kann\, Daten ins Zielformat zu übersetzen. Ein 
 weiteres Problem besteht darin\, dass einige Informationen über das 
 Resultat des Datenaustauschs oft nur implizit spezifiziert werden. Die 
 grundlegende Frage ist dann\, wie solche Anfragen überhaupt beantwortet 
 werden sollen bzw. können.\n\nEine erste Anfragesemantik wurde 2003 von 
 Fagin\, Kolaitis\, Miller und Popa vorgestellt und wurde schnell als die 
 \"richtige\" Semantik zur Auswertung monotoner Anfragen (wie z.B. 
 konjunktive Anfragen) akzeptiert. Darüberhinaus hat sich aber gezeigt\, 
 dass sie für nicht-monotone Anfragen oft unintuitive Antworten liefert. 
 Der Vortrag gibt eine kurze Übersicht über einige in der Literatur 
 vorgestellte Semantiken für nicht-monotone Anfragen und wendet sich dann 
 der Komplexität der Anfrageauswertung bzgl. einer konkreten Semantik zu. 
 Insbesondere wird ein Algorithmus zur Auswertung sogenannter universeller 
 Anfragen bzgl. passend eingeschränkten Spezifikationen skizziert\, der 
 für die im Datenaustausch übliche Einschränkung\, dass die 
 Spezifikation und die Anfrage fest ist\, in Polynomialzeit arbeitet. 
 Dieses Resultat ist insofern überraschend\, als dass die Auswertung 
 nicht-monotoner Anfragen üblicherweise coNP-schwer bzw. unentscheidbar 
 ist.
SUMMARY:André Hernich - Anfrageauswertung im relationalen 
 Datenaustausch
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100507T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100507T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20101222T140605Z
UID:c23d0d3f-c9b0-4589-8614-e71a5a69140c
LAST-MODIFIED:20101222T140605Z
SUMMARY:André Hernich - Computing Universal Models under Inclusion 
 Dependencies
DTSTART;TZID=Europe/Paris:20101203T110000
DTEND;TZID=Europe/Paris:20101203T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:1
DTSTAMP:20101222T140643Z
UID:c14fec26-9683-41ea-8f9b-11582a4f916f
SEQUENCE:1
LAST-MODIFIED:20101222T140643Z
DESCRIPTION:We show that for every probability $p$ with $0<p<1$\, 
 computation of all-terminal graph reliability with edge failure 
 probability $p$ requires time exponential in $\\Omega(m/\\log2 m)$ for 
 simple graphs of $m$ edges under the Exponential Time Hypothesis.
SUMMARY:Nina Taslaman (ITU Copenhagen) - The Exponential Time Complexity 
 of Computing the Probability that a Graph is Connected
DTSTART;TZID=Europe/Paris:20101126T110000
DTEND;TZID=Europe/Paris:20101126T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ATTENDEE;CN="Mitarbeiterseminar Logik in der Informatik";RSVP=FALSE;
 PARTSTAT=ACCEPTED;ROLE=REQ-PARTICIPANT;X-UID=0:mailto:
 28c074ohvkqngj13v90i72kb3s@group.calendar.google.com
DTSTAMP:20091022T134353Z
UID:taqriudu6nnt5rhkq9m4oj28ks@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:Frederic Dorn (HU Berlin) - Catalan structure and dynamic 
 programming
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20071026T090000Z
DTEND:20071026T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1034434594.340
LAST-MODIFIED:20091022T115602Z
SUMMARY:Nicole Schweikardt - Additions-invariantes FO und reguläre 
 Sprachen
PRIORITY:5
DTSTART:20090911T090000Z
DTEND:20090911T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:3
DTSTAMP:20110524T110458Z
UID:0d322b99-25f2-4a0c-b69c-9aa727513afb
SEQUENCE:2
LAST-MODIFIED:20110524T110458Z
DESCRIPTION:Databases are dynamic structures - a database is object to an 
 ongoing sequence of small changes and queries. In a dynamic approach one 
 can initialize auxiliary relations which help to answer a query faster 
 than recomputing it from scratch. These relations must be updated after 
 each change in order to keep them consistent with the database.\n\nIn 
 this talk I will introduce the Dyn-FO framework of Patnaik and Immerman 
 which models databases as finite relational structures and measures the 
 complexity of maintaining auxiliary relations by logical means. I will 
 give an overview over important results from dynamic complexity 
 theory.\n\nIn the literature it is assumed that the considered structures 
 are ordered or equivalently that the dynamic process starts with an empty 
 structure (then the order of arrival can be incrementally built). I will 
 discuss the importance of the availability of an ordering of the 
 considered structures. In particular I will show how to modify the known 
 dynamic algorithms for symmetric reachability and how to modify the 
 concept of dynamic reductions to work on unordered structures. On the 
 other hand I will show that several queries which can be handled with 
 first-order updates in the ordered setting cannot be handled in the 
 unordered setting.
SUMMARY:Sebastian Siebertz - Dynamic Definability
DTSTART;TZID=Europe/Paris:20110527T110000
DTEND;TZID=Europe/Paris:20110527T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Daniel Kirsten":MAILTO:Daniel.Kirsten@gmx.net
X-MOZ-GENERATION:17
DTSTAMP:20120507T113920Z
UID:KOrganizer-88391912.993
SEQUENCE:3
LAST-MODIFIED:20120522T193204Z
DESCRIPTION:Rank Logics were introduced by Dawar/Grohe/Holm/Laubner  as 
 one significant step towards a logics which captures polynomial time.  In 
 the talk\, we give some first results concering the expressive power of 
 rank logics over empty signatures.\n\nIn the talk\, we will sketch the 
 main steps to prove the central conjecture by the speaker raised in his 
 talk from December 9\, 2011.   The talk will be self-contained.
SUMMARY:Daniel Kirsten - Rank Logics over Empty Signatures:  First Real 
 Results
DTSTART;TZID=Europe/Berlin:20120525T110000
DTEND;TZID=Europe/Berlin:20120525T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100301T072331Z
UID:20100301T072331Z-20867-2000-1-0@dublin
SEQUENCE:3
LAST-MODIFIED:20100301T062435Z
SUMMARY:Ken-ichi Kawarabayashi - The disjoint paths problem: Algorithm 
 and Structure\n
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100301T141500
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100301T160000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
ATTENDEE;CN="Holger Dell";RSVP=FALSE;PARTSTAT=ACCEPTED;
 ROLE=REQ-PARTICIPANT;X-UID=137689152:mailto:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1577533850.382
SEQUENCE:2
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:ksh3jiq2u8oc08beraqgarmfao@google.com
SEQUENCE:3
LAST-MODIFIED:20091028T100918Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:roearl69m0v97htsm1cakcou3g@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T101033Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Daniel Kirsten":MAILTO:Daniel.Kirsten@gmx.net
X-MOZ-GENERATION:20
DTSTAMP:20120624T200847Z
UID:KOrganizer-1422832860.368
SEQUENCE:2
LAST-MODIFIED:20120624T201823Z
DESCRIPTION:The Valiant–Vazirani Isolation Lemma (1986) provides an 
 efficient procedure for isolating a satisfying assignment of a given 
 satisfiable circuit: Given a Boolean circuit C on n input variables\, the 
 procedure outputs a new circuit C' on the same n input variables such 
 that\n (i) every satisfying assignment of C' also satisfies C\, and  
 \n(ii) if C is satisfiable\, then C' has exactly one satisfying 
 assignment. In particular\, if C is unsatisfiable\, then (i) implies that 
 C' is unsatisfiable. The Valiant–Vazirani procedure is randomized\, and 
 when C is satisfiable it produces a uniquely satisfiable circuit C' with 
 probability Omega(1/n).\n\nIs it possible to have an efficient 
 deterministic witness-isolating procedure? Or\, at least\, is it possible 
 to improve the success probability of a randomized procedure to a large 
 constant? We argue that the answer is likely \"No\". More precisely\, we 
 prove that there exists a non-uniform randomized polynomial-time 
 witness-isolating procedure with success probability bigger than 2/3 if 
 and only if SAT has polynomial-size circuits.\n
SUMMARY:Holger Dell - Is Valiant–Vazirani's Isolation Probability 
 Improvable?
DTSTART;TZID=Europe/Berlin:20120706T110000
DTEND;TZID=Europe/Berlin:20120706T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:1
DTSTAMP:20110628T094302Z
UID:0f61f98a-96d5-4e1b-a310-6d739e7eacb4
LAST-MODIFIED:20110628T094302Z
DESCRIPTION:Das Bestimmen der Anzahl verschiedener Elemente $F_0$ in 
 einem Datenstrom ist ein fundamentales Problem in den verschiedensten 
 Anwendungen\, unter anderem in der Überwachung des Netzwerkverkehrs 
 sowie im Bereich der Datenbanken. Algorithmen\, die dieses Problem mit 
 sublinearen Speicherplatz lösen\, müssen randomisiert und approximativ 
 sein. Die in den letzten Jahren gezeigten unteren Schranken für einen 
 randomisierten Approximationsalgorithmus wurden nun von Kane\, Nelson und 
 Woodruff in ihrer Arbeit \"An Optimal Algorithm for the Distinct Elements 
 Problem\" auf der PODS 2010 erreicht. Die Ideen ihres Algorithmus werde 
 ich in meinem Vortrag vorstellen.
SUMMARY:Lena Kalleske - Randomisierter Approximationsalgorithmus zur 
 Berechnung der Anzahl verschiedener Elemente in einem Datenstrom
DTSTART;TZID=Europe/Paris:20110701T110000
DTEND;TZID=Europe/Paris:20110701T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100415T135500Z
UID:20100415T135500Z-11805-2000-1-3@dublin
SEQUENCE:4
LAST-MODIFIED:20100521T092605Z
DESCRIPTION:In diesem Vortrag zeigen wir obere und untere Schranken für 
 parametrisierte \nProbleme innerhalb der Schaltkreiskomplexitätsklasse 
 AC$^0$. Als erstes \nErgebnis in diese Richtung bewies Benjamin Rossman 
 2007\, dass $k$-Clique \n(enthält ein gegebener Graph eine Clique der 
 Größe $k$?) AC$^0$-Schaltkreise der \nGröße $n^{2k/9}$ benötigt. 
 Kazuyuki Amano konnte 2009 die Methode auf \nSubgraphisomorphieprobleme 
 erweitern. Darauf aufbauend zeigen wir untere \nSchranken für induzierte 
 Subgraphisomorphie- und Homomorphieprobleme. \n\nMit einer auf 
 Schaltkreise übertragenen fpt-Reduktion folgt\, dass die 
 \n$k$-Clique-Schranke auch für $k$-DominatingSet gilt. Auf der anderen 
 Seite können \nwir zeigen\, dass sich $k$-VertexCover mit $f(k)n^2$ 
 Gattern in AC$^0$ berechnen \nlässt.
SUMMARY:Christoph Berkholz - Über die Schaltkreiskomplexität 
 parametrisierter Probleme
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100528T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100528T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20110214T130755Z
UID:bf6df205-3745-41bf-997f-3f3bebb196c6
SEQUENCE:1
LAST-MODIFIED:20110214T130755Z
DESCRIPTION:We study some problems of the following type: Given a set of 
 straight-line segments in the plane and a set of cells in the induced 
 arrangement\, compute a subset of segments of minimum size one needs to 
 remove so that the cells become connected. In other words\, we want to 
 compute a minimum-color subgraph in the (edge-colored) dual of the 
 arrangement.\n\nWe show that the problems of connecting two cells and 
 connecting all cells are both NP-hard. We discuss polynomial-time and 
 fixed-parameter tractable cases and several open problems.
SUMMARY:Panos Giannopoulos - On some connection problems in straight-line 
 segment arrangements
DTSTART;TZID=Europe/Paris:20110218T110000
DTEND;TZID=Europe/Paris:20110218T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20110715T095429Z
UID:e308d2ad-1389-4325-a438-1c1b52200c4d
SEQUENCE:1
LAST-MODIFIED:20110715T095429Z
SUMMARY:Holger Dell - Sparse Instances of Hard Problems
LOCATION:Humboldt-Kabinett
DTSTART;TZID=Europe/Paris:20110715T150000
DTEND;TZID=Europe/Paris:20110715T160000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:i2rrfuob84hakvmhpn1kob8j9g@google.com
SEQUENCE:3
LAST-MODIFIED:20091028T100924Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20101222T140510Z
UID:9333eca4-8f31-4d4c-b9f9-324732b21bbe
LAST-MODIFIED:20101222T140510Z
SUMMARY:Siamak Tazari - Excluding shallow directed minors\, and further 
 structural properties of\,directed graphs
DTSTART;TZID=Europe/Paris:20101119T110000
DTEND;TZID=Europe/Paris:20101119T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:KOrganizer-1152744305.796
SEQUENCE:2
LAST-MODIFIED:20091028T100103Z
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\".
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:5itfrh7ia3aun9oakcsthekabc@google.com
SEQUENCE:2
LAST-MODIFIED:20091028T101043Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:9
DTSTAMP:20110915T122218Z
UID:796104f0-e1ec-40aa-8f9f-030c42bf07ff
SEQUENCE:2
LAST-MODIFIED:20110915T122218Z
DESCRIPTION:Zeitunabhängige Lebendigkeit von Intervall-Petrinetzen
SUMMARY:Jörg Bachmann - Diplomarbeitverteidigung
DTSTART;TZID=Europe/Paris:20110923T111500
DTEND;TZID=Europe/Paris:20110923T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100507T110427Z
UID:20100507T110427Z-31033-2000-1-0@dublin
SEQUENCE:5
LAST-MODIFIED:20100518T090357Z
DESCRIPTION:In this talk we will present a polynomial time algorithm for 
 computing\nflat and linkless embeddings of graphs in $\\mathbb 
 R^3$.\n\nAn embedding of a graph in 3-dimensional space is called 
 \"linkless\" if\nno pair of disjoint cycles forms a non-trivial link in 
 the sense of\nknot-theory. That is\, for any two disjoint cycles in the 
 embedding\,\none can be contracted to a single point without cutting the 
 other. A\ngraph is called linklessly embeddable if it has a linkless 
 embedding\nin $\\mathbb R^3$.\n\nLinklessly embeddable graphs generalise 
 the concept of planar graphs\nto the 3-dimensional case. Like planar 
 graphs\, they have many nice\nproperties which makes it desirable to 
 decide whether a graph is\nlinklessly embeddable and if so\, to compute 
 an embedding.\n\nNot every graph has a linkless embedding\, though. A 
 characterisation\nin terms of excluded minors of those graphs that can be 
 drawn in this\nway was given by Robertson\, Seymour and Thomas\, 
 generalising the\ncharacterisation of planar graphs by Kuratowski and 
 Wagner. However\,\nwhile this can be used to decide whether a graph has a 
 linkless\nembedding\, this does not give an algorithm for actually 
 computing one\nif it exists.\n\nIn this talk I will present such an 
 algorithm for computing linkless\nembeddings. In fact\, we will compute 
 even nicer embeddings which are\ncalled flat.\n\nI will first introduce 
 the relevant concepts needed for the algorithm\nand then present the main 
 ideas focussing mostly on the\ngraph-theoretical aspects of the 
 algorithm.\n
SUMMARY:Stephan Kreutzer - Computing linkless and flat embeddings of 
 graphs in 3-space
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100521T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100521T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:4
DTSTAMP:20110207T122245Z
UID:0c69938b-4c75-4a15-a94b-75838bb48700
SEQUENCE:1
LAST-MODIFIED:20110207T122245Z
DESCRIPTION:Time Petri nets are a well-known extension of standard Petri 
 nets\, where each transition gets a continuous time interval\, specifying 
 the range of the transition's firing time. The transitions fire in 
 single-firing mode. In contrast\, Timed Petri nets are a different 
 time-dependent extension where a time duration is associated with each 
 transition. The transitions fire in maximal-step mode. We sketch a 
 locally defined transformation from a Timed into a Time Petri net. 
 Additionally\, we consider time-dependent Petri nets\, where the firing 
 of each transition lasts a certain time which is limited by both a lower 
 and an upper bound. These nets can also be transformed locally into Time 
 Petri nets. We use them for modelling and analyzing biochemical systems 
 and demonstrate this considering the  cdc2 and cyclin interaction in the 
 cell division cycle.
SUMMARY:Louchka Popova - About Verification of Biochemical Network Models 
 using Time-dependent Petri Nets
DTSTART;TZID=Europe/Paris:20110211T110000
DTEND;TZID=Europe/Paris:20110211T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:ert61vendukbkra62615t2b0lo@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100936Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:1
DTSTAMP:20101222T140448Z
UID:bade1c44-de24-4d5a-aadd-8d47e0374f77
SEQUENCE:1
LAST-MODIFIED:20101222T140448Z
DESCRIPTION:For many algorithmic graph problems\, the problem variant for 
 directed graphs is strictly harder than the one for undirected graphs 
 (consider for instance Shortest Path\, Longest Path\, Dominating Set). By 
 this we mean that an algorithm for the directed problem variant can 
 easily be used to solve the undirected problem variant: simply replace 
 undirected edges by a pair of directed edges in both directions.\n\nThe 
 Feedback Vertex Set (FVS) problem is an exception to this pattern. This 
 decision problem asks\, given a (possibly directed) graph $G$ and integer 
 $k$\, whether there is a set of at most $k$ vertices that hits all cycles 
 of $G$. We are interested in Fixed Parameter Tractable (FPT) algorithms 
 for this problem: algorithms with complexity bounded by $f(k)n^c$\, where 
 $n$ is the number of vertices of $G$\, $c$ is a constant independent of 
 $k$\, and $f(k)$ may be an arbitrary computable function.\n\nMany 
 different FPT algorithms are known for undirected FVS. In a breakthrough 
 result from 2007\, Chen\, Liu\, Lu\, O'Sullivan and Razgon gave the first 
 (and only) FPT algorithm for directed FVS\, using very different 
 techniques. Their algorithm does however not apply to undirected 
 FVS.\n\nIn this talk we will bridge the gap between undirected and 
 directed FVS by giving an algorithm that works for both types of graphs. 
 More precisely\, we give an FPT algorithm for FVS in mixed graphs\, which 
 may have both directed and undirected edges.\n\nThis is joint work with 
 Daniel Lokshtanov.
SUMMARY:Paul Bonsma - Feedback Vertex Set in Mixed Graphs
DTSTART;TZID=Europe/Paris:20101022T110000
DTEND;TZID=Europe/Paris:20101022T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:3
DTSTAMP:20110707T103240Z
UID:8f234cc1-76a9-4808-9d42-97f44c7e2c83
SEQUENCE:2
LAST-MODIFIED:20110707T103240Z
DESCRIPTION:Algorithmic meta theorems state that problems definable in 
 some logic are efficiently solvable on some class of logical structures. 
 The prime example of these results is the Theorem of Courcelle\, which 
 states that all monadic second-order (MSO) definable problems are linear 
 time solvable on structures of bounded tree width.\n\nIn the talk I will 
 discuss the computational complexity of classes of problems that are 
 solvable by applying algorithmic meta theorems. We will have a look at 
 two results and discuss their proofs as well as their applications: The 
 first result is an algorithmic meta theorem for L\, which states that all 
 MSO-definable decision\, optimization\, and counting problems are 
 solvable on deterministic logarithmic space on structures of bounded tree 
 width. The second result transfers the idea of unified MSO-based problem 
 definitions to a class inside L. It states that all MSO-definable 
 decision\, optimization\, and counting problems are solvable by uniform 
 circuit families from TC0 on structures of bounded tree depth\, a width 
 measure that is related to the longest simple path length in graphs. 
 During the course of the talk we will see that each result covers 
 complete problems for the corresponding complexity class and\, thus\, 
 classifies the computational complexity of the considered class of 
 problems.
SUMMARY:Michael Elberfeld (Lübeck) - Algorithmic Meta Theorems Around 
 Logspace
DTSTART;TZID=Europe/Paris:20110708T110000
DTEND;TZID=Europe/Paris:20110708T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
ATTENDEE;CN="Holger Dell";RSVP=FALSE;PARTSTAT=ACCEPTED;
 ROLE=REQ-PARTICIPANT;X-UID=137703056:mailto:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1033924799.120
SEQUENCE:3
LAST-MODIFIED:20091117T142845Z
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).
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:4
DTSTAMP:20110111T143252Z
UID:5ba9a691-ac61-4326-ae6f-23a355fa091f
LAST-MODIFIED:20110111T143252Z
DESCRIPTION:Schoening in 1999 presented a simple randomized algorithm for 
 $k$-SAT with running time $O(a^n poly(n))$ for $a = 2(k-1)/k$. We give a 
 deterministic version of this algorithm running in time $O(a^{n+o(n)} 
 )$.\n\nJoint work with Dominik Scheder.
SUMMARY:Robin Moser (ETH Zürich) - A Full Derandomization of Schoening's 
 k-SAT Algorithm
DTSTART;TZID=Europe/Berlin:20110114T110000
DTEND;TZID=Europe/Berlin:20110114T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:g7pdm48m316nuu1rdgvorvnl18@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100932Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:2
DTSTAMP:20110204T145849Z
UID:6ac9c69b-e97d-4b64-bd72-e6ecacb96c21
LAST-MODIFIED:20110204T145849Z
DESCRIPTION:At CSL2010 we introduced randomised logics for studying 
 randomised complexity classes using descriptive complexity theory. We 
 showed that in particular first-order logic provably gains expressive 
 power from randomisation\, contrary to what is believed of most classical 
 randomised complexity classes.\n\nAfter briefly reviewing these results\, 
 I will present some recent results in the opposite direction\, namely 
 that randomised first-order logic can be completely derandomised on 
 structures with a unary signature (i.e.\, coloured sets). The technique 
 used to obtain this result is interesting insofar as it deviates from the 
 classical approach of constructing random generators. Rather\, we show 
 that first-order sentences which have a probability gap can not express 
 properties of coloured sets which are not expressible in FO 
 alone.\n\nFinally\, I will mention a few concrete queries which are 
 provably not expressible in randomised FO\, and state some open 
 problems.
SUMMARY:Kord Eickmeyer - Nonaxiomatisability in Randomised First-Order 
 Logic
DTSTART;TZID=Europe/Paris:20110204T110000
DTEND;TZID=Europe/Paris:20110204T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:q3b5kt22top4mbct2ftel0tup8@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100847Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:5v43fe1qle1jl8pl4j5f5uk124@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100913Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:lhhdqgfitg9fh221586daqhgls@google.com
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
X-MOZ-GENERATION:3
DTSTAMP:20110608T155721Z
UID:a1795a63-a51a-4261-8fd7-94220466f6ab
SEQUENCE:2
LAST-MODIFIED:20110608T155721Z
SUMMARY:André Hernich - Computing Universal Models Under Linear Tgds
DTSTART;TZID=Europe/Paris:20110610T110000
DTEND;TZID=Europe/Paris:20110610T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:av3cho3fs5lpe4iia59qabt3rg@google.com
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
ORGANIZER;CN="Daniel Kirsten":MAILTO:Daniel.Kirsten@gmx.net
X-MOZ-GENERATION:20
DTSTAMP:20120430T210121Z
UID:e9debb6d-ae4d-4d7a-9515-54cd7ef07240
SEQUENCE:2
LAST-MODIFIED:20120503T101334Z
DESCRIPTION:We tackle the problem of defining a well-founded semantics 
 for Datalog rules with existentially quantified variables in their heads 
 and negations in their bodies. In particular\, we provide a well-founded 
 semantics (WFS) for the recent Datalog$^\\pm$ family of ontology 
 languages\, which covers several important description logics (DLs). To 
 do so\, we  generalize  Datalog$^\\pm$ by non-stratified nonmonotonic 
 negation in rule bodies\, and we define a WFS for this generalization via 
 guarded fixed-point logic. We refer to this approach as {\\it 
 equality-friendly WFS}\, since it has the advantage that it does not make 
 the unique name assumption (UNA)\; this brings it close to OWL and its 
 profiles as well as typical DLs\, which also do not make the UNA. We 
 prove that for guarded Datalog$^\\pm$ with negation under the 
 equality-friendly WFS\, conjunctive query answering is decidable\, and we 
 provide precise complexity results for this problem. From these results\, 
 we obtain precise definitions of the standard WFS extensions of EL and of 
 members of the $DL-Lite$ family\, as well as corresponding complexity 
 results for query answering.\n\nThis is joint work with Georg Gottlob\, 
 Clemens Kupke\, and Thomas Lukasiewicz.
SUMMARY:André Hernich - Equality-Friendly Well-Founded Negation for 
 Datalog +/- and  Applications to Description Logics
DTSTART;TZID=Europe/Paris:20120504T110000
DTEND;TZID=Europe/Paris:20120504T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100427T112455Z
UID:20100427T112455Z-16693-2000-1-0@dublin
SEQUENCE:4
LAST-MODIFIED:20100427T131848Z
DESCRIPTION:Theoretical computer science provides us with tools and 
 techniques to\nclassify problems as efficiently solvable or 
 computationally hard. But\neven hard problems have to be solved and there 
 exist various ways to\nattack them. One way is to restrict the input to 
 certain classes that\nare computationally more feasible. In the case of 
 graph theoretic\nproblems\, this is akin to considering the problem on 
 special graph\nclasses. One of the most important such classes is the 
 class of\nplanar graphs or more generally\, graphs that are embedded on a 
 fixed\nsurface\; an even further generalization is to consider classes 
 of\ngraphs that are closed under taking minors. Such classes of 
 graphs\nhave been extensively studied in the past three decades\, 
 especially\ndue to the deep graph minor theory of Robertson and Seymour. 
 In this\nthesis\, we consider various algorithms on or related to such 
 graph\nclasses and the theory of graph minors. The thesis consists of 
 three\nparts:\n\nIn the first part\, we consider the Steiner tree problem 
 in embedded\ngraphs. We present an extension\, engineering\, and 
 application of the\nrecent polynomial-time approximation scheme (PTAS) of 
 this problem in\nplanar graphs by Borradaile\, Klein\, and Mathieu 
 (2007\,2009): (i) we\nshow how to generalize the technique of the PTAS 
 from planar graphs to\ngraphs of bounded genus and further subset 
 connectivity problems\; (ii)\nwe implemented and engineered this 
 algorithm from a practical point of\nview and show that it works 
 surprisingly well\, even on very large\ninstances\; and (iii) we apply 
 this algorithm to obtain an efficient\nPTAS for the geometric Steiner 
 tree problem among obstacles in the\nplane.\n\nIn the second part of the 
 thesis\, we present a linear-time\nshortest-paths algorithm for proper 
 minor-closed graph classes and\nshow how to obtain faster approximation 
 schemes and parameterized\nalgorithms for various problems on these 
 graphs classes.\n\nFinally\, in the last part\, we provide the first 
 lower bounds for\nCourcelle's famous theorem (1990) about the 
 model-checking problem of\nfixed formulas of monadic second-order logic 
 in graphs. Whereas\nCourcelle showed that this problem is efficiently 
 solvable on graphs\nof bounded treewidth\, we show that on various 
 classes of graphs of\nunbounded but low treewidth the problem becomes 
 computationally hard\n(modulo some complexity assumptions). Along the 
 way\, we develop\nseveral algorithmic tools using recent graph structure 
 theory: most\nnotably\, we provide polynomial-time algorithms to 
 construct brambles\,\ngrid-like minors\, and tree-ordered webs in general 
 graphs of high\nenough treewidth.
SUMMARY:Siamak Tazari - Algorithmic Graph Minor Theory: Approximation\, 
 Parameterized Complexity\, and Practical Aspects
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100430T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100430T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1796002777.177
SEQUENCE:1
LAST-MODIFIED:20091022T115602Z
SUMMARY:Berit Grußien - Polynomial Time Algorithms for Constraint 
 Satisfaction Problems
PRIORITY:5
DTSTART:20090710T090000Z
DTEND:20090710T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:a6qvqr7ofaeftpn3okqbip6ius@google.com
SEQUENCE:3
LAST-MODIFIED:20091028T101024Z
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
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:14
DTSTAMP:20120412T114433Z
UID:c8e6fc74-709f-4ffc-ab6a-02214a1188bf
LAST-MODIFIED:20120412T114433Z
SUMMARY:Vincenz Priesnitz  - Diplomverteidigung: Baum- und Pfadweite 
 planarer Graphen und minimale verbotene Minoren
DTSTART;TZID=Europe/Paris:20120413T110000
DTEND;TZID=Europe/Paris:20120413T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20100415T135307Z
UID:20100415T135307Z-11805-2000-1-2@dublin
SEQUENCE:10
LAST-MODIFIED:20100721T133749Z
DESCRIPTION:The Exponential Time Hypothesis (ETH) says that deciding the 
 satisfiability of $n$-variable 3-CNF formulas requires time 
 $\\exp(\\Omega(n))$. We relax this hypothesis by introducing its counting 
 version #ETH\, namely that every algorithm that counts the satisfying 
 assignments requires time $\\exp(\\Omega(n))$.  We transfer the 
 sparsification lemma for $d$-CNF formulas to the counting setting\, which 
 makes #ETH robust.\n\nUnder this hypothesis\, we show lower bounds for 
 well-studied #P-hard problems: Computing the permanent of an $n\\times n$ 
 matrix with $m$ nonzero entries requires time $\\exp(\\Omega(m))$. 
 Restricted to 01-matrices\, the bound is $\\exp(\\Omega(m/\\log m))$. 
 Computing the Tutte polynomial of a multigraph with $n$ vertices and $m$ 
 edges requires time $\\exp(\\Omega(n))$ at points $(x\,y)$ with 
 $(x-1)(y-1)\\neq 1$ and $y\\notin\\{0\,\\pm 1\\}$. At points $(x\,0)$ 
 with $x \\not \\in \\{0\,\\pm 1\\}$ it requires time 
 $\\exp(\\Omega(n))$\, and if $x=-2\,-3\,\\ldots$\, it requires time 
 $\\exp(\\Omega(m))$.  For simple graphs\, the  bound is 
 $\\exp(\\Omega(m/\\log^3 m))$.
SUMMARY:Holger Dell - Exponential Time Complexity of the Permanent and 
 the Tutte Polynomial
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100730T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100730T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091208T085233Z
UID:20091208T085233Z-4161-2000-1-0@dublin
SEQUENCE:4
LAST-MODIFIED:20091208T075344Z
DESCRIPTION:We study the definability of finite graphs in first order 
 logic with two relation symbols for adjacency and equality of vertices. 
 The logical depth D(G) of a graph G is equal to the minimum quantifier 
 depth of a sentence defining G up to isomorphism. The logical width W(G) 
 is the minimum number of variables occurring in such a sentence. We 
 overview known estimates for these graph parameters and discuss their 
 relations to other research areas.
SUMMARY:Oleg Verbitsky - First-Order Complexity of Graphs (a Survey)
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091211T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20091211T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:5
DTSTAMP:20110126T231912Z
UID:040e46af-7ec1-45c3-88d5-6ab6864b1e3a
SEQUENCE:3
LAST-MODIFIED:20110126T231912Z
DESCRIPTION:We consider the edge- and vertex-isoperimetric problem on 
 finite and infinite hexagonal grids: For a subset A of the hexagonal grid 
 of given cardinality\, we give a lower bound for the number of edges 
 between A and its complement\, and lower bounds for the number of 
 vertices in the neighborhood of A and for the number of vertices in the 
 boundary of A. For the infinite hexagonal grid the given bounds are 
 tight.
SUMMARY:Berit Grußien - Isoperimetric Inequalities on Hexagonal Grids
DTSTART;TZID=Europe/Paris:20110128T110000
DTEND;TZID=Europe/Paris:20110128T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:mail@holger-dell.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1272553881.525
SEQUENCE:1
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:clogca6dnrjkviidakuhcna884@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T101028Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1702660997.396
SEQUENCE:2
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:vnmolrt3mpornkbcl3oo750pnc@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:Kord Eickmeyer - Algorithmische Rekonstruktion phylogenetischer 
 Bäume
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20080606T090000Z
DTEND:20080606T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20101222T140433Z
UID:8df96e22-7396-42cb-8df5-fcac027f100f
LAST-MODIFIED:20101222T140433Z
DESCRIPTION:Given an undirected graph G\, a collection (s_1\,t_1)\, ...\, 
 (s_k\,t_k) of pairs of vertices\, and an integer p\, the Edge Multicut 
 problem asks if there is a set S of at most p edges such that the removal 
 of S disconnects every s_i from the corresponding t_i. Vertex  Multicut 
 is the analogous problem where S is a set of at most p vertices. Our main 
 result is that both problems can be solved in time 2^{O(p3)} n^{O(1)}\, 
 i.e.\, fixed-parameter tractable parameterized by the size p of the 
 cutset in the solution.\n\nThis is joint work with Igor Razgon.
SUMMARY:Dániel Marx - Fixed-parameter tractability of multicut 
 parameterized by the size of the cutset
DTSTART;TZID=Europe/Paris:20101029T110000
DTEND;TZID=Europe/Paris:20101029T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:iv062njvot7lj83j4fr622hka4@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100901Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:d1bjadbm0ofuafi8ntc9tjbk68@google.com
SEQUENCE:1
LAST-MODIFIED:20100427T101132Z
SUMMARY:Dániel Marx (Budapest University of Technology and Economics) - 
 Movement Problems
STATUS:CONFIRMED
PRIORITY:5
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080611T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080611T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-1229176622.912
SEQUENCE:3
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
X-MOZ-GENERATION:5
DTSTAMP:20120112T094339Z
UID:a413063a-8ad7-4c37-8481-80251a531529
LAST-MODIFIED:20120112T094339Z
DESCRIPTION:The question of whether there is a polynomial time algorithm 
 deciding whether two graphs are isomorphic has been a one of the best 
 known open problems in theoretical computer science for more than forty 
 years. Indeed\, the graph isomorphism problem is one of the very few 
 natural problems in NP that is neither known to be in P nor known to be 
 NP-complete. The question is still wide open\, but a number of deep 
 partial results giving polynomial time algorithms for specific classes of 
 graphs are known. Many of them have been obtained through a group 
 theoretic approach that dominated the research on the graph isomorphism 
 problem since the early 1980s.\n\nAfter an introductory survey on the 
 graph isomorphism problem\, in my talk I will focus on approaches to the 
 graph isomorphism problem based on structural graph theory and 
 connections between logical definability and certain combinatorial 
 algorithms for the isomorphism problem. In particular\, I will speak 
 about two recent results: The first says that the Weisfeiler-Lehman 
 algorithm (a simple combinatorial algorithm) can be used to decide 
 isomorphism on graph classes with excluded minors in polynomial time. The 
 second says that isomorphism can be decided in polynomial time on graph 
 classes with excluded topological subgraphs.\n\n*** This is the talk I'll 
 give at SODA. No need to attend for those who'll be there. ***\n
SUMMARY:Martin Grohe - Structural and Logical Approaches to the Graph 
 Isomorphism Problem
DTSTART;TZID=Europe/Paris:20120113T110000
DTEND;TZID=Europe/Paris:20120113T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:3
DTSTAMP:20120106T160617Z
UID:3b9a5465-db96-4b17-824e-0033f086a8d0
LAST-MODIFIED:20120106T160617Z
DESCRIPTION:Baumweite ist ein Beispiel für ein Komplexitätsmaß von 
 Graphen. In diesem Vortrag wird das Komplexitätsmaß der Rangweite 
 vorgestellt. Viele NP-vollständige Graphenprobleme sind FPT\, wenn als 
 Parameter k die Rangweite des Eingabegraphen gewählt wird. Anders als 
 bei der Baumweite ist i.A. die Rangweite eines Subgraphen nicht kleiner 
 gleich der Rangweite des Ausgangsgraphen. Es wird gezeigt\, dass die 
 Rangweite eines Graphen (bis auf eine Differenz von maximal 1) mit der 
 Rangweite ihres Komplementgraphen übereinstimmt. \n\nEs sei $C$ eine 
 Graphklasse. Dann enthält die $MSO$-Theorie von $C$ alle $MSO$-Sätze\, 
 die für sämtliche Graphen aus $C$ gelten. Seese vermutete: Wenn die 
 $MSO$-Theorie von $C$ entscheidbar ist\, sind die Rangweiten der Graphen 
 in $C$ beschränkt. Courcelle und Oum konnten davon folgende 
 Abschwächung zeigen: Wenn die $C_2MSO$-Theorie von $C$ entscheidbar 
 ist\, dann haben ihre Graphen beschränkte Rangweite. Die Logik $C_2MSO$ 
 besitzt zu den sprachlichen Möglichkeiten von $MSO$ ein einstelliges 
 Relationssymbol Even\, welches für jede Menge ausdrückt\, ob diese 
 geradzahlig viele Elemente besitzt.\n
SUMMARY:Michael Bode - Rangweite von Graphen und eine Vermutung von 
 Seese
DTSTART;TZID=Europe/Paris:20120127T110000
DTEND;TZID=Europe/Paris:20120127T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20101222T140630Z
UID:24a1a1eb-441c-4bcc-bac7-66cef90caf7e
LAST-MODIFIED:20101222T140630Z
SUMMARY:Vincenz Priesnitz - Gitter und Baumweite
DTSTART;TZID=Europe/Paris:20101217T110000
DTEND;TZID=Europe/Paris:20101217T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:mail@holger-dell.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-460400107.942
LAST-MODIFIED:20091022T115602Z
SUMMARY:Anne Pilchowski - Quantitativer Vergleich zweier Arten von 
 Erreichbarkeitsgraphen von Intervall-Petrinetzen
PRIORITY:5
DTSTART:20090529T090000Z
DTEND:20090529T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:12
DTSTAMP:20120117T142524Z
UID:36e3a3d5-b5d4-407e-8a61-cce28e2f0023
LAST-MODIFIED:20120117T142524Z
DESCRIPTION:The existential $k$-pebble game characterizes the expressive 
 power of the existential-positive $k$-variable fragment of the infinitary 
 logic L_{\\infty \\omega}. The winner of the existential k-pebble game on 
 two given finite structures can easily be determined in time $O(n^{2k})$. 
 We show that there is no $O(n^{(k-3)/12})$ time algorithm that decides 
 which player can win the existential k-pebble game on two given 
 structures. This lower bound is unconditional and does not rely on any 
 unproven complexity theoretic assumptions.\n\nEstablishing strong 
 $k$-consistency is a well-known heuristic for solving the constraint 
 satisfaction problem (CSP). By the game characterization of Kolaitis and 
 Vardi our result implies that there is no $O(n^{(k-3)/12})$ time 
 algorithm that decides if strong $k$-consistency can be established for a 
 given CSP-instance.\n
SUMMARY:Christoph Berkholz - A lower bound for the existential k-pebble 
 game and k-consistency tests
DTSTART;TZID=Europe/Paris:20120120T110000
DTEND;TZID=Europe/Paris:20120120T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:dsapf5i9h1p7od0e0af3270qc0@google.com
LAST-MODIFIED:20091022T115602Z
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:\n<a href=\"http:
 //arxiv.org/PS_cache/arxiv/pdf/0902/0902.3780v1.pdf\">http:
 //arxiv.org/PS_cache/arxiv/pdf/0902/0902.3780v1.pdf</a>\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
CREATED:20120624T201823Z
X-MOZ-GENERATION:16
DTSTAMP:20120419T130754Z
UID:287bfd6a-ff84-4671-987c-59b00d1c5233
LAST-MODIFIED:20120419T130754Z
DESCRIPTION:The Subgraph Isomorphism problem asks\, given a host graph G 
 on n vertices and a pattern graph P on k vertices\, whether G contains a 
 subgraph isomorphic to P. The restriction of this problem to planar 
 graphs has often been considered.  After a sequence of improvements\, the 
 current best algorithm for planar graphs is a linear time algorithm by 
 Dorn (STACS '10)\, with complexity  $2^{O(k)}O(n)$.\n\nWe generalize this 
 result\, by giving an algorithm of the same complexity for graphs that 
 can be embedded in surfaces of bounded genus. In addition\, we simplify 
 the algorithm and analysis. The key to these improvements is the 
 introduction of surface split decompositions for bounded genus graphs\, 
 which generalize sphere cut decompositions for planar graphs. We extend 
 the algorithm for the problem of counting and generating all subgraphs 
 isomorphic to P\, even for the case where P is disconnected. This answers 
 an open question by Eppstein (JGAA '99).\n
SUMMARY:Paul Bonsma - Surface Split Decompositions and Subgraph 
 Isomorphism in Graphs on Surfaces
DTSTART;TZID=Europe/Paris:20120427T110000
DTEND;TZID=Europe/Paris:20120427T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:4
DTSTAMP:20110104T153007Z
UID:10e49733-b388-49f0-b1ff-c3f238d19885
SEQUENCE:1
LAST-MODIFIED:20110104T153007Z
DESCRIPTION:Consider the problem of approximating the number of 
 independent sets in graphs  of maximum degree D. This problem has a 
 polynomial time algorithm if D is at most 5 (as shown by Weitz in 2006) 
 and has just very recently been shown (Sly 2010) to be NP-hard for D >= 
 6. This unusual point of PTIME-to-NP-hardness transition (note that exact 
 problem is hard already for D >= 3) corresponds to a phase transition 
 phenomenon studied in statistical physics: the occurrence of multiple 
 Gibbs measures on the infinite D-regular tree. In fact\, both\, Weitz' 
 PTIME algorithm for the D >= 5 case and Sly's NP-hardness proof draw 
 heavily from intuition and methodology developed by statistical 
 physicists.\n\nIn my talk I will give a gentle introduction to the matter 
 and an overview of the above two results. With independent sets being a 
 special example of so-called spin systems\, I will further discuss the 
 possibilities of applying the techniques developed to other such systems 
 such as\, e.g. the Ising model.
SUMMARY:Marc Thurley (UC Berkeley) - Phase Transitions and The Complexity 
 of Spin Systems
LOCATION:Haus 3\, Raum 113
DTSTART;TZID=Europe/Berlin:20110107T110000
DTEND;TZID=Europe/Berlin:20110107T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
ATTENDEE;CN="Mitarbeiterseminar Logik in der Informatik";RSVP=FALSE;
 PARTSTAT=ACCEPTED;ROLE=REQ-PARTICIPANT;X-UID=137686248:mailto:
 28c074ohvkqngj13v90i72kb3s@group.calendar.google.com
DTSTAMP:20091022T134353Z
UID:52p15r4c4htc8qk2tk43fl1bk0@google.com
SEQUENCE:2
LAST-MODIFIED:20091028T101017Z
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
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:3
DTSTAMP:20110511T165302Z
UID:5b990c64-fda6-4426-855b-3badd0dcfd17
SEQUENCE:1
LAST-MODIFIED:20110511T165302Z
DESCRIPTION:Lots of data leads to lots of difficulties. When storage 
 space\, bandwidth\, or processing power are limited\, we often use data 
 reduction techniques to reduce the size and the resolution of data\, or 
 we compile small summaries and statistics that we hope still contain the 
 information we want to keep or transmit. Kernelization is a 
 mathematically rigorous framework for preprocessing data by creating 
 small summaries. In particular\, kernelization allows us to make precise 
 which core information of the data we want to preserve in the data 
 reduction step\, and it allows us to analyze the amount of storage space 
 that is required to store the summaries\, called kernels\, in the worst 
 case.\n\nThe kernelization framework was proposed by Downey and Fellows. 
 It has been studied in the setting where the information we want to 
 preserve is an NP-hard property of the input\, and where we only have 
 polynomial time to compute the kernels. In the first part of the talk\, 
 we will see some examples of how kernels can be computed in that setting. 
 Moreover\, we will informally discuss a result from my thesis that gives 
 us a complexity-theoretic reason to believe that the kernelization 
 algorithms from the first part of the talk are essentially optimal.
SUMMARY:Holger Dell - Data Reduction for Hard Problems
DTSTART;TZID=Europe/Paris:20110513T140000
DTEND;TZID=Europe/Paris:20110513T160000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
ATTENDEE;CN="Holger Dell";RSVP=FALSE;PARTSTAT=ACCEPTED;
 ROLE=REQ-PARTICIPANT;X-UID=137618728:mailto:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-993726071.861
SEQUENCE:5
LAST-MODIFIED:20091028T100032Z
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:m5085btk0e6eqq4u181scv22k4@google.com
SEQUENCE:4
LAST-MODIFIED:20091028T100927Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-365779121.187
SEQUENCE:2
LAST-MODIFIED:20091022T115602Z
SUMMARY:Mark Weyer - Games\, unravellings\, tree decompositions\, ... and 
 consistencies for CSP
PRIORITY:5
DTSTART:20090717T090000Z
DTEND:20090717T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:7aoaf961h1kckfijvvqtaq5n5s@google.com
SEQUENCE:4
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20100415T135239Z
UID:20100415T135239Z-11805-2000-1-1@dublin
SEQUENCE:7
LAST-MODIFIED:20100629T090306Z
DESCRIPTION:Das wohl wichtigste offene Problem im Bereich der 
 deskriptiven\nKomplexitätstheorie ist die Frage nach einer 
 (handhabbaren) Logik\, die\nexakt alle in Polynomialzeit berechenbaren 
 Klassen von Strukturen\ncharakterisiert. Sollte eine solche Logik nicht 
 existieren\, so würde\nsich unmittelbar ergeben\, dass die 
 Komplexitätsklassen PTIME und NP\nungleich sind\, da eine entsprechende 
 logische Charakterisierung für NP\nbekannt ist. Existiert eine solche 
 Logik aber\, dann ermöglicht diese\nden Vergleich der beiden 
 Komplexitätsklassen mit Methoden der\nendlichen Modelltheorie. Außerdem 
 würde eine solche Logik eine\nAnfragesprache für Datenbanken 
 implizieren\, in der sich exakt alle\neffizient (d.h. in Polynomialzeit) 
 berechenbaren Anfragen ausdrücken\nlassen\, aber keine weiteren\, was 
 eine positive Antwort auf eine offene\nFrage von Chandra und Harel aus 
 dem Jahre 1982 wäre.\n\nMein Vortrag wird zunächst die grundlegenden 
 Resultate in diesem\nBereich beleuchten. Vor deren Hintergrund ergeben 
 sich zwei mögliche\nForschungsrichtungen\, die eine Beantwortung der 
 obigen Frage zum Ziel\nhaben und zu denen meine Dissertation einen 
 Beitrag leistet: die\npräzise Charakterisierung von PTIME auf 
 eingeschränkten Klassen von\nStrukturen\, und der Entwurf von Logiken 
 mit neuartigen\nAusdrucksstärken.\n\nIm ersten Bereich erläutere ich 
 meine Charakterisierung von PTIME auf\nder Klasse der Intervallgraphen 
 durch die Logik FP+C\, die lediglich\neinfache induktive Definitionen und 
 Zählen beherrscht. Das Ergebnis\ngibt Aufschluss über die Anwendbarkeit 
 modularer Graphenzerlegungen\nfür die Kanonisierung von Graphenklassen. 
 Aus dem Resultat ergibt sich\nauch eine logische Charakterisierung der 
 Komplexitätsklasse LOGSPACE\nauf der Klasse der 
 Einheitsintervallgraphen. Zudem wurden die\nvorgestellten Techniken in 
 einer gemeinsamen Arbeit mit Köbler\,\nKuhnert und Verbitsky 
 angewendet\, um zu zeigen\, dass\nIntervallgraphenisomorphie und 
 -kanonisierung mit nur logarithmischem\nPlatz möglich sind.\n\nIm 
 zweiten Bereich stelle ich logische Operatoren vor\, die den Rang\nvon 
 Matrizen über endlichen Körpern berechnen und so gewissermaßen\neine 
 Verallgemeinerung der Fähigkeit zu zählen darstellen. Logiken 
 mit\nsolchen Operatoren\, sogenannte Ranglogiken\, haben eine 
 höhere\nAusdrucksstärke als FP+C\, da sie alle bekannten 
 Konstruktionen\nausdrücken können\, die zeigen\, dass FP+C schwächer 
 ist als PTIME.\nSomit sind Rangberechnungen eine intrinsische Fähigkeit 
 von\nPolynomialzeitalgorithmen\, deren Verständnis für die Beantwortung 
 der\nursprünglichen Frage wichtig ist. Neben grundlegenden 
 Eigenschaften\nvon Rangoperatoren im logischen Kontext zeige ich\, 
 dass\nRangoperationen eine strikt größere Ausdrucksstärke haben 
 bei\nzunehmender Stelligkeit der betrachteten Matrizen. Schließlich 
 schlage\nich eine Brücke zur klassischen Komplexitätstheorie\, indem 
 ich\nerkläre\, wie Variationen von Ranglogiken 
 verschiedene\nKomplexitätsklassen zwischen LOGSPACE und PTIME über der 
 Klasse der\ngeordneten Strukturen charakterisieren. Die meisten dieser 
 Ergebnisse\nwurden in einer gemeinsamen Arbeit mit Dawar\, Holm und 
 Grohe\nveröffentlicht.
SUMMARY:Bastian Laubner - Die Struktur von Graphen und neue Logiken für 
 die präzise Charakterisierung von Polynomialzeit
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100618T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100618T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:1
DTSTAMP:20110504T095537Z
UID:9366e3eb-430f-4878-a868-1582069be220
LAST-MODIFIED:20110504T095537Z
DESCRIPTION:We present two aspects of the use of randomisation in 
 computational complexity theory.\n\nIn the first part\, we review certain 
 gap-introduction reductions which were used to proof inapproximability 
 results. Because these reductions were originally stated as randomised 
 reductions\, they implied non-approximability results under a complexity 
 hypothesis involving randomised complexity classes. We were able to 
 derandomise them and therefore weaken the hypotheses to ones about 
 deterministic complexity classes.\n\nIn the second part we show how 
 descriptive complexity can be used to shed light on questions about 
 randomised complexity classes. To this end we define randomised logics as 
 a counterpart to randomised complexity classes and show that we can 
 indeed capture several important randomised complexity classes by these 
 logics. We then show derandomisation results\, both positive and 
 negative\, for these randomised logics. In particular\, we can prove 
 unconditionally that a certain uniform variant of randomised AC0 can 
 _not_ be derandomised.\n\n(joint work with Martin Grohe\, Magdalena 
 Grüber\, Kristoffer Arnsfelt Hansen and Elad Verbin).
SUMMARY:Kord Eickmeyer - Randomisation and Derandomisation in Complexity 
 Theory
DTSTART;TZID=Europe/Berlin:20110506T110000
DTEND;TZID=Europe/Berlin:20110506T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:qkadcbeq4mj58lebbtbom5d2q8@google.com
SEQUENCE:3
LAST-MODIFIED:20091028T100908Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:mlnpe8i58e1gv89urnmnetrtpo@google.com
SEQUENCE:1
LAST-MODIFIED:20091028T100853Z
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.
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
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
X-MOZ-GENERATION:1
DTSTAMP:20111206T201633Z
UID:34d534cd-b417-4b56-ba3a-90ff0e3eb002
LAST-MODIFIED:20111206T201633Z
SUMMARY:Daniel Kirsten - Rank Logics over Empty Signatures: First 
 Results
DTSTART;TZID=Europe/Paris:20111209T110000
DTEND;TZID=Europe/Paris:20111209T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-8511662.260
SEQUENCE:1
LAST-MODIFIED:20091022T115602Z
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
CREATED:20120624T201823Z
DTSTAMP:20100311T093254Z
UID:20100311T093254Z-12831-2000-1-0@dublin
SEQUENCE:7
LAST-MODIFIED:20100315T122448Z
DESCRIPTION:The currently fastest deterministic algorithm for k-SAT is 
 based on deterministic local search\, introduced by Dantsin et al. 
 (2002). Basically the same algorithm can also be used to solve 
 (d\,k)-CSPs (constraint satisfaction problems)\, which are the same as 
 CNF formulas\, but with d instead of 2 'truth values'.\n\nIn the talk\, I 
 will present this algorithm and show a surprisingly simple way to 
 substantially improve its running time. The idea is to change the notion 
 of Hamming distance\, thus changing the neighborhood relation between 
 assignments (colorings) and the notion Hamming balls.
SUMMARY:Dominik Scheder - Using a Skewed Hamming Distance to Speed Up 
 Deterministic Local Search
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100416T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20100416T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
ORGANIZER;CN="Holger Dell":MAILTO:dell@informatik.hu-berlin.de
DTSTAMP:20091022T134353Z
UID:KOrganizer-2103692823.226
SEQUENCE:1
LAST-MODIFIED:20091022T115602Z
SUMMARY:Mark Weyer - Baumweitechniken für FO^k
PRIORITY:5
DTSTART:20090626T090000Z
DTEND:20090626T110000Z
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:pqnj2aroejrqfrb8vumsraq1rc@google.com
SEQUENCE:1
LAST-MODIFIED:20100427T101201Z
SUMMARY:Tomer Kotek (Technion\, Israel) - Connection matrices of numeric 
 graph invariants
STATUS:CONFIRMED
PRIORITY:5
DTSTART;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080507T110000
DTEND;TZID=/softwarestudio.org/Tzfile/Europe/Berlin:20080507T130000
TRANSP:OPAQUE
END:VEVENT
BEGIN:VEVENT
CREATED:20120624T201823Z
DTSTAMP:20091022T134353Z
UID:3ggdtghhij71v4g2aho7fp5mio@google.com
LAST-MODIFIED:20091022T115602Z
SUMMARY:Isolde Adler - Compactness of tree-width and other hypergraph 
 invariants
STATUS:CONFIRMED
PRIORITY:5
DTSTART:20080516T090000Z
DTEND:20080516T110000Z
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR