Rajsekar Manokaran

I am a fourth year graduate student at the Princeton University. Before coming here, I was an undergraduate at the Indian Institute of Technology, Madras. Madras (née and now Chennai) is also the city I grew up in.

Research Interests

I am interested in theoretical computer science, specifically approximation algorithms, hardness of approximation and complexity theory. My advisor is Sanjeev Arora. Recently, I've been working on limits on approximation achieved by mathematical relaxations and their relation to computational hardness.

Publications

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

    • with Konstantin Makarychev and Maxim Sviridenko
    submitted
    {abstract}
    [PDF]

  • Every k-ary Permutation CSP is Approximation Resistant

    • with Moses Charikar, Johan Håstad and Venkatesan Guruswami
    manuscript under preparation
    {abstract}

  • On the Optimality of a Class of LP-based Algorithms

    • with Amit Kumar, Madhur Tulsiani, Nisheeth Vishnoi
    submitted
    {abstract}
    [PDF]

  • Every Permutation CSP of arity 3 is Approximation Resistant

    • with Moses Charikar and Venkatesan Guruswami
    in CCC 2009
    {abstract}
    [PDF]

  • 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.

  • Song Bird

    • Coming soon

Friends Swarm

Vinodh Muralidaran Murtaza Deepak Shyamnath Vishal Anirudh Anirudh Prasad David Arunachalam Srikanth Narayanan Vijay Arun Sid Moritz Aditya Aravindan Seshadhri Eden Bernhard Indraneel Sid Madhur Ashwin Sudheendra Ravishankar Vishal

Contact

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

Email: firstname at cs dot princeton dot edu