Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with statistical distance :
TR21-085 | 21st June 2021
Ilya Volkovich

The Final Nail in the Coffin of Statistically-Secure Obfuscator.

We present an elementary, self-contained proof of the result of Goldwasser and Rothblum [GR07] that the existence of a (perfect) statistically secure obfuscator implies a collapse of the polynomial hierarchy. In fact, we show that an existence of a weaker object implies a somewhat stronger statement. In addition, we extend ... more >>>

TR23-079 | 31st May 2023
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ... 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