Probabilistic methods for algorithmic discrete mathematics

By M. Habib. 1998

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

Local Rademacher complexities (2005, background): “Indeed, with only a trivial bound on the maximal variance, better results can be obtained via simpler concentration inequalities, such as the bounded difference inequality [23], which would allow √ rx/n to be replaced by √ x/n.”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, methodology): “The Laplace transform method, attributed to Bernstein, is a particularly elegant system for producing tail bounds for sums of scalar random variables; see [34, 36] for accessible discussions.”
Sparse coding for multitask and transfer learning (2012, background): “That is The concentration inequality in part (i) of the following theorem, known as the bounded difference inequality is given in (McDiarmid, 1998).”
Exponential inequalities for self-normalized martingales with applications (2007, background): “The celebrated Azuma–Hoeffding inequality [4, 16, 18] is as follows.”
On concentration of self-bounding functions (2009, background): “McDiarmid and Reed further generalize the notion of self-bounding functions.”
On normal domination of (super)martingales (2005, methodology): “fashion, various concentration inequalities for general functions g were obtained in (17; 18) and (1).”
Shannon sampling and function reconstruction from point values (2004, background): “The efficiency of a compression scheme is measured by the ratio |x|/|t| (as large as possible, representing the richness of the data) and the error (within a threshold).”
On the maximum queue length in the supermarket model (2006, methodology): “Now we use the independent bounded differences inequality; see, for instance, [12].”
Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles (2016, methodology): “If the colouring on Kn is a 1-factorization then a rainbow maximum degree 2 subgraph with n−O(log2 n) edges exists by a result of Hatami and Shor [12].”
Theory of classification : a survey of some recent advances (2005, background): “…[175], Devroye [71] Anthony and Biggs [10], Kearns and Vazirani [117], Vapnik [230] [231], Devroye, Györfi, and Lugosi [72], Ripley [185], Vidyasagar [235], Anthony and Bartlett [9], The bounded differences inequality was formulated explicitly first by McDiarmid [166] (see also the surveys [167]).”