Israel CS THEORY DAY

Open University of Israel

Division of Computer Science

 

Date: 17.3.08

Speaker: Muli Safra

Title: On Parallel-Repetition, Unique-Game and Max-Cut

Abstract:

We investigate a reduction from the Max-Cut problem to the Unique-Game problem via Parallel Repetition.

Such a reduction would imply the two problems` complexity is related, and both may be representatives of a class of problems that are not in P, neither NP-hard.

We manage to show a variation of the Parallel Repetition scheme to be applicable, however, only when the Max-Cut graph is a good expander.

Joint work with Oded Schwartz.