Analyzing linear mergers

Mergers are functions that transform k (possibly dependent) random sources (distributions) into a single random source, in a way that ensures that if one of the input sources has min‐entropy rate δ then the output has min‐entropy rate close to δ. Mergers have proven to be a very useful tool in explicit constructions of extractors and condensers, and are also interesting objects in their own right. In this work we give a refined analysis of the merger constructed by [Raz, STOC'05] (based on [Lu, Reingold, Vadhan, and Wigderson, STOC'03 pp. 602–611, 2003]). Our analysis uses min‐entropy instead of Shannon's entropy to derive tighter results than the ones obtained in [Raz STOC'05]. We show that for every constant r and k it is possible to construct a merger that takes as input k strings of length n bits each, and outputs a string of length n/r bits, such that if one of the input sources has min‐entropy b, the output will be close to having min‐entropy b/(r + 1). This merger uses a constant number of additional uniform bits. One advantage of our analysis is that b (the min‐entropy of the “good” source) can be as small as a constant (this constant depends on r and k), while in the analysis given in [Raz STOC'05], b is required to be linear in n. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Dispersing hash functions

We define a family of functions F from a domain U to a range R to be dispersing if for every set S ? U of a certain size and random h ∈ F, the expected value of ∣S∣ – ∣h[S]∣ is not much larger than the expectation if h had been chosen at random from the set of all functions from U to R. We give near‐optimal upper and lower bounds on the size of dispersing families and present several applications where using such a family can reduce the use of random bits compared to previous randomized algorithms. A close relationship between dispersing families and extractors is exhibited. This relationship provides good explicit constructions of dispersing hash functions for some parameters, but in general the explicit construction is left open. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Increasing the output length of zero‐error dispersers

Let $\cal{C}$ be a class of probability distributions over a finite set Ω. A function $D : \Omega \mapsto\{0,1\}^{m}$ is a disperser for $\cal{C}$ with entropy threshold $k$ and error $\epsilon$ if for any distribution X in $\cal{C}$ such that X gives positive probability to at least $2^{k}$ elements we have that the distribution $D(X)$ gives positive probability to at least $(1-\epsilon)2^{m}$ elements. A long line of research is devoted to giving explicit (that is polynomial time computable) dispersers (and related objects called “extractors”) for various classes of distributions while trying to maximize m as a function of k. For several interesting classes of distributions there are explicit constructions in the literature of zero‐error dispersers with “small” output length m. In this paper we develop a general technique to improve the output length of zero‐error dispersers. This strategy works for several classes of sources and is inspired by a transformation that improves the output length of extractors (which was given by Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity, (2006) 46–60.) building on earlier work by Gabizon, Raz and Shaltiel (SIAM J Comput 36 (2006) 1072–1094). Our techniques are different than those of Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006) 46–60) and in particular give non‐trivial results in the errorless case. Using our approach we construct improved zero‐error 2‐source dispersers. More precisely, we show that for any constant $\delta >0$ there is a constant $\eta >0$ such that for sufficiently large n there is a poly‐time computable function $D :\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}^{\eta n}$ such that for every two independent distributions $X_1,X_2$ over $\{0,1\}^{n}$ each with support size at least $2^{\delta n}$ , the output distribution $D(X_1,X_2)$ has full support. This improves the output length of previous constructions by Barak, Kindler, Shaltiel, Sudakov and Wigderson (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 1–10) and has applications in Ramsey theory and in improved constructions of certain data structures from the work of Fiat and Naor [SIAM J Comput 22 (1993)]. We also use our techniques to give explicit constructions of zero‐error dispersers for bit‐fixing sources and affine sources over polynomially large fields. These constructions improve the best known explicit constructions due to Rao (unpublished data) and Gabizon and Raz [Combinatorica 28 (2008)] and achieve $m=\Omega(k)$ for bit‐fixing sources and $m=k-o(k)$ for affine sources over polynomial size fields. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Deterministic random walks on finite graphs

The rotor‐router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor‐router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor‐router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015     

On Sparse Parity Check Matrices

We consider the extremal problem to determine the maximal number of columns of a 0-1 matrix with rows and at most ones in each column such that each columns are linearly independent modulo . For fixed integers and , we shall prove the probabilistic lower bound = ; for a power of , we prove the upper bound which matches the lower bound for infinitely many values of . We give some explicit constructions.