DISSECTION: A NEW PARADIGM FOR SOLVING BICOMPOSITE SEARCH PROBLEMS

Speaker: Adi Shamir , Weizmann Institute

Date: Friday, October 18, 2013

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Shafi Goldwasser

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/381

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security Seminar Seminars Fall 2013 / Spring 2014.

Created by Holly A Jones Email at Friday, October 11, 2013 at 11:36 AM.