DISSECTION: A NEW PARADIGM FOR SOLVING BICOMPOSITE SEARCH PROBLEMS
, Weizmann Institute
Date: Friday, October 18, 2013
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Host: Shafi Goldwasser
Contact: Holly A Jones, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/381
Speaker URL: None
TALK: DISSECTION: A NEW PARADIGM FOR SOLVING BICOMPOSITE SEARCH PROBLEMS
Abstract: Most combinatorial search problems can be described by 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 given initial state into the desired final state. One can always solve such problems by trying out all the possible sequences of actions, but in many cases it is possible to exploit special properties of the states and actions in order to lower the exponential complexity of exhaustive search. In this talk I will introduce the new notion of bicomposite search problems, whose solution can be partitioned both along the action and the state dimensions, and show that such problems can be solved with a new algorithmic paradigm, which we call dissection with greatly reduced com-binations of time and space complexities. To demonstrate the wide applicability of these ideas, I will show how to improve the best-known algorithms for untangling Rubik's cube, for solving various set partition problems, and for breaking multiple encryption schemes.
*Joint work with Itai Dinur, Orr Dunkelman, and Nathan Keller.
Created by Holly A Jones at Friday, October 11, 2013 at 11:36 AM.