Rajsekar Manokaran

I am a graduating PhD candidate working with the theory group at Princeton University. My advisor is Sanjeev Arora.

Here is a link to my CV

Research Interests

My area of research is theoretical computer science, particularly understanding the complexity of approximating various combinatorial optimization problems and connections between the approximability of such problems. A common thread in much of my work has been the study of convex relaxations for designing approximation algorithms. This yields results of the following flavour: for a fairly general class of problems, a specific relaxation already yields optimal approximations, upto current algorithmic techniques.

Publications

Inapproximabilty of Densest k-Subgraph from Average Case Hardness

with Sanjeev Arora, Noga Alon, Dana Moshkovitz, and Omri Weinstein
submitted
(abstract)
(PDF) (Postscript)

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover & LP-based Approximation Algorithm

with Konstantin Makarychev and Maxim Sviridenko
in ICALP 2010
(abstract)
(PDF) (Postscript)

Every k-ary Permutation CSP is Approximation Resistant

with Johan Håstad, Venkatesan Guruswami, Prasad Raghavendra, and Moses Charikar,
in SICOMP special issue for FOCS 2008
(abstract)
(PDF) (Postscript)

On the Optimality of a Class of LP-based Algorithms

with Amit Kumar, Madhur Tulsiani, and Nisheeth Vishnoi
in SODA 2011
(abstract)
(PDF) (Postscript)

Every Permutation CSP of arity 3 is Approximation Resistant

with Moses Charikar, and Venkatesan Guruswami
in CCC 2009
(abstract)
(PDF) (Postscript)

SDP Gaps and UGC Hardness for Multiway Cut, $0$-Extension and Metric Labelling

with Joseph (Seffi) Naor, Prasad Raghavendra, and Roy Schwartz
in STOC 2008
(abstract)
(PDF) (Postscript)

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

with Venkatesan Guruswami, and Prasad Raghavendra
in FOCS 2008 (invited to SICOMP special issue for FOCS 2008)
(abstract)
(PDF) (Postscript)

Steganographic Communication in Ordered Channels

with Ravichadra Chakinala, Abishek Kumarasubramanian, Guevara Noubir, C. Pandu Rangan, and Ravi Sundaram
in Proceedings of Information Hiding, IH2006, LNCS, 2006
(abstract)

Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networks

with Ravichadra Chakinala, Abishek Kumarasubramanian, Kofi Laing, C. Pandu Rangan, and Rajmohan Rajaraman
in Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, July 2006
(abstract)

Musings

  • Open Source Web Design

    • A website containing zillions of cool, clean and creative web design templates. All of them are open source; so you are free to download, tweak and publish. I got quite a few ideas from the templates there. In fact, the color scheme is (loosely) based on the Coffee N Cream template there.

    By the way, mine's generated from an XHTML file along with an XSLT. The styles exist in a separate CSS file. This way, the web page document is clean and not cluttered with HTML tags. In fact, most modern browsers (Firefox, Safari, Opera) can directly read the files and merge them (Click here to check it out). IE (upto version 7 atleast) doesn't know how to handle such "complex" things and hence I had to generate the HTML too.

    Feel free to download the files (xhtml, xsl and css), modify and use it for your homepage. In fact, there are quite a few handly xml tags which might make your life easier. You can use the xsltproc tool to generate the HTML file.

  • AsciiMathML

    • This is a cool javascript written by Peter Jipsen. The script goes through the page, converting math expressions like 2^{\sqrt { log n }} into MathML encoded text that looks as cool as $2^{\sqrt { log n }}$. You will, however, need a MathML enabled web browser like firefox to render it for you. I made it into a greasemonkey script (really trivial transformations) so that mathy pages like ECCC which don't really know about this script still render the math. Here is a screenshot of how it renders this page. I will try to put it up online sometime; in the meantime, please feel free to mail me if you want to try it out.

Contact

Address:
Department of Computer Science
Princeton University
35 Olden Street
Princeton, NJ 08540-5233

Email: firstname at cs dot princeton dot edu