### DIMACS Theoretical Computer Science Seminar

Title: Real complex semidefinite programming and its application to circular arrangements

Speaker: **Alantha Newman**, DIMACS

Date: Wednesday, December 10, 2008 11:00-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We consider the problem of arranging elements on a circle so as to
preserve specified pairwise distances. Given a set of equations of
the form x_v - x_u = c (mod p), we address the objective of
maximizing a linear payoff function depending on how close x_v-x_u
actually is to c, rather than the standard payoff function of '1' or
'0', if equation is true or false, respectively.

We show that this problem can be approximated to within .854 using
semidefinite programming. Since the problem can be viewed as a strict
generalization of the Max-Cut problem, this is a near optimal
approximation ratio assuming the Unique-Games Conjecture. Our main
contribution is that we show how the framework of complex semidefinite
programming can be applied to round a ``standard'' semidefinite
programming relaxation for our problem, even though we do not know how
to model our problem with the complex roots of unity, as is standard
in most applications of complex semidefinite programming.

(Joint work with Konstantin Makarychev.)