[Colloquium] Reminder: Rajendran/MS Presentation/May 25, 2018

[Margaret Jaffey via Colloquium]

This is a reminder about Goutham's MS Presentation on Friday.

------------------------------------------------------------------------------
Date:  Friday, May 25, 2018

Time:  2:30 PM

Place:  Ryerson 277

M.S. Candidate:  Goutham Rajendran

M.S. Paper Title: Combinatorial Optimization via the Sum of Squares
hierarchy

Abstract:
We study the Sum of Squares (SoS) Hierarchy with a view towards
combinatorial optimization. We survey the use of the SoS hierarchy to
obtain approximation algorithms on graphs using their spectral
properties. We present a simplified proof of the result of Feige and
Krauthgamer on the performance of the hierarchy for the Maximum Clique
problem on random graphs. We also present a result of Guruswami and
Sinop that shows how to obtain approximation algorithms for the
Maximum Bisection problem on low threshold-rank graphs.

We study inapproximability results for the SoS hierarchy for general
constraint satisfaction problems and problems involving graph
densities such as the Densest k-subgraph problem. We improve the
existing inapproximability results for general constraint satisfaction
problems in the case of large arity, using stronger probabilistic
analyses of expansion of random instances. We examine connections
between constraint satisfaction problems and density problems on
graphs. Using them, we obtain new inapproximability results for the
hierarchy for the Densest k-subhypergraph problem and the Minimum
p-Union problem, which are proven via reductions.

We also illustrate the relatively new idea of pseudocalibration to
construct integrality gaps for the SoS hierarchy for Maximum Clique
and Max K-CSP. The application to Max K-CSP that we present is known
in the community but has not been presented before in the literature,
to the best of our knowledge.

Goutham's advisors are Prof. Janos Simon and Prof. Madhur Tulsiani

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#goutham

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