Dr. Rajsekar Manokaran

Selected Publications

Improved NP-Inapproximability for 2-Variable Linear Equations

with Sanxia Huang, Johan Håstad, Ryan O'Donnell, John Wright,
in APPROX 2015.
(abstract) (pdf)

We prove NP-hardness of approximating the Unique-Games problem, and the special cases: Max-Cut, Max-2-LIN. Our result is the present best inapproximability for all these problems, in the regime of interest. The proof involves an improved gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, no such reduction can establish an inapproximability surpassing a factor $C > 2.54$. Previously, no such limitations on gadget reductions was known.

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

with Per Austrin, Cenny Wenner,
in Theory of Computing, 2015.
(abstract) (pdf)

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NP-hard approximation factors of $14/15+\epsilon$ and $1/2+\epsilon$. An OCSP is said to be approximation resistant if it is hard to approximate it 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 the assumption $P \ne NP$.

Towards a Characterization of Constant-Factor Approximable Min CSPs

with Victor Dalmau, Andrei Krokhin,
in SODA 2015.
(abstract) (pdf)

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language on an arbitrary finite domain. Using an algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation for such problems.

Testing Permanent Oracles - Revisited

with Sanjeev Arora, Arnab Bhattacharyya, Sushant Sachdeva,
in RANDOM 2012.
(abstract) (pdf)

On the Optimality of a Class of LP-based Algorithms

with Amit Kumar, Madhur Tulsiani, Nisheeth Vishnoi,
in SODA 2011.
(abstract) (pdf)

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.

Every k-ary Permutation CSP is Approximation Resistant

with Venkatesan Guruswami, Johan Håstad, Prasad Raghavendra, Moses Charikar,
in SICOMP special issue for FOCS 2008.
(abstract) (pdf)

We prove that every permutation CSP of constant arity, k, is approximation resistant.

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

with Konstantin Makarychev, Maxim Sviridenko,
in ICALP 2010.
(abstract) (pdf)

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.

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

with Venkatesan Guruswami, Prasad Raghavendra,
in FOCS 2008 (invited to SICOMP special issue for FOCS 2008).
(abstract) (pdf)

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.

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

with Joseph (Seffi) Naor, Prasad Raghavendra, Roy Schwartz,
in STOC 2008.
(abstract) (pdf)

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.

Steganographic Communication in Ordered Channels

with Ravichadra Chakinala, Abishek Kumarasubramanian, Guevara Noubir, C. Pandu Rangan, Ravi Sundaram,
in Proceedings of Information Hiding, IH2006, LNCS, 2006.

In this paper we focus on estimating the amount of information that can be embedded in the sequencing of packets in ordered channels.

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

with Ravichadra Chakinala, Abishek Kumarasubramanian, Kofi Laing, C. Pandu Rangan, Rajmohan Rajaraman,
in SPAA 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.