Israel CS THEORY DAY
Open University of
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.