Steganographic Communication in Ordered Channels

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 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 We show that for $k$-way multicut, $0$-extension and metric labeling problems, a simple linear programming relaxation (known as the earthmover relaxation) provides the best approximation (upto an arbitrarily small additive error) to the optimum of a given instance of the above mentioned problems, assuming the UGC. in STOC 2008 papers/mlpaper.pdf papers/mlpaper.ps Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph , and 2008 Maximum Acyclic Subgraph is the problem of identifying the largest subset of edges in a directed graph that do not contain a directed cycle. 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. in ICALP 2010 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. in SICOMP special issue for FOCS 2008 papers/ocsp.pdf papers/ocs.ps On the Optimality of a Class of LP-based Algorithms , , and 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. in SODA 2011 papers/scsp.pdf papers/scsp.ps Inapproximabilty of Densest k-Subgraph from Average Case Hardness , , , and 2011 We show that the Densest-k-Subgraph problem is hard to approximate to any constant, assuming either: random k-AND formulas are hard to distinguish from well-satisfiable ones; or random graphs (in the Erdos-Renyi G(n, 1/2) sense) are hard to distinguish from ones containing a large clique in it. Both the results involve a simple "direct product" style result on density of size k subgraphs when the graph looks sufficiently random. submitted papers/dks.pdf papers/dks.ps Testing Permanent Oracles -- Revisited , , and 2012 We show a testing procedure to verify an oracle that supposedly computes the permanent of most gaussian distributed matrices. Random 2012 papers/perm-gaussian.pdf Approximability and Mathematical Relaxations 2012 Thesis. Defended in Oct. 2012. The thesis ascertains the approximability of classic combinatorial optimization problems using mathematical relaxations. The general flavor of results in the thesis is: a problem $P$ is hard to approximate to a factor better than one obtained from the $R$ relaxation, unless the Unique Games Conjecture is false.
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. papers/thesis.pdf On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems , and 2013 We show improved NP-hardness of approximating {Ordering Constraint Satisfaction Problems}~(OCSPs). For the two most well-studied OCSPs, \textproblem{Maximum Acyclic Subgraph} and \textproblem{Maximum Betweenness}, we prove inapproximability of $14/15+\epsilon$ and $1/2+\epsilon$.%, respectively. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction $1 / (m/2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P \neq NP. Approx 2013 papers/ordNP.pdf

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.