Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rajsekar Manokaran:

TR12-094 | 19th July 2012
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Testing Permanent Oracles -- Revisited

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 >>>

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint