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 >>>

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 >>>

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained
by setting all *-entries to constants 0 or 1. A system of semi-linear
equations over GF(2) has the form Mx=f(x), where M is a completion of
A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ... more >>>

Call a function f: \mathbb{F}_2^n \to \{0,1\} odd-cycle-free if there are no x_1, \dots, x_k \in \mathbb{F}_2^n with k an odd integer such that f(x_1) = \cdots = f(x_k) = 1 and x_1 + \cdots + x_k = 0. We show that one can distinguish odd-cycle-free functions from those \epsilon-far ... more >>>

Let G=\langle S\rangle be a solvable permutation group given as input by generating set S. I.e.\ G is a solvable subgroup of the symmetric group S_n. We give a deterministic polynomial-time algorithm that computes an expanding generator set for G. More precisely, given a constant \lambda <1 we can compute ... more >>>