All reports by Author Rajsekar Manokaran:

__
TR12-094
| 19th July 2012
__

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva#### Testing Permanent Oracles -- Revisited

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR09-124
| 24th November 2009
__

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi#### On the Optimality of a Class of LP-based Algorithms

Revisions: 1

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

more >>>