Rajsekar ManokaranI am a post-doctoral researcher in the Theoretical Computer Science Group here at KTH. My adviser is
Research InterestsMy 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.
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problemswith
Testing Permanent Oracles -- Revisitedwith
Approximability and Mathematical Relaxations
Almost optimal inapproximability is shown for a wide set of problems including Metric Labeling, Max. Acyclic Subgraph, various packing and covering problems. The key new idea in this thesis is in coverting hard instances of relaxations (a.k.a integrality gap instances) into a proof of inapproximability (assuming the UGC). In most cases, the hard instances were discovered prior to this work; our results imply that these hard instances are possibly strong bottlenecks in designing approximation algorithms of better quality for these problems.
For ordering problems such as Max. Acyclic Subgraph, and Feedback Arc Set, such hard instances were previously unknown. For these problems, we construct such hard instance by using the reduction designed to prove the inapproximability. The hard instances show that all ordering problems are hard to approximate to a factor larger than the expected fraction satisfied by a random ordering: i.e., all ordering CSPs are approximation resistant.
Techniques involve using mathematical relaxations to obtain local distributions, converting them into low degree functions defined over the boolean cube and using the invariance principle to analyse such function.
Inapproximabilty of Densest k-Subgraph from Average Case Hardnesswith
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover & LP-based Approximation Algorithmwith
Every k-ary Permutation CSP is Approximation Resistantwith
On the Optimality of a Class of LP-based Algorithmswith
Every Permutation CSP of arity 3 is Approximation Resistantwith
SDP Gaps and UGC Hardness for Multiway Cut, $0$-Extension and Metric Labellingwith
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraphwith
Steganographic Communication in Ordered Channelswith
Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networkswith
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.
Address: Nada, KTH, SE-100 44 Stockholm, Sweden
Email: firstname at csc dot kth dot se