Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 124-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{chung_et_al:LIPIcs.STACS.2012.124, author = {Chung, Kai-Min and Lam, Henry and Liu, Zhenming and Mitzenmacher, Michael}, title = {{Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {124--135}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.124}, URN = {urn:nbn:de:0030-drops-34374}, doi = {10.4230/LIPIcs.STACS.2012.124}, annote = {Keywords: probabilistic analysis, tail bounds, Markov chains} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky. AMS Without 4-Wise Independence on Product Domains. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 119-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{braverman_et_al:LIPIcs.STACS.2010.2449, author = {Braverman, Vladimir and Chung, Kai-Min and Liu, Zhenming and Mitzenmacher, Michael and Ostrovsky, Rafail}, title = {{AMS Without 4-Wise Independence on Product Domains}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {119--130}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2449}, URN = {urn:nbn:de:0030-drops-24496}, doi = {10.4230/LIPIcs.STACS.2010.2449}, annote = {Keywords: Data Streams, Randomized Algorithms, Streaming Algorithms, Independence, Sketches} }