Search

Your search keyword '"Mitzenmacher, Michael"' showing total 63 results
Start Over Author "Mitzenmacher, Michael" Publication Type Books
63 results on '"Mitzenmacher, Michael"'

1. Probability and computing : Randomization and Probabilistic techniques in algorithms and data analysis.

Author

Mitzenmacher, Michael and Upfal, Eli

Subjects
Algorithms, Probabilities, Stochastic analysis
Abstract

Summary: "Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics"-- Provided by publisher.

Published
2017

39. On Balls and Bins with Deletions

Author

Cole, Richard, primary, Frieze, Alan, additional, Maggs, Bruce M., additional, Mitzenmacher, Michael, additional, Richa, Andréa W., additional, Sitaraman, Ramesh, additional, and Upfal, Eli, additional

Published
1998
Full Text
View/download PDF

48. Tight Thresholds for Cuckoo Hashing via XORSAT.

Author

Dietzfelbinger, Martin, Goerdt, Andreas, Mitzenmacher, Michael, Montanari, Andrea, Pagh, Rasmus, and Rink, Michael

Abstract

We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k ≥ 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds ck such that, as n goes to infinity, if n/m ≤ c for some c < ck then a hash table can be constructed successfully with high probability, and if n/m ≥ c for some c > ck a hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k > 2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem. We then extend these results to the setting where keys can have differing number of choices, and make a conjecture (based on experimental observations) that extends our result to cuckoo hash tables storing multiple keys in a bucket. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

49. Streaming Graph Computations with a Helpful Advisor.

Author

Cormode, Graham, Mitzenmacher, Michael, and Thaler, Justin

Abstract

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only constant memory is needed for single-pass algorithms given linear-sized annotations. We also obtain a protocol achieving optimal tradeoffs between annotation length and memory usage for matrix-vector multiplication; this result contributes to a trend of recent research on numerical linear algebra in streaming models. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

50. An Analysis of Random-Walk Cuckoo Hashing.

Author

Frieze, Alan, Melsted, Páll, and Mitzenmacher, Michael

Abstract

In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has required a breadth-first search analysis, which is both inefficient in practice and currently has only a polynomial high probability upper bound on the insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found. [ABSTRACT FROM AUTHOR]

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results