BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20140330T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20131027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260504T123413Z
UID:50040450b5ab2@ist.ac.at
DTSTART:20140113T163000
DTEND:20140113T173000
DESCRIPTION:Speaker: Emo Welzl\nAbstract: The general theme underlying the 
 talk is the following question: Given a set of constraints\, how\nmuch int
 erleaving of these constraints (relative to how serious these constraints 
 are) is necessary\nso that all of them cannot be satisfied simultaneously?
 \nFor a concrete setting we consider boolean formulas in conjunctive norma
 l form (CNF)\, where the\nclauses play the role of constraints. If all cla
 uses are large\, it needs many clauses to obtain an\nunsatisfiable formula
 \; moreover\, these clauses have to interleave. We review quantitative res
 ults\nfor the amount of interleaving required\, many of which rely on the 
 Lovász Local Lemma\, a\nprobabilistic lemma with many\napplications in co
 mbinatorics.\nIn positive terms\, we are interested in simple combinatoria
 l conditions which guarantee for a CNF\nformula to be satisfiable. The cri
 teria obtained are nontrivial in the sense that even though they\nare easy
  to check\, it is by far not obvious how to compute a satisfying assignmen
 t efficiently if the\nconditions are fulfilled\; until recently\, it was n
 ot known how to do so. It is also remarkable that\nwhile deciding\nsatisfi
 ability is trivial for formulas that satisfy the conditions\, a slightest 
 relaxation of the\nconditions leads us into the territory of NP-completene
 ss.\nThis is a survey with results by Heidi Gebauer\, Robin Moser\, Domini
 k Scheder\, and Gábor Tardos\,\namong others.
LOCATION:Raiffeisen Lecture Hall\, Central Building\, ISTA
ORGANIZER:ihetzenauer@ist.ac.at
SUMMARY:Emo Welzl: Institute Colloquium: When conflicting constraints can b
 e resolved - the local lemma
URL:https://talks-calendar.ista.ac.at/events/500
END:VEVENT
END:VCALENDAR