Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Randomized reduction:
TR97-047 | 20th October 1997
Miklos Ajtai

The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

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

TR23-145 | 20th September 2023
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran

Total Variation Distance Estimation Is as Easy as Probabilistic Inference

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

ISSN 1433-8092 | Imprint