Kfir Barhum

Abstract of Master Thesis (Weizmann Inst., 2007)

Approximating Averages of Geometrical and Combinatorial Quantities


We look into the problem of estimating the average of quantities relating to combinatorial and geometrical objects. In all the cases we study it is possible to get the exact average of these quantities by using the trivial algorithm that calculates the average by obtaining all the quantities. Using the underlying structure of these problems, we are able to obtain faster algorithms that approximate the average. Specifically, we consider randomized algorithms that are given an approximation parameter epsilon, and return a (1+epsilon)-approximation of the average quantity. Our work focuses on the problem of calculating the average degree of a hypergraph, and the problem of calculating the average distance between every pair of points in a set of points in a d-dimensional Euclidean space.


Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, February 2007.

Available: the thesis (in PS format).



click for big

click for big

click for big
Kfir as Hermes delivers a message gets punished


Back to Oded Goldreich's homepage.