Consider a weather forecaster predicting a probability of rain for
the next day. We consider tests that given a finite sequence of
forecast predictions and outcomes will either pass or fail the
forecaster. Sandroni (2003) shows that any test which passes a
forecaster who knows the distribution of nature, can ... more >>>

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in ... more >>>

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)
= O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>