[Colloquium] Worah/MS Presentation/May 5, 2011

[Margaret Jaffey]

This is an announcement of Pratik Worah's MS Presentation.

------------------------------------------------------------------------------
Date:  Thursday, May 5, 2011

Time:  11:00 AM

Place:  Ryerson 277

M.S. Candidate:  Pratik Worah

M.S. Paper Title: Some Problems related to Proof Complexity and
Optimization

Abstract:
Lovasz and Schjriver introduced several lift and project methods for
$0$-$1$ integer programs, now collectively known as Lovasz-Schjriver
($LS$) hierarchies. Several lower bounds have since been proven for
the rank/depth of various linear programming relaxations in the $LS$
hierarchy. In this thesis we study lower bounds in the more general
$LS_*$ hierarchy, which was first investigated by Grigoriev et al. In
particular we show that the $PHP$ inequalities have a $\log_2 n$ depth
refutation in $LS_*$ and we prove that this is tight. We also extend
the strong rank lower bounds for Max-cut, Sparsest cut etc studied in
Charikar et al. for Sherali-Adams to weaker rank lower bounds in
$LS_*$ hierarchy.

Pratik's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=