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.
I am interested in theoretical computer science, specifically approximation algorithms and hardness of approximation. My advisor is . Recently, I've been working on limits on approximation achieved by mathematical relaxations and their relation to computational hardness.
Sanjeev Arora Abishek Kumarasubramanian C. Pandu Rangan Ravichadra Chakinala Guevara Noubir Ravi Sundaram Rajmohan Rajaraman Kofi Laing Joseph (Seffi) Naor Prasad Raghavendra Roy Schwartz Venkatesan Guruswami Moses Charikar Konstantin Makarychev Maxim Sviridenko Johan Håstad Amit Kumar Madhur Tulsiani Nisheeth ishnoi
Steganographic Communication in Ordered Channels , , , , and 2006 In this paper we focus on estimating the amount of information that can be embedded in the sequencing of packets in ordered channels. in Proceedings of Information Hiding, IH2006, LNCS, 2006 Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networks , , , , and 2006 In this paper, we consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements. in Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, July 2006 SDP Gaps and UGC Hardness for Multiway Cut, $ 0 $-Extension and Metric Labelling , , and 2008 In this paper, we show a direct way to convert linear programming integrality gaps for the Multiwaycut, $0$-extension, and Metric Labeling problems into UGC-based hardness results. in STOC 2008 papers/mlpaper.pdf papers/mlpaper.ps Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph and 2008 We prove that approximating the Maximum Acyclic Subgraph problem within a factor better than $1/2$ is Unique-Games hard. Our results also give a super-constant factor inapproximability result for the Feedback Arc Set problem. Using our reductions, we also obtain SDP integrality gaps for both the problems. in FOCS 2008 (invited to SICOMP special issue for FOCS 2008) papers/mas.pdf papers/mas.ps Every Permutation CSP of arity 3 is Approximation Resistant and 2009 Extending the results of the paper on the inapproximability of Max Acyclic Subgraph, we prove that every permutation CSP of arity 3 is approximation resistant. in CCC 2009 papers/perm-3csp.pdf papers/perm-3csp.ps Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover LP-based Approximation Algorithm and 2010 We show that for every positive epsilon, unless NP has randomized polynomial time algorithms, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-\varepsilon} n}$ by a reduction from the maximum label cover problem. Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms. submitted papers/maxqap.pdf papers/maxqap.ps Every k-ary Permutation CSP is Approximation Resistant , and 2010 We prove that every permutation CSP of constant arity, k, is approximation resistant. manuscript under preparation On the Optimality of a Class of LP-based Algorithms , , 2010 In this paper, we explain why the simple LP-based rounding algorithm for the Vertex Cover problem is optimal assuming the UGC. Complementing Raghavendra's result, our result generalizes to a class of strict, covering/packing type CSPs. We first write down a natural LP relaxation for this class of problems and present a simple rounding algorithm for it. The key ingredient, then, is a dictatorship test, which is parametrized by a rounding-gap example for this LP, whose completeness and soundness are the LP-value and the rounded value respectively. submitted papers/scsp.pdf papers/scsp.ps

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.

 Coming soon
Vinodh Muralidaran Murtaza Deepak Shyamnath Vishal Anirudh Anirudh Prasad David Arunachalam Srikanth Narayanan Vijay Arun Sid Moritz Aditya Aravindan Arthi Seshadhri Eden Bernhard Indraneel Sid Madhur Ashwin Sudheendra Ravishankar Vishal
Address:
Department of Computer Science
Princeton University
35 Olden Street
Princeton, NJ 08540-5233

Email: firstname at cs dot princeton dot edu