# Rajsekar Manokaran

I am a post-doctoral researcher in the Theoretical Computer Science Group here at KTH. My adviser is# 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

### On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

with(abstract)

(PDF)

### Testing Permanent Oracles -- Revisited

with(abstract)

(PDF)

### Approximability and Mathematical Relaxations

(abstract)

(PDF)

### Inapproximabilty of Densest k-Subgraph from Average Case Hardness

with(abstract)

(PDF) (Postscript)

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

with(abstract)

(PDF) (Postscript)

### Every k-ary Permutation CSP is Approximation Resistant

with(abstract)

(PDF) (Postscript)

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

with(abstract)

(PDF) (Postscript)

### Every Permutation CSP of arity 3 is Approximation Resistant

with(abstract)

(PDF) (Postscript)

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

with(abstract)

(PDF) (Postscript)

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

with(abstract)

(PDF) (Postscript)

### Steganographic Communication in Ordered Channels

with(abstract)

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

with(abstract)

# Musings

### Open Source Web Design

### AsciiMathML

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.

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: Nada, KTH, SE-100 44 Stockholm, Sweden
```

Email: firstname at csc dot kth dot se