The Probabilistic Method

By Andreas Klappenecker. 2005

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Introduction to Online Convex Optimization (2016, methodology): “The probabilistic method is attributed to Paul Erdos, see the illuminating text of Alon and Spencer (10).”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, methodology): “We also reference our companion paper on parametric statistical inference under diﬀerential privacy constraints [11]; we make use of two theorems from that earlier paper, but in order to keep the current paper self-contained, we restate them in this section.”
Novel scaling limits for critical inhomogeneous random graphs (2009, unknown): “The simplest example of a random graph is the Erd˝os-R´enyi random graph, for which its critical nature is by now well established (see e.g., the monographs [2, 5, 10, 19, 29] and the references therein).”
Quantum random number generators (2016, methodology): “Using the probabilistic method (Alon and Spencer, 2016), (Radhakrishnan and Ta-Shma, 2000) showed there always exist extractors with an output that contains almost all of the available hidden entropy in an input raw sequence coming from any k-source.”
$F$-factors in hypergraphs via absorption (2011, unknown): “[1]) with probability 1 − o(1) as n → ∞, the family F satisfies the following properties: |F| ≤(η/2)n/4 (1)”
A structure theorem for Boolean functions with small total influences (2010, background): “Thus h2 is decreasing, and then it follows from the classical FKG inequality (see [AS00]) that E[f(x)|xS = (1, .”
An improved LP-based approximation for steiner tree (2010, methodology): “After submitting the preliminary version of this paper, we found a way to derandomize our algorithm via the method of limited independence (see, e.g., Alon and Spencer [2]).”
Small cancellation labellings of some infinite graphs and applications (2014, unknown): “[AS00]) that can be found in [AGHR02, Lemma 1].”