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

__
TR11-119
| 4th September 2011
__

Subhash Khot, Preyas Popat, Nisheeth Vishnoi#### $2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

__
TR09-125
| 24th November 2009
__

David Steurer, Nisheeth Vishnoi#### Connections Between Unique Games and Multicut

__
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

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

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

Subhash Khot, Preyas Popat, Nisheeth Vishnoi

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

David Steurer, Nisheeth Vishnoi

In this paper we demonstrate a close connection between UniqueGames and

MultiCut.

%

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

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