Binary search trees are a fundamental data structure and their height
plays a key role in the analysis of divide-and-conquer algorithms like
quicksort. Their worst-case height is linear; their average height,
whose exact value is one of the best-studied problems in average-case
complexity, is logarithmic. We analyze their smoothed height ... more >>>

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.
Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and
with better rates if the affine dimensions of most of the sets $K_i$ are small.\\
Our approach is ... more >>>