Nisheeth K. Vishnoi
$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing.
Tue, 09/13/2011 - 15:01 — SomNambulAuthors: Nisheeth K. Vishnoi, Subhash Khot, Preyas Popat
Subjects: Computational Complexity
AbstractWe prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not
\subseteq$DTIME$(2^{{\log^{O(1/\eps)} 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-\eps}n}.$ This improves upon the
previous hardness factor of $(\log n)^\delta$ for some $\delta > 0$ due to
\cite{AKKV05}.- 23 comments
- login or register to post comments
Algorithms and Hardness for Subspace Approximation.
Wed, 12/09/2009 - 16:01 — SomNambulAuthors: Amit Deshpande, Kasturi Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi
Subjects: Data Structures and Algorithms
AbstractThe subspace approximation problem Subspace($k$,$p$) asks for a
$k$-dimensional linear subspace that fits a given set of points optimally,
where the error for fitting is a generalization of the least squares fit and
uses the $\ell_{p}$ norm instead. Most of the previous work on subspace
approximation has focused on small or constant $k$ and $p$, using coresets and
sampling techniques from computational geometry.
User login
