BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20130310T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20131103T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20200401T114341Z
UID:c38110d7-76ae-4e1b-98fb-ba6a53849719
DTSTART;TZID=America/New_York:20131018T103000
DTEND;TZID=America/New_York:20131018T120000
CREATED:20131011T113636
DESCRIPTION:Abstract: Most combinatorial search problems can be described b
y a collection of possible states\, a list of possible actions\, which map
each current state into some next state\, and a pair of initial and final
states. The problem is to find a sequence of actions\, which map the give
n initial state into the desired final state. One can always solve such pr
oblems by trying out all the possible sequences of actions\, but in many c
ases it is possible to exploit special properties of the states and action
s in order to lower the exponential complexity of exhaustive search. In th
is talk I will introduce the new notion of bicomposite search problems\, w
hose solution can be partitioned both along the action and the state dimen
sions\, and show that such problems can be solved with a new algorithmic p
aradigm\, which we call dissection with greatly reduced com-binations of t
ime and space complexities. To demonstrate the wide applicability of these
ideas\, I will show how to improve the best-known algorithms for untangli
ng Rubik's cube\, for solving various set partition problems\, and for bre
aking multiple encryption schemes.\n\n*Joint work with Itai Dinur\, Orr Du
nkelman\, and Nathan Keller.\n
LAST-MODIFIED:20131104T103446
LOCATION:32-G449
SUMMARY:DISSECTION: A NEW PARADIGM FOR SOLVING BICOMPOSITE SEARCH PROBLEMS
URL:https://calendar.csail.mit.edu/events/116296
END:VEVENT
END:VCALENDAR