Concentration of measure for the analysis of randomized algorithms by Devdatt P. Dubhashi and Alessandro Panconesi Cambridge University Press, 2009

By Devdatt P. Dubhashi, Alessandro Panconesi. SIGA, 2009

1,115 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/f1904abd5da453f6d321c7366885b160b5efa04d

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Cryptocurrencies Without Proof of Work (2014, background): “ for the purpose of this analysis. Let Ybe the random variable that counts how many of the ‘locations of the next round will be controlled by the mstakeholders, hence E[Y] = p‘. Using tail inequality [8], it holds that Pr(Y > 1 2 ‘) = Pr(Y > 1 2p E[Y]) expf ( 1 2p 1)2p‘ 1 3 g: Thus, the amount”
Double Thompson Sampling for Dueling Bandits (2016, background): “[4] extends the classic Upper Confidence Bound (UCB) method [9] to dueling bandits and proposes a Relative Upper Confidence Bound (RUCB) algorithm that achieves O(K log T ) regret in K-armed dueling bandits.”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, background): “Part (1) of Theorem 3.1 is now immediate by linearity of expectation, since for i = 1 , 2 we have that Part (2) of Theorem 3.1 follows by a direct application of Chernoﬀ bounds (see e.g. [10]).”
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time (2018, methodology): “We will use the following Chernoﬀ inequality, which follows from the standard Chernoﬀ bound (see, e.g., [DP09]).”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, background): “Finally, from the practical side, we discuss a workload-balancing heuristic that provides signiﬁcant improvements in running-time by dynamically adjusting (cid:15) r .”
Coboundary expanders (2010, methodology): “Since each (k + 1)-cell is included in Y independently with probability p, by the Chernoff-Hoeffding bounds [7] (or see, for example, [10]),”
The Church of the Symmetric Subspace (2013, background): “However, it turns out that taking g ( x ) = x p and optimizing over p always yields a bound that is at least as powerful than when g ( x ) is of the form e yf ( x ) [14].”
Social learning and distributed hypothesis testing (2014, background): “From Azuma’s inequality [6], we have that for all positive δ,”
Sampling-based algorithms for optimal motion planning (2011, background): “Since {In,m,i}ni=1 are i.i.d. random variables, large deviations of their sum, Mn,m, can be bounded by the following Chernoff bound (Dubhashi and Panconesi 2009): P ( { Nn,m >( 1+ ) E[Nn,m] } ) ≤ ( e ( 1+ )(1+ ) )E[Nn,m] , for all > 0.”
Subcubic Equivalences between Path, Matrix and Triangle Problems (2010, result): “Analogous to the standard analysis of treaps (see [25], Problems 1.”
Kantorovich duality for general transport costs and applications (2014, methodology): “We refer to [62, 37, 2, 20, 51] for applications of this concentration inequality, under the so-called convex hull distance.”
Fast algorithms for maximizing submodular functions (2014, neutral): “1 [5]) Let X1, .”
Quantum circuits and low-degree polynomials over F2 (2016, background): “By a standard Chernoﬀ bound argument [15], in order for this estimate to be correct up to absolute error (cid:15) with probability 2 / 3, it is suﬃcient to take s = O (1 / 2 ).”