Concentration of measure for the analysis of randomized algorithms / (Record no. 522172)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 03155nam a22003858i 4500 |
| 001 - CONTROL NUMBER | |
| control field | CR9780511581274 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | UkCbUP |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20200124160325.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS--GENERAL INFORMATION | |
| fixed length control field | m|||||o||d|||||||| |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr|||||||||||| |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 090604s2009||||enk o ||1 0|eng|d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780511581274 (ebook) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9780521884273 (hardback) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9781107606609 (paperback) |
| 040 ## - CATALOGING SOURCE | |
| Original cataloging agency | UkCbUP |
| Language of cataloging | eng |
| Description conventions | rda |
| Transcribing agency | UkCbUP |
| 050 00 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | QA273 |
| Item number | .D765 2009 |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 518/.1 |
| Edition number | 22 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Dubhashi, Devdatt, |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Concentration of measure for the analysis of randomized algorithms / |
| Statement of responsibility, etc | Devdatt Dubhashi, Alessandro Panconesi. |
| 264 #1 - Production, Publication, Distribution, Manufacture, and Copyright Notice (R) | |
| Place of production, publication, distribution, manufacture (R) | Cambridge : |
| Name of producer, publisher, distributor, manufacturer (R) | Cambridge University Press, |
| Date of production, publication, distribution, manufacture, or copyright notice | 2009. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 online resource (xiv, 196 pages) : |
| Other physical details | digital, PDF file(s). |
| 336 ## - Content Type (R) | |
| Content type term (R) | text |
| Content type code (R) | txt |
| Source (NR) | rdacontent |
| 337 ## - Media Type (R) | |
| Media type term (R) | computer |
| Media type code (R) | c |
| Source (NR) | rdamedia |
| 338 ## - Carrier Type (R) | |
| Carrier type term (R) | online resource |
| Carrier type code (R) | cr |
| Source (NR) | rdacarrier |
| 500 ## - GENERAL NOTE | |
| General note | Title from publisher's bibliographic system (viewed on 05 Oct 2015). |
| 505 0# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Chernoff-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. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | Randomized 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. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Random variables. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Distribution (Probability theory) |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Limit theorems (Probability theory) |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Algorithms. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Panconesi, Alessandro, |
| Relator term | author. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Print version: |
| International Standard Book Number | 9780521884273 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://doi.org/10.1017/CBO9780511581274">https://doi.org/10.1017/CBO9780511581274</a> |
No items available.