Probability and Computing: Randomized Algorithms and Probabilistic Analysis

By Michael M. Mitzenmacher, Eli Upfal. 2005

2,440 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Probabilistic & Bayesian Methods, Algorithms & Complexity, Signal Processing

How researchers see this paper

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

In Computational Theory and Mathematics

In Probabilistic & Bayesian Methods

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Privacy Amplification via Random Check-Ins (2020, positive): “One can view this line of reasoning to be analogous to privacy-preserving deep learning research, in that the theoretical guarantees for convex models acted as guiding principles for non-convex (deep learning) models [9, 1, 29].”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, neutral): “Lemma 17 Mitzenmacher and Upfal (2005) For X ∼ Poi(λ) or X ∼ B(n, λn) and any δ > 0, we have P(X ≥ (1 + δ)λ) ≤ ( eδ (1 + δ)1+δ )λ ≤ exp(−(δ 2 ∧ δ)λ 3 ), P(X ≤ (1− δ)λ) ≤ ( e−δ (1− δ)1−δ )λ ≤ exp(−δ 2λ 2 ).”
Deep Fried Convnets (2014, background): “This idea is related to random projections, which have been deeply studied in theoretical computer science [28].”
Heavy Hitters and the Structure of Local Privacy (2017, neutral): “Theorem 3.9 (e.g., [25]) .”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, neutral): “ that (Y 1,Y 2,··· ,YS)|( PS i=1Yi = n) ∼ Multinomial(n,P), hence Lemma A.1 yields the desired result. The following lemma gives some tail bounds for Poisson or Binomial random variables. Lemma A.2. (Mitzenmacher and Upfal, 2005, Exercise 4.7) If X ∼ Poi(λ) or X ∼ B(n, λ n), then for any δ > 0, w”
Multiwinner Voting with Fairness Constraints (2017, background): “ed; this is natural, e.g., when we simply want to ensure minority representations. Further, assume that P i∈[p] ℓi ≤k.Thus,wecanensure thecommittee includes atlest ℓi candidates belonging to Pi. 5see [27] for details. 3.3 Price of Fairness Enforcing fairness must naturally come at a cost – the feasi”
Chebyshev polynomials, moment matching, and optimal estimation of the unseen (2015, methodology): “Recall from the deﬁnition of D k ( (cid:15) ) that i p i ≤ 1 + (cid:15) and Therefore by (34), we have where in the last inequality we used the Chernoﬀ bound (see, e.g., [MU05, Theorem 5.4]).”
Aiding the Detection of Fake Accounts in Large Scale Social Online Services (2012, methodology): “Inspecting random users for trust seeds to cover most of communities in the non-Sybil region would require a prohibitive manual inspection workload, as indicated by the Coupon Collector’s Problem [39].”
Predicting the popularity of web 2.0 items based on user comments (2014, background): “partite, which could cause the random walk to become periodic and non-stationary [26].”
Information source detection in the SIR model: A sample path based approach (2012, methodology): “According to the Chernoff bound [19], we have”
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, neutral): “Therefore, Azuma’s inequality [45] then gives: We also have that p ( A t +1 k | A t ≥ k ) ≤ p ( A t +1 ≤ k | A t = k ).”