[Colloquium] Revised Abstract: Purdy/MS Presentation/April 24, 2008 (Tomorrow)

[Margaret Jaffey]

This announcement of Eric Purdy's MS Presentation includes a revised  
abstract.

-----------------------------------------------------------------------
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.

We relate this question to the Unique Games Conjecture, giving a
reduction from unique 3-CSP's to Unique Games. This reduction only
works when the underlying hypergraph of the 3-CSP has a (hypergraph)
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 give a precise formulation
of the desired hardness result as a conjecture, which we call the
Expanding Unique 3-CSP's Conjecture. We also prove the converse, that
the weak version of the UGC would imply our conjecture, so that the
two conjectures are completely equivalent. This equivalence is our
first main result.

Our second main result is an approximation algorithm for unique
3-CSP's that does well on instances whose underlying hypergraphs are
expanders. 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. In particular,
this result gives an answer to an open-ended question posed
by Khot and Naor in 2007.

We also explore hypergraph expansion, proving that random hypergraphs
of an appropriate density meet our expansion criteria with high
probability, and giving two algebraic 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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=