# The Probabilistic Method

@inproceedings{Alon1992ThePM, title={The Probabilistic Method}, author={Noga Alon and Joel H. Spencer}, booktitle={SODA}, year={1992} }

The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called the probabilistic Method as developed primarily by Paul Erdoős over the past half century. Here I will explore a particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets. A central point will be the evolution of these problems… Expand

#### Supplemental Presentations

#### Figures and Topics from this paper

#### 6,091 Citations

The Probablistic Method

- SODA '92
- 2000

The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called… Expand

Additive Combinatorics: The probabilistic method

- Mathematics
- 2006

In additive number theory, one frequently faces the problem of showing that a set A contains a subset B with a certain property P . A very powerful tool for such a problem is Erdős’ probabilistic… Expand

The Probabilistic Method

- Computer Science
- 1998

A few of the basic tools of the probabilistic method are introduced and some of the areas in which the method has had impact are described. Expand

Logarithmic reduction of the level of randomness in some probabilistic geometric constructions

- Mathematics
- 2006

Many of the surprising phenomena occurring in high dimensions are proved by use of probabilistic arguments, which show the existence of organized and regular structures but do not hint as to where… Expand

Encoding Arguments

- Computer Science, Mathematics
- ACM Comput. Surv.
- 2017

“Encoding arguments” provide an alternative presentation in which probabilistic reasoning is encapsulated in a “uniform encoding lemma” that provides an upper bound on the probability of an event using the fact that a uniformly random choice from a set of size n cannot be encoded with fewer than log 2n bits on average. Expand

Randomness and Pseudo-Randomness in Discrete Mathematics

- Computer Science
- 2002

The application of probabilistic techniques for proving deterministic theorems, and the application of deterministicTheorems for derandomizing Probabilistic existence proofs form an interesting combination of mathematical ideas from various areas, whose intensive study in recent years led to the development of fascinating techniques. Expand

Erdös Magic

- Mathematics, Computer Science
- FSTTCS
- 2005

This work gives a simple proof of the author of the Probabilistic Method that analyzes the random greedy algorithm and takes a Computer Science vantagepoint, creating a probabilistic algorithm to create the object and showing that with positive probability the created object has the desired properties. Expand

Pseudorandomness and Combinatorial Constructions

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 2006

Connections between the conditional �derandomization� results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and �randomness extractors� are described. Expand

The Complexity of Explicit Constructions

- Computer Science, Mathematics
- Theory of Computing Systems
- 2011

This paper poses several questions geared towards initiating a structural approach to the relationship between extremal combinatorics and computational complexity, to understand better why circuit lower bounds are hard. Expand

A PROBABILISTIC TECHNIQUE FOR FINDING ALMOST-PERIODS IN ADDITIVE COMBINATORICS

- 2010

We introduce a new probabilistic technique for finding ‘almost-periods’ of convolutions of subsets of finite groups. This allows us to give probabilistic proofs of two classical results in additive… Expand

#### References

SHOWING 1-10 OF 130 REFERENCES

A Parallel Algorithmic Version of the Local Lemma

- Mathematics, Computer Science
- Random Struct. Algorithms
- 1991

Here the Lovasz Local Lemma is modified and an algorithmic version that can be parallelized is achieved, thus obtaining deterministic NCl algorithms for several interesting algorithmic problems. Expand

An effective additive basis for the integers

- Computer Science, Mathematics
- SODA '94
- 1994

Abstract We give an algorithm for the enumeration of a set E of nonnegative integers with the property that each nonnegative integer x can be written as a sum of two elements of E in at least C 1 log… Expand

The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions

- Mathematics
- 1940

The present paper concerns itself with the applications of statistical methods to some number-theoretic problems. Recent inrestigations of Erdiis and Wintrier ? have shown the importance of the… Expand

Dispersers, deterministic amplification, and weak random sources

- Computer Science, Mathematics
- 30th Annual Symposium on Foundations of Computer Science
- 1989

The use of highly expanding bipartite multigraphs (called dispersers) to reduce greatly the error of probabilistic algorithms at the cost of few additional random bits is treated. Explicit… Expand

Deterministic simulation in LOGSPACE

- Computer Science, Mathematics
- STOC
- 1987

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 /… Expand

Small-bias probability spaces: efficient constructions and applications

- Mathematics, Computer Science
- STOC '90
- 1990

We show how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with "almost" equal probability. They are… Expand

An Algorithmic Approach to the Lovász Local Lemma. I

- Mathematics, Computer Science
- Random Struct. Algorithms
- 1991

This article converts some of the applications of the Lovasz Local Lemma into polynomial time sequential algorithms (at the cost of a weaker constant factor in the “exponent”). Expand

Probabilistic Communication Complexity

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1986

The logarithmic lower bound on communication complexity is applied to obtain an Ω(n log n) bound on the time of 1-tape unbounded error probabilistic Turing machines, believed to be the first nontrivial lower bound obtained for such machines. Expand

Geometrical realization of set systems and probabilistic communication complexity

- Mathematics, Computer Science
- 26th Annual Symposium on Foundations of Computer Science (sfcs 1985)
- 1985

It is shown that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. Expand

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

- Computer Science, Mathematics
- STOC
- 1987

It is proved that depth k circuits with gates NOT, OR and MODp where p is a prime require Exp(&Ogr;(n1/2k)) gates to calculate MODr functions for any r ≠ pm. Expand