Publications

Spherical Cubes and Rounding in High Dimensions

with Guy Kindler, Ryan O'Donnell and Avi Wigderson.

[FOCS 2008]

What is the least surface area of a shape that tiles R^d under translations by Z^d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(sqrt(d)). Our main result is a construction with surface area O(sqrt(d)), matching the lower bound up to a constant factor of 2 sqrt(2 pi/e). The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles R^d by translations of any full rank discrete lattice Lambda with surface area 2pi fnorm(V^{-1}), where V is the matrix of basis vectors of Lambda, and fnorm denotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in R^d to rectangular lattice points.

A 2-Source Almost Extractor for Linear Entropy

[Random 2008]

We give an explicit construction of a function that is almost a 2-source extractor for linear entropy, it is a condenser where the output has almost full entropy. Given 2 sources with entropy delta n, the output of the condenser is a distribution on m-bit strings that is epsilon-close to having min-entropy m - poly(log(1/epsilon), 1/delta), where here m is linear in n.

Network Extractor Protocols
with Yael Tauman Kalai, Xin Li and David Zuckerman.

[FOCS 2008]

We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy. We give several such network extractor protocols in both the information theoretic and computational settings.

For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings. These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults, even when the min-entropy is only $2^{(\log n)^{\Omega(1)}}$. For larger min-entropy, in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case. Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99\% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least $\polylog (n)$ and where the parties only have access to an independent source with min-entropy~$n^{\Omega(1)}$.

Extractors for Three Uneven-Length Sources

with David Zuckerman.

[Random 2008]

We construct an efficient 3-source extractor that requires one of the sources to be significantly shorter than the min-entropy of the other two sources. Our extractors work even when the longer, n-bit sources have polynomially small min-entropy and the shorter source has polylogarithmic min-entropy. Previous constructions for independent sources with polynomial min-entropy required a constant number of sources, where the constant depended on the entropy. Our construction relies on lossless condensers based on Parvaresh-Vardy codes, as well as on a 2-source extractor for a block source and general sources from earlier work.

Parallel Repetition in Projection Games and a Concentration Bound

[STOC 2008]
We give a new bound for the parallel repetition of "projection games", the type of game most commonly used in hardness of approximation results. We also prove a concentration bound: the probability that players win more than the expected fraction of games in the repetition is exponentially small.

Extractors for Low-Weight Affine Sources

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are thus a generalization of the well studied models of bit-fixing sources (which are just weight 1 affine sources). For universal constants c,e , our extractors can extract almost all the entropy from weight k affine sources of dimension k, as long as k > log^c n, with error 2^{-k^Omega(1)} . This gives new extractors for low entropy bit-xing sources with exponentially small error, a parameter that is important for the application of these extractors to cryptography. Our techniques involve constructing new condensers for affine somewhere random sources.

Randomness Extractors for Independent Sources and Applications

My Ph.D. thesis, combining several of my previous papers.

An Exposition of Bourgain's Extractor

[Manuscript]

A construction of Bourgain gave the first 2-source extractor to break the min-entropy rate 1/2 barrier. In this note, we write an exposition of his result, giving a high level way to view his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma that seems interesting in its own right, and an argument (due to Boaz Barak) that shows that any two source extractor with sufficiently small error must be strong.

2-Source Dispersers for n^o(1) Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction

with Boaz Barak, Ronen Shaltiel and Avi Wigderson.

[STOC 2006]

The main result of this paper is an explicit disperser for two independent sources on n bits, each of entropy k=n^{o(1)}. Put differently, setting N=2^n and K=2^k, we construct explicit N by N Boolean matrices for which no K by K submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of K-Ramsey bipartite graphs of size N. This greatly improves the previous the previous bound of k=o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson. It also significantly improves the 25-year record of k= O(\sqrt{n}) on the very special case of Ramsey graphs, due to Frankl and Wilson. The construction uses (besides "classical" extractor ideas) almost all of the machinery developed in the last couple of years for extraction from independent sources.

Deterministic Extractors for Small Space Sources

with Jesse Kamp, Salil Vadhan and David Zuckerman.

[STOC 2006]

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on {0,1\}^n as sources generated by width 2^s branching programs: For every constant \delta > 0, we can extract .99\delta n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy \delta n, where s=\Omega(n). In addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant \eta > 0 such that for any \minrate > n^{-\eta}, we can extract m=(\delta-\minrate)n bits that are exponentially close to uniform from space s sources with min-entropy \delta n, where s=\Omega(\beta^3 n). Previously, nothing was known for \delta \leq 1/2, even for space 0.

Our results are obtained by a reduction to a new class of sources that we call "independent-symbol" sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. We give deterministic extractors for such sources when k is as small as \polylog(n), for small enough~d.

Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources

[STOC 2006]

This paper is about extracting randomness from independent sources.

Many applications in computer science require a source of true high quality random bits, yet such a source may not be available. In this work we show how to deterministically extract high quality randomness from several independent sources of low quality randomness.

It turns out that this task is equivalent to giving an explicit deterministic way to color the set [N]^c with M colors so that the coloring "looks random" in the following sense: for any large enough rectangle in the set, the number of points in the rectangle colored a particular color is about what you would expect for a random coloring. The goal is to maximize M, minimize c and minimize the size of the rectangles (a.k.a. the entropy of the sources) for which the extractor succeeds.

In this paper, we construct an extractor that can extract from a constant (c) number of independent sources of length n (N = 2^n), each of which have min-entropy that is polynomially small in n (say n^delta for some arbitrarily small constant delta). Previously the best known extractors for a constant number of independent sources required the sources to have min-entropy at least linear in n. Our extractor is built by composing previous constructions of strong seeded extractors in simple ways. We introduce a new technique to condense somewhere random sources that seems like a useful way to manipulate independent sources. Unlike other recent work for this problem, our main result does not rely on any results from additive number theory.

Using Bourgain's extractor (which does use results from additive number theory) as a black box, we show how to obtain a new extractor for 2 independent blockwise sources with few blocks, even when the min-entropy is as small as polylog(n). We also show how to modify the 2 source disperser for linear min-entropy of Barak et al. and Raz's 3 source extractor to get dispersers/extractors with exponentially small error and linear output length where previously both were constant.

A Technique for Dynamic Updating of Java Software

with Alessandro Orso and Mary Jean Harrold.

International Conference on Software Maintanence 2002, pp. 649--658.

In this paper we show how almost any object oriented program can be transformed into another program that has the same functionality as the original program, but has the additional feature that its code can be updated at runtime. In particular, we allow updates where classes in the object oriented programs can be replaced with classes whose code is different. The interesting thing is that this transformation does not require any support from the runtime system. We also introduce a new tool that we wrote which can rewrite (almost) any Java program so that it can support dynamic update.