### May 30, Wednesday 14:15, Room 303, Jacobs Building

** Title: Improved Algorithms for Composite Problems
**

**Lecturer: **Itai Dinur

**Affiliation :** Weizmann Institute

** Title: Improved Algorithms for Composite Problems
**

**Lecturer: **Itai Dinur

**Affiliation :** Weizmann Institute

The meet-in-the-middle (MITM) approach (Merkle and Hellman, 1981) suggests that in such problems, one can obtain the time/memory tradeoff curve TM=N (where N is the number of possible solutions, and T, M are the time and memory complexities of the algorithm). In the last thirty years, several generic algorithms improved over the basic MITM approach and achieved the curve TM=N^{3/4} for specific values of M.

In this talk we show that surprisingly, the curve TM=N^{3/4} is not optimal. We achieve a better curve of TM < N^{3/4} for any M < N^{1/4}, and in particular, obtain TM=N^{5/7} with M=N^{1/7}. Our results are obtained by a new algorithm called dissection, in which the problem is divided into several sub-problems by guessing (parts of) intermediate values. An interesting feature of the technique is that the best results are obtained by division into "exotic" numbers of parts, such as 7 and 11, rather than to 2^k parts (as was common in previous works).

Joint work with Orr Dunkelman, Nathan Keller and Adi Shamir.