[Colloquium] Tomorrow: Purdy/MS Presentation/April 24, 2008

[Margaret Jaffey]

Just a reminder about Eric Purdy's MS Presentation tomorrow.

-----------------------------------------------------------------------
Date:  Thursday, April 24, 2008

Time:  1:30 p.m.

Place:  Ryerson 251

M.S. Candidate:  Eric Purdy

M.S. Paper Title:  Unique 3-CSP's on Expander Hypergraphs are Easy

Abstract:
In this paper, we examine the hardness of approximating constraint
satisfaction problems with three-variable constraints, known as
3-CSP's. We are specifically interested in 3-CSP's whose constraints
are unique, which means that for any assignment to two of the
variables, there is a unique assignment to the third satisfying the
constraint. Our main result is an approximation algorithm that for
unique 3-CSP's that does well on the class of unique 3-CSP's whose
underlying hypergraph has expansion properties. Our approximation
algorithm does better on these instances than is possible in general,
since a result of H\aa stad gives a hardness of approximation result
for this question.

We also relate this question to the Unique Games Conjecture, giving a
reduction from unique 3-CSP's to Unique Games. This reduction only
works in the presence of the expansion property. We give a weakened
form of the UGC (where the soundness parameter is constant rather than
arbitrarily small), and prove that a hardness result for unique
3-CSP's on expanding hypergraphs would imply this weak UGC.

We also explore hypergraph expansion, proving that random hypergraphs
of an appropriate density meet our expansion criteria with high
probability, and giving two constructions (one fully explicit, and one
semi-random) of such hypergraphs.

Advisor:  Prof. Laszlo Babai

A draft copy of Eric Purdy's MS paper is available in Ry 156.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=