BEGIN:VCALENDAR
VERSION:2.0
PRODID:www.dresden-science-calendar.de
METHOD:PUBLISH
CALSCALE:GREGORIAN
X-MICROSOFT-CALSCALE:GREGORIAN
X-WR-TIMEZONE:Europe/Berlin
BEGIN:VTIMEZONE
TZID:Europe/Berlin
X-LIC-LOCATION:Europe/Berlin
BEGIN:DAYLIGHT
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
DTSTART:19810329T030000
RRULE:FREQ=YEARLY;INTERVAL=1;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
DTSTART:19961027T030000
RRULE:FREQ=YEARLY;INTERVAL=1;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:DSC-15759
DTSTART;TZID=Europe/Berlin:20190621T110000
SEQUENCE:1561154911
TRANSP:OPAQUE
DTEND;TZID=Europe/Berlin:20190621T120000
URL:https://dresden-science-calendar.de/calendar/en/detail/15759
LOCATION:MPI-CBG\, Pfotenhauerstraße 10801307 Dresden
SUMMARY:Ercsey-Ravasz: A continuous-time Max-SAT solver with high analog pe
 rformance
CLASS:PUBLIC
DESCRIPTION:Speaker: Dr. Maria Ercsey-Ravasz\nInstitute of Speaker: Babes-B
 olyai University\, Romania\nTopics:\n\n Location:\n  Name: MPI-CBG (CSBD S
 R Top Floor)\n  Street: Pfotenhauerstraße 108\n  City: 01307 Dresden\n  P
 hone: +49 351 210-0\n  Fax: +49 351 210-2000\nDescription: Many real-life 
 optimization problems can be formulated in Boolean logic as MaxSAT\, a cla
 ss of problems where the task is finding Boolean assignments to variables 
 satisfying the maximum number of logical constraints. Since MaxSAT is NP-h
 ard\, no algorithm is known to efficiently solve these problems. Here we p
 resent a continuous-time analog solver for MaxSAT and show that the scalin
 g of the escape rate\, an invariant of the solver’s dynamics\, can predi
 ct the maximum number of satisfiable constraints\, often well before findi
 ng the optimal assignment. Simulating the solver\, we illustrate its perfo
 rmance on MaxSAT competition problems\, then apply it to two-color Ramsey 
 number R(m\, m) problems. Although it finds colorings without monochromati
 c 5-cliques of complete graphs on N &amp\;#8804\; 42 vertices\, the best c
 oloring for N = 43 has two monochromatic 5-cliques\, supporting the conjec
 ture that R (5\, 5) = 43. This approach shows the potential of continuous-
 time analog dynamical systems as algorithms for discrete optimization. As 
 another interesting example we present a Sudoku solver based on this algor
 ithm and show how it helps us define  a type of  \"Richter scale\" to char
 acterize the hardness of Sudoku problems.
DTSTAMP:20260507T042203Z
CREATED:20190308T000956Z
LAST-MODIFIED:20190621T220831Z
END:VEVENT
END:VCALENDAR