DIMACS Workshop on Pseudorandomness and Explicit Combinatorial Constructions


Noga Alon, Tel Aviv University

Title: Ramsey graphs

The problem of constructing explicitly Ramsey graphs, that is, graphs which contain neither large cliques nor large independent sets, received a considerable amount of attention. I will describe some recent and less recent constructions, mention several open problems and discuss some related information theoretic questions.

Juergen Bierbrauer, Michigan Technological University

Title: From algebraic-geometric codes to limited bias and dependence

The problem of constructing families of random variables on a small probability space such that any $t$ of the random variables are close to being statistically independent can be reduced to a conceptually simpler structure, $\epsilon -$ biased arrays. We show how this problem can be reduced to error-correcting codes. Algebraic-geometric codes yield an asymptotically optimal solution to one variant of the problem. In view of the crucial problem of efficiency we show that Hermitian codes are just as efficient as Reed-Solomon codes, and they yield asymptotically better results. The relationship with expanding graphs is also discussed.

Johan Hastad, Royal Institute of Technology, Sweden

Title: Security of all individual RSA bits

We show that given an RSA-encryption of a message m, unless RSA can be efficiently inverted, it is impossible to guess any individual bit of m with accuracy significanly above 1/2. The probability is taken over a random message m and the coinflips of the guessing algorithm.

Joint work with Mats Naslund.

Adam Klivans, MIT

Title: Boosting and Hard-Core Sets

We link two fundamental ideas from theoretical computer science: {\em hard-core set construction,} a type of hardness amplification from computational complexity, and {\em boosting}, a technique from computational learning theory.

Using this connection we give fruitful applications of complexity-theoretic techniques to learning theory and vice versa. We show that the hard-core set construction of Impagliazzo, which establishes the existence of distributions under which boolean functions are highly inapproximable, may be viewed as a boosting algorithm. Using alternate boosting methods we give an improved bound for hard-core set construction which matches known lower bounds from boosting and thus is optimal within this class of techniques. We then show how to apply techniques from Impagliazzo's construction to give a new version of Jackson's celebrated Harmonic Sieve algorithm for learning DNF formulae under the uniform distribution using membership queries. Our new version has a significant asymptotic improvement in running time. Critical to our arguments is a careful analysis of the distributions which are employed in both boosting and hard-core set constructions.

This is joint work with Rocco Servedio.

Chi-Jen Lu, Academia Sinica

Title: Pseudorandom Generators for Combinatorial Rectangles

Let [m] denote the set {1, ..., m}. A combinatorial rectangle of type (m,d) is a subset of [m]^d that is a cross product of d subsets of [m]. A pseudorandom generator for such rectangles is a deterministic function maping short strings to elements in [m]^d such that these elements form a good sample space for approximating each rectangle's volume.

Pseudorandom generators for combinatorial rectangles have been actively studied for a while in theoretical computer science. They are closely related to fundamental problems such as derandomizing RL, DNF approximate counting, and approximating the distributions of independent multivalued random variables.

In this talk, a pseudorandom generator will be described which uses O(log m + log d + log^{3/2} 1/epsilon) bits to approximates the volume of any rectangles of type (m,d) to within epsilon error. Another pseudorandom generator will also be described for rectangles where each dimension is an interval. This talk will be based on a paper that appeared in ICALP'98.

Alex Lubotzky, Hebrew University and Yale University

Title: Groups and Expanders

In the last decade various constructions of expanders were presented, many of them are Cayley graphs of some finite groups with respect to carefully chosen sets of generators. We descuss the question whether indeed the expansion properties depend on the generators or merely on the groups. The question is still open. We present some partial results. We show that if the expansion is indepent of the generators, some remarkable results would follow, including proofs for some important conjecture on discrete subgroups of Lie groups.

Peter Bro Miltersen, University of Aarhus

Title: Derandomizing Arthur-Merlin games using hitting sets.

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some epsilon>0, some language in NE intersect coNE requires nondeterministic circuits of size 2^(epsilon n). This improves recent results of Arvind and Kobler and of Klivans and Van Melkebeek who proved the same conclusion, but under stronger hardness assumptions, namely, either the existence of a language in NE intersect coNE which cannot be approximated by nondeterministic circuits of size less than 2^(epsilon n) or the existence of a language in NE intersect coNE which requires oracle circuits of size 2^(epsilon n} with oracle gates for satisfiability. These previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's hitting set approach to derandomization.

Joint work with N.V. Vinodchandran, to appear on FOCS'99.

Moni Naor, Stanford University and Weizmann Institute

Title: Pseudo-Random Functions, Factoring and Assumptions

Factoring integers is the most established problem on which cryptographic primitive are based. This work presents an efficient construction of {\m pseudo-random functions} whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudo-random functions where each evaluation requires only a {\m constant} number of modular multiplications per output bit. This is substantially more efficient than any previous construction of pseudo-random functions based on factoring, and matches (up to a constant factor) the efficiency of the best known factoring-based {\m pseudo-random bit generators}.

We will also discuss a methodology for evaluating cryptographic assumptions.

Joint work with Omer Reingold and Alon Rosen

Igor Pak, Yale University

Title: Generating random group elements by product replacement algorithm

Product replacement algorithm is by far the most popular algorithm for generation of (nearly) uniform elements in finite groups. The algorithm is conjectured to be polynomial. We present various positive and negative results in favor of the conjecture.

Ran Raz, Weizmann Institute

Title: On Recycling the Randomness of the States in Space Bounded Computation

Let M be a logarithmic space Turing machine (or a polynomial width branching program) that uses up to k of approximately 2^{sqrt(log n)} (read once) random bits. For a fixed input, let P_i(S) be the probability (over the random string) that at time i the machine M is in state S, and assume that some weak estimation of the probabilities P_i(S) is known or given or can be easily computed. We construct a logarithmic space pseudo-random generator that uses only logarithmic number of truly random bits and outputs a sequence of k bits that looks random to M. This means that a very weak estimation of the state probabilities of M is sufficient for a full derandomization of M and for constructing pseudo-random sequences for M. We give several applications of the main theorem. To prove our theorem, we introduce the idea of recycling the state $S$ of the machine M at time i as part of the random string for the same machine at later time. That is, we use the entropy of the random variable S in order to save truly random bits later on.

Joint work with Omer Reingold.

Omer Reingold, AT&T Research

Title: Error Reduction for Extractors

We present a general method to reduce the error of any extractor. Our method works particularly well in the case that the original extractor extracts up to a constant fraction of the source min-entropy and achieves a polynomially small error. In that case, we are able to reduce the error to (almost) any epsilon, using only O(log(1/epsilon)) additional truly random bits (while keeping the other parameters of the original extractor more or less the same). In other cases (e.g. when the original extractor extracts all the min-entropy or achieves only a constant error) our method is not optimal but it is still quite efficient. Using our method, we are able to improve almost all known extractors in the case where the error required is relatively small (e.g. less than polynomially small error).

Joint work with Ran Raz and Salil Vadhan.

Ronen Shaltiel, Hebrew University

Title: Extractors and Pseudo-Random generators with optimal seed size

The Nisan Wigderson generator is one of the main tools used when trying to derandomize probabilistic algorithms. Recently, Trevisan showed how to use it to construct extractors. It turns out that the NW-generator has an inherent limitation which hurts it performance for some setups.

For example, Trevisan's extractors use $O(\log^2 n / k)$ extra random bits, when working on a source of length $n$ which contains $k$ random bits. This should be compared to the non-constructive bound which used only $O(\log n)$ extra random bits.

Our construction uses the NW-generator in a more sophisticated which bypass its limitation. Specifically, we get an extractor which uses only $O(\log n)$ extra random bits, and extracts $k^{1-a}$ bits (where $a$ is an arbitrarily small constant).

Joint work with Russell Impagliazzo and Avi Wigderson

Amin Shokrollahi, Bell Laboratories

Title: Codes on Algebraic Curves

Algebraic-geometric codes are without doubt one of the most powerful classes of linear codes known. They were introduced by V.~D.~Goppa in a series of papers during the period of 1977 to 1981. They became instanteneously famous in the coding community through a result proved in 1982 by Tsfasman, Vladut, and Zink who showed that algebraic-geometric codes contain explicit sequences of codes over large enough finite fields that lie above the Gilbert-Varshamov bound. In this talk I will give---using a minimal amount of theory---a soft introduction into the construction of these codes.

Aravind Srinivasan, Bell Labs

Title: Min-wise independent permutation families

Not much is known in general about explicit constructions of small pseudorandom permutation families. A very useful such notion of pseudorandomness for permutation families has been introduced by Broder, Charikar, Frieze and Mitzenmacher: "min-wise independence". We survey our joint work with Michael Saks, Shiyu Zhou and David Zuckerman on explicit constructions of approximate min-wise pseudorandom permutation families. This is based on a simple connection with low discrepancy sets for rectangles; we present some known results that show how improved constructions of such low discrepancy sets for some specific ranges of the parameters, would be interesting progress. We also sketch some applications of min-wise independence in derandomization.

Madhu Sudan, MIT

Title: List Decoding: Algorithms and Applications

The ``list decoding'' problem for an error-correcting code C is the task, given a target vector v and a bound t, of constructing a list (actually, a set) of codewords in C that agree with v in at least t coordinates. In this talk we will describe families of codes for which efficient list-decoding algorithms are known and describe some of the algorithms. We will also describe some applications of list-decoding and in particular, to the amplification of hardness of Boolean functions. (This latter task occupies a central role in the constructions of pseudorandom generators of Impagliazzo and Wigderson that derandomize BPP under complexity theoretic assumptions.)

The talk covers joint works with Venkatesan Guruswami (MIT), Luca Trevisan (Columbia) and Salil Vadhan (MIT).

Tibor Szabo, University of Illinois at Urbana-Champaign

Title: Norm-graphs: variations and applications

Norm-graphs were introduced in a paper by Koll\'ar, R\'onyai and the speaker. They are explicit constructions of dense $K_{t, t!+1}$-free graphs. In this talk we discuss recent developments about these creatures. We define a variant of them to obtain new sharp bounds for the Tur\'an number and multicolor Ramsey number of complete bipartite graphs. We also present a generalization of the original norm-graph construction which works in asymmetric cases of the Zarankiewicz problem. We apply this to settle a problem of Matou\v sek in Discrepancy Theory about his dual shatter function bound. The talk represents joint work with Noga Alon and Lajos R\'onyai.

Luca Trevisan, Columbia University

Title: Extractors and Pseudorandom Generators

We describe a new approach to construct extractors. Extractors are algorithms that transform a ``weakly random'' distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, such as the simulation of randomized algorithms using weak random sources; the explicit construction of expanders and superconcentrators; randomness-efficient reduction of error in sampling and in randomized algorithms; and simpler proofs of certain complexity-theoretic results.

We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator construction of a certain kind is an extractor.

A pseudo-random generator construction due to Impagliazzo and Wigderson, once reinterpreted via this connection, is an extractor that improves some known constructions and solves the open question of finding an extractor yielding an "entropy-rate optimal" simulation of randomized algorithms using weak random sources.

We also show that, using the simpler Nisan-Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained treatment.

Salil Vadhan, MIT

Title: Pseudorandom Generators without the XOR Lemma

Impagliazzo and Wigderson have recently shown that if there exists a decision problem solvable in time $2^{O(n)}$ and having circuit complexity 2^{Omega(n)} (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators.

The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.

Our first result is that when (a modified version of) the Nisan-Wigderson generator construction is applied with a "mildly" hard predicate, the result is a generator that produces a distribution indistinguishable from having large min-entropy. An extractor can then be used to produce a distribution computationally indistinguishable from uniform. This is the first construction of a pseudorandom generator that works with a mildly hard predicate without doing hardness amplification.

We then show that in the Impagliazzo-Wigderson construction only the first hardness-amplification phase (encoding with multivariate polynomial) is necessary, since it already gives the required average-case hardness. We prove this result by (i) establishing a connection between the hardness-amplification problem and a list-decoding problem for error-correcting codes; and (ii) presenting a list-decoding algorithm for error-correcting codes based on multivariate polynomials that improves and simplifies a previous one by Arora and Sudan.

Joint work with Madhu Sudan and Luca Trevisan.

DIMACS Homepage
Contacting the Center
Document last modified on May 18, 1999.