Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with randomized approximation algorithms:
TR04-013 | 10th February 2004
Oded Goldreich, Dana Ron

On Estimating the Average Degree of a Graph.

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using ``neighbor queries'' as well as ``degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... 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