Miklos Ajtai

We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of ...
more >>>

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for ... more >>>