Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nisheeth Vishnoi:

TR17-127 | 12th August 2017
Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.
More precisely,
the property that we need is that every face of the polytope lies in an affine space defined ... more >>>

TR11-119 | 4th September 2011
Subhash Khot, Preyas Popat, Nisheeth Vishnoi

$2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

TR09-125 | 24th November 2009
David Steurer, Nisheeth Vishnoi

Connections Between Unique Games and Multicut

In this paper we demonstrate a close connection between UniqueGames and
In MultiCut, one is given a ``network graph'' and a ``demand
graph'' on the same vertex set and the goal is to remove as few
edges from the network graph as ... 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