LEADER 04130nam 22007332 450 001 9910777912603321 005 20151005020622.0 010 $a1-107-20031-8 010 $a1-139-63769-X 010 $a1-282-30277-9 010 $a9786612302770 010 $a0-511-58063-0 010 $a0-511-58095-9 010 $a0-511-57955-1 010 $a0-511-57881-4 010 $a0-511-58127-0 010 $a0-511-58029-0 035 $a(CKB)1000000000784190 035 $a(EBL)451942 035 $a(OCoLC)609842926 035 $a(SSID)ssj0000128137 035 $a(PQKBManifestationID)11936945 035 $a(PQKBTitleCode)TC0000128137 035 $a(PQKBWorkID)10063487 035 $a(PQKB)11141035 035 $a(UkCbUP)CR9780511581274 035 $a(Au-PeEL)EBL451942 035 $a(CaPaEBR)ebr10333193 035 $a(OCoLC)438728734 035 $a(MiAaPQ)EBC451942 035 $a(PPN)150194013 035 $a(EXLCZ)991000000000784190 100 $a20090604d2009|||| uy| 0 101 0 $aeng 135 $aur||||||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aConcentration of measure for the analysis of randomized algorithms /$fDevdatt Dubhashi, Alessandro Panconesi$b[electronic resource] 210 1$aCambridge :$cCambridge University Press,$d2009. 215 $a1 online resource (xiv, 196 pages) $cdigital, PDF file(s) 300 $aTitle from publisher's bibliographic system (viewed on 05 Oct 2015). 311 $a1-107-60660-8 311 $a0-521-88427-6 320 $aIncludes bibliographical references (p. 189-193) and index. 327 $aChernoff-Hoeffding bounds -- Applications of the Chernoff-Hoeffding bounds -- Chernoff-Hoeffding bounds in dependent settings -- Interlude : probabilistic recurrences -- Martingales and the method of bounded differences -- The simple method of bounded differences in action -- The method of averaged bounded differences -- The method of bounded variances -- Interlude : the infamous upper tail -- Isoperimetric inequalities and concentration -- Talagrand's isoperimetric inequality -- Isoperimetric inequalities and concentration via transportation cost inequalities -- Quadratic transportation cost and Talagrand's inequality -- Log-Sobolev inequalities and concentration -- Appendix A : summary of the most useful bounds. 330 $aRandomized algorithms have become a central part of the algorithms curriculum, based on their increasingly widespread use in modern applications. This book presents a coherent and unified treatment of probabilistic techniques for obtaining high probability estimates on the performance of randomized algorithms. It covers the basic toolkit from the Chernoff-Hoeffding bounds to more sophisticated techniques like martingales and isoperimetric inequalities, as well as some recent developments like Talagrand's inequality, transportation cost inequalities and log-Sobolev inequalities. Along the way, variations on the basic theme are examined, such as Chernoff-Hoeffding bounds in dependent settings. The authors emphasise comparative study of the different methods, highlighting respective strengths and weaknesses in concrete example applications. The exposition is tailored to discrete settings sufficient for the analysis of algorithms, avoiding unnecessary measure-theoretic details, thus making the book accessible to computer scientists as well as probabilists and discrete mathematicians. 606 $aRandom variables 606 $aDistribution (Probability theory) 606 $aLimit theorems (Probability theory) 606 $aAlgorithms 615 0$aRandom variables. 615 0$aDistribution (Probability theory) 615 0$aLimit theorems (Probability theory) 615 0$aAlgorithms. 676 $a518/.1 700 $aDubhashi$b Devdatt$01535240 702 $aPanconesi$b Alessandro 801 0$bUkCbUP 801 1$bUkCbUP 906 $aBOOK 912 $a9910777912603321 996 $aConcentration of measure for the analysis of randomized algorithms$93783345 997 $aUNINA LEADER 02169nas--2200421-n-450 001 990008897900403321 005 20250917101307.0 011 $a0469-5461 035 $a000889790 035 $aFED01000889790 035 $a(Aleph)000889790FED01 035 $a000889790 091 $2CNR$aP 00095217 100 $a20090724b19511988km-y0itaa50------ba 101 0 $aita 110 $aauu-------- 200 1 $aAnnali della Facoltà di Lettere e Filosofia. Università di Napoli 207 1$a1951-1988 210 $aNapoli$c[s.n.] 326 $aAnnuale 530 0 $aAnnali della Facoltà di Lettere e Filosofia. Università di Napoli 675 $a1 675 $a82 675 $a378 712 02$aUniversità degli studi di Napoli.$bFacoltà di lettere e filosofia 801 0$aIT$bACNP$c20090723 859 4 $uhttp://acnp.cib.unibo.it/cgi-ser/start/it/cnr/dc-p1.tcl?catno=63658&person=false&language=ITALIANO&libr=&libr_th=unina1$zBiblioteche che possiedono il periodico 901 $aSE 912 $a990008897900403321 958 $aBiblioteca della Facoltà di Economia Complesso Universitario Monte S. Angelo- Università degli Studi di Napoli "Federico II"$b1951-1954;$fDECBC 958 $aNucleo Bibliotecario di Geografia.Facoltà di Lettere e Filosofia.Università degli Studi di Napoli Federico II$b1951-1980;1982;1985;1988.$eZ-02-02$fILFGE 959 $aDECBC 959 $aILFGE 996 $aAnnali della Facoltà di Lettere e Filosofia. Università di Napoli$9801154 997 $aUNINA AP1 8 $6866-01$aNA042 Biblioteca della Facoltà di Economia Complesso Universitario Monte S. Angelo- Università degli Studi di Napoli "Federico II"$evia Cinthia,26, 80126 Napoli (NA)$m081676647-0816782$m081676684$nit AP1 8 $6866-02$aNA239 Nucleo Bibliotecario di Geografia.Facoltà di Lettere e Filosofia.Università degli Studi di Napoli Federico II$bZ-02-02$evia Rodinò 22/Largo S. Marcellino 10, 80138 Napoli (NA)$m0812538238$nit AP2 40$aacnp.cib.unibo.it$nACNP Italian Union Catalogue of Serials$uhttp://acnp.cib.unibo.it/cgi-ser/start/it/cnr/df-p.tcl?catno=63658&language=ITALIANO&libr=&person=&B=1&libr_th=unina&proposto=NO