[Colloquium] Reminder: Worah/Dissertation Defense/May 1, 2013

[Margaret Jaffey]

This is a reminder about Pratik's defense on Wednesday morning.

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Pratik Worah

Date:  Wednesday, May 1, 2013

Time:  10:15 AM

Place:  Ryerson 277

Title: Approximation Resistance in Optimization Hierarchies: Beyond
Linear Predicates

Abstract:
In the 1970s, Cook and Levin showed that it was impossible to
efficiently decide the satisfiability of $3$-SAT instances, assuming
P$\neq$NP. Based on their work, Karp and others quickly showed a host
of other problems to be computationally hard. In particular, Schaefer
was able to show that most $k$-ary boolean predicates besides
disjunction, which corresponds to $k$-SAT, are also hard. Schaefer
gave a complete classification of boolean predicates, depending on
whether satisfiability checking for their corresponding constraint
satisfaction problem (CSP) is easy or hard.

A couple of decades later, the notion of effcient approximation
algorithms stimulated the investigation of the optimization version of
the satisfiability checking problem for CSPs. Building on several
outstanding results, H\aa stad was able to show that MAX $3$-LIN is
approximation resistant. In other words, H\aa stad showed that if one
wants to efficiently find an assignment that simultaneously satisfies
a maximum fraction of constraints in a MAX $3$-LIN instance then the
best strategy is to simply pick a random $0$-$1$ assignment for its
variables, assuming P$\neq$NP. Several results have built upon the
work of H\aa stad, but a complete understanding of approximation
resistant predicates still seems quite far-off.

A few years after H\aa stad's results, Arora, Bollob\'{a}s and
Lov\'{a}sz initiated another avenue in the study of the limitations of
approximation algorithms. Since many approximation algorithms are
based on rounding Linear or Semidefinite relaxations, their approach
was used to show that most such relaxations have a large integrality
gap, which precludes any efficient approximation algorithm from
beating the random assignment solution for MAX $3$-LIN by rounding a
Linear (LP) or Semidefinite program (SDP).

More recently, the results of Raghavendra together with the Unique
Games Conjecture of Khot have shown that the above two approaches are
closely related and even complimentary to each other.

Thus far, the works of H\aa stad, Chan, Schoenebeck, Tulsiani and
others have shown that it is hard to beat the random assignment for
linear predicates like $k$-LIN and its conjunctions, and also
predicates like $k$-SAT, which are implied by linear predicates. In
this thesis, we show similar bounds for larger classes of predicates
with the aim to classify all boolean predicates as hard or easy, under
various notions of hardness. In particular, we show the following
results.

-For CSPs on pairwise uniform predicates, which subsume the class of
linear predicates, we show that semidefinite relaxations, obtained
after a linear number of rounds of the Lov\'{a}sz-Schrijver SDP
hierarchy, can not beat the random assignment solution.

-H\aa stad introduced the weaker notion of somewhat approximation
resistant predicates to make progress on the question of approximation
resistance. We extend H\aa stad's results, and give a more precise
quantitative characterization of somewhat approximation resistant
predicates. Our results also hold in the context of the Lasserre SDP
relaxations.

-We introduce a stronger notion of approximation resistance, which we
call strong approximation resistance. We prove integrality gaps for
various LP and SDP relaxations for strongly approximation resistant
predicates. Moreover, we completely characterize all strongly
approximation resistant predicates, assuming the Unique Games
Conjecture.

-We investigate lift and project hierarchies with more general lift
operations than the usual Lov\'{a}sz-Schrijver hierarchies. We are
able to show that known lower bound techniques can be used to prove
integrality gaps for such hierarchies, as well.

Pratik's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#pworah

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