Chernoff-Hoeffding Inequality and Applications

A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations

Herman Chernoff · 1952

Earlier work this paper cites.

Probability inequalities for the sum of bounded random variables

Wassily Hoeffding · 1963

Earlier work this paper cites.

On the uniform convergence of relative frequencies of events to their probabilities

Vladimir Vapnik and Alexey Chervonenkis · 1971

Earlier work this paper cites.

Extensions of Lipschitz maps into a Hilbert space

William B. Johnson and Joram Lindenstrauss · 1984

Earlier work this paper cites.

The Johnson-Lindenstrauss lemma and the spericity of some graphs

P. Frankl and H. Maehara · 1987

Earlier work this paper cites.

On the method of bounded differences

Colin McDiarmid · 1989

Earlier work this paper cites.

Sharper bounds for Gaussian and emperical processes

M. Talagrand · 1994

Cited alongside, same era.

Approximate nearest neighbors: Towards removing the curse of dimensionality

Piotr Indyk and Rajeev Motwani · 1998

Cited alongside, same era.

Randomized Algorithms

Rajeev Motwani and Prabhakar Raghaven · 2000

Cited alongside, same era.

Improved bounds on the samples complexity of learning

Yi Li, Philip M. Long, and Aravind Srinivasan · 2001

Cited alongside, same era.

Database-friendly random projections: Johnson-Lindenstrauss with binary coints

Dimitris Achlioptas · 2003

Cited alongside, same era.

An elmentary proof of a theorem of johnson and lindenstrauss

Sanjoy Dasgupta and Anupam Gupta · 2003

Cited alongside, same era.

Emperical processes and random projections

B. Klartag and S. Mendelson · 2005

Later among the works it cites.

Probability and Computing: Randomized Algorithms and Probabilisitic Analysis

Michael Mitzenmacher and Eli Upfal · 2005

Later among the works it cites.

Nearest neighbor preserving embeddings

Piotr Indyk and Assaf Naor · 2007

Later among the works it cites.

On variants of the Johnson-Lindenstrauss lemma

Jirři Matoušek · 2008

Later among the works it cites.

Concentration of Measure for the Analysis of Randomized Algorithms

Devdatt P. Dubhashi and Alessandro Panconesi · 2009

Later among the works it cites.