[talks] R Manokaran general exam

Melissa M Lawson mml at CS.Princeton.EDU
Tue Apr 29 13:26:59 EDT 2008

Rajsekar Manokaran will present his research seminar/general exam on Monday May 5 
at 2PM in Room 402.  The members of his committee are:  Sanjeev Arora (advisor), 
Moses Charikar, and Boaz Barak.  Everyone is welcome to attend his talk, and those 
faculty wishing to remain for the oral exam following are welcome to do so.  His abstract
reading list appear below.


Mathematical relaxations  are one of  the most powerful tools  used in designing
approximation algorithms for hard combinatorial optimization problems.  For  example,
linear programming  relaxations have provided
the  best  approximation  algorithms   known  for  a  huge  number  of
optimization problems.  More recently, for some optimization problems,
semidefinite  relaxations  have   been  used  to  obtain  breakthrough
improvements in the approximation  factor.  This work investigates the limits  on
approximations  achieved  by mathematical  relaxations  of
combinatorial  optimization   problems  and  their   relation  to  the
computation hardness of approximating them.

For a small yet quite general set of problems, a direct way to convert integrality gaps
for a linear  programming relaxation of  the problem into  a computational hardness
result under  a certain  conjecture is shown.  This problem, known as  metric labeling is
a generalization of classification problems  with pairwise constraints.  In  this work, it
is shown that  a certain linear programming relaxation  gives the best approximation one
can expect, assuming the unique games conjecture.

Continuing in the same  theme, a similar computational hardness result is shown  for the
maximum  acyclic subgraph problem.  Here,  a trivial
algorithm  obtains  a  half   approximation  and  obtaining  a  better
approximation algorithm has been an  open problem for quite some time.
Assuming the UG conjecture, this work shows that it is computationally hard to approximate
the maximum acyclic subgraph problem  by a better factor is hard.  This result also,
unconditionally, rules out a simple semi-definite programming approach to obtain a better

Reading List

 1. Complexity Theory: A Modern Approach
    by Sanjeev Arora and Boaz Barak
    Chapters 1-8, 16-19.

 2. Approximation Algorithms
    by Vijay Vazirani
    Chapters 1-4, 12-21.

 3. Expander Flows, Geometric Embeddings, and Graph Partitionings
    by Sanjeev Arora, Satish Rao, and Umesh Vazirani
    ACM Symposium on Theory of Computing, 2004.

 4. A tight bound on approximating arbitrary metrics by tree metrics
    by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar
    ACM Symposium on Theory of Computing, 2003

 5. Some Optimal Inapproximability Results
    by Johan Hastad
    STOC 1997.

 6. Proving integrality gaps without knowing the linear program.
    by Sanjeev Arora, Bela Bollobas and Laszlo Lovasz.
    Proc. IEEE Foundations of Computer Science, 2002.

 7. Local Global Tradeoffs in Metric Embeddings,
    by Moses Charikar, Konstantin Makarychev, Yury Makarychev,
    FOCS 2007, pp. 713-723.

 8. On the power of unique 2-prover 1-round games
    by Subhash Khot
    STOC '02.

 9. Optimal inapproximability results for max-cut and other 2-variable csps?
    by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell.
    FOCS '04.

10. The unique games conjecture, integrality gap for cut problems and
    embeddability of negative type metrics into $L_1$.
    by Subhash Khot and Nisheeth Vishnoi.
    FOCS '05.

11. Noise stability of functions with low influences: Invariance and optimality.
    by Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz.
    FOCS '05.

12. Vertex cover might be hard to approximate to within 2-$\epsilon$.
    by Subhash Khot and Oded Regev.
    J. Comput. Syst. Sci.

13. Near-Optimal Algorithms for Unique Games,
    by Moses Charikar, Konstantin Makarychev, Yury Makarychev,
    STOC 2006, pp. 205-214.

14. Approximation algorithms for the metric labeling problem via a new linear
    programming formulation.
    Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin.
    SIAM J. Disc. Math.

15. On the advantage over random for maximum acyclic subgraph.
    Moses Charikar, Konstantin Makarychev, and Yury Makarychev.
    FOCS 2007, pp. 625-633.

More information about the talks mailing list