Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Chernoff:
TR05-107 | 28th September 2005
Avi Wigderson, David Xiao

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

TR06-105 | 23rd August 2006
Avi Wigderson, David Xiao

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

ISSN 1433-8092 | Imprint