Dissection: A New Paradigm for Solving Bicomposite Search Problems

Friday, October 18, 2013 - 10:30am to 12:00pm
Adi Shamir, Weizmann Institute of Science

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.