Michael Mitzenmacher

Subhasish Mitra, Steven S. Lumetta, Michael Mitzenmacher, Nishant Patil

Preset dictionaries for Hu man codes are used e ectively in fax transmission and JPEG encoding. A natural extension is to allowmultiple preset dictionaries instead of just one. We show, ho wever,...

Intel (2009)

Larger, denser designs lead to more defects; higher quality requirements and new test methods lead to an explosion in test data volume. Test compression techniques attempt to do more testing with...

576 Abstract Improved Classification via Connectivity Information (2008)

Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher

The motivation for our work is the observation that Web pages on a particular topic are often linked to other pages on the same topic. We model and analyze the problem of how to improve the...

Abstract (2008)

Unscrambling Address Lines, Andrei Broder, Michael Mitzenmacher, Laurent Moll

A writer leaves a message in a write-once memory accessible via address lines. Before the intended recipient has a chance to get the message, the address lines are permuted by an adversary. We...

Towards a Theory of Networked Computation 1 (2008)

Joan Feigenbaum, Michael Mitzenmacher

The increasing prominence of the Internet, the Web, and large data networks in general has profoundly affected social and commercial activity. It has also wrought one of the most profound shifts in...

On the Hardness of Finding Optimal Multiple Preset Dictionaries (2008)

The Power of One Move: Hashing Schemes for Hardware (2008)

Abstract—We show that the following simple compression problem is NP-hard: given a collection of documents, find the pair of Huffman dictionaries that minimizes the total compressed size of the...

Adam Kirsch, Student Member, Michael Mitzenmacher

Abstract—In a standard multiple choice hashing scheme, each item is stored in one of d ≥ 2 hash table buckets. The availability of choice in where items are stored improves space utilization....

Capacity Upper Bounds for the Deletion Channel (2008)

Suhas Diggavi, Michael Mitzenmacher, Henry D. Pfister

Abstract — We present two upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. The first can be numerically...

Improved lower bounds for the capacity of i.i.d. deletion and duplication channels,” [Online]. Available: http://www.eecs.harvard.edu/∼michaelm/postscripts/toitsubmita.ps (2008)

Eleni Drinea, Michael Mitzenmacher

Abstract—This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability �. It improves significantly upon the best previous framework used to...

Harvard University (2008)

Network coding meets TCP (2008)

A standard load balancing model considers placing Ò balls into Ò bins by choosing � possible locations for each ball independently and uniformly at random and sequentially placing each in the...

Sundararajan, Jay Kumar, Shah, Devavrat, Medard, Muriel, Mitzenmacher, Michael, Barros, Joao

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random...

\Lambda (2008)

Frederic H. Behr, Victoria Fossum, Michael Mitzenmacher, David Xiao

x Abstract Previous work on estimating the entropy of written natural language has focused primarily on English. We expand this work by considering other natural languages, including Arabic, Chinese,...

Estimating and Comparing Entropy across Written Natural Languages Using PPM Compression (2008)

Frederic H. Behr, Victoria Fossum, Michael Mitzenmacher, David Xiao, Frederic H. Behr, Jr. \lambda Victoria, ...

Abstract Previous work on estimating the entropy of written natural language has focused primarily on English. We expand this work by considering other natural languages, including Arabic, Chinese,...

Fine-Grained Layered Multicast with STAIR (2008)

John W. Byers, Gu-in Kwon, Michael Luby, Michael Mitzenmacher

Abstract—Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...

General Terms (2008)

Neal Lesh, Michael Mitzenmacher, Sue Whitesides

We present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobichydrophilic model. We found these solutions with a generic implementation of tabu...

ABSTRACT FLID-DL: Congestion Control for Layered Multicast (2008)

John Byers, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...

TO APPEAR IN IEEE/ACM TRANSACTIONS ON NETWORKING 1 Informed Content Delivery Across Adaptive Overlay Networks (2008)

John W. Byers, Jeffrey Considine, Michael Mitzenmacher, Stanislav Rost

Abstract—Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive...

A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION (2008)

Human-Guided Search for Jobshop Scheduling (2008)

We describe lessons learned in developing a program for interactive optimization of large airlift scheduling problems. While for small problems one can create a visualization that both shows a...

Neal Lesh, Leonardo B. Lopes, Joe Marks, Michael Mitzenmacher, Guy T. Schafer

We present an interactive jobshop scheduling application developed with the Human-Guided Search (HuGS) framework and toolkit. Our system leverages people’s abilities in areas in which they...

Pattern-based compression of text images (2008)

Measuring index quality using random walks on the Web (2008)

We suggest a novel approach for compressing images of text documents based on building up a simple derived font from patterns in the image, and present the results of a prototype implementation based...

Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...

Designing Stimulating Programming Assignments for an Algorithms Course: A Collection of Exercises Based on Random Graphs (2008)

Abstract A Digital Fountain Approach to Reliable Distribution of Bulk Data (2008)

The field of random graphs contains many surprising and interesting results. Here we demonstrate how some of these results can be used to develop stimulating, open-ended exercises for courses in...

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

SUBMITTED TO IEEE/ACM TRANSACTIONS ON NETWORKING 1 Fine-Grained Layered Multicast with STAIR (2008)

John W. Byers, Gu-in Kwon, Michael Luby, Michael Mitzenmacher

Abstract—Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...

ABSTRACT Network Monitoring using Traffic Dispersion Graphs (TDGs) (2008)

Marios Iliofotou, Michael Mitzenmacher

Monitoring network traffic and detecting unwanted applications has become a challenging problem, since many applications obfuscate their traffic using unregistered port numbers or payload encryption....

Abstract (2008)

Yan-cheng Chang, Michael Mitzenmacher

We consider the following problem: a user U wants to store his files in an encrypted form on a remote file server S. Later the user U wants to efficiently retrieve some of the encrypted files

Books on Algorithms and Data Structures 1. The Traveling Salesman Problem: A Computational Study by Applegate, Bixby, Chvatal, and (2008)

William Gasarch, Michael Mitzenmacher, One Jonathan Katz, C William Gasarch

Borchers. Books I want Reviewed If you want a FREE copy of one of these books in exchange for a review, then email me at gasarchcs.umd.edu Reviews need to be in LaTeX, LaTeX2e, or Plaintext.

�Ò � ��ÖÙÔØ Ö�Ø � �Ò Ö��×� × Ä�� ÊÄ � �ÄÁ � �Ä � × � × �Ð��Ð� (2008)

Michael Mitzenmacher, Alex Roetter, William Shaver

�ÄÁ � �Ä ×�××�ÓÒ × �Ò � ×ÙÔÔÓÖØ × ��Ò�Ö�Ð Ö�Ø� × ÓÒ Ø� � ��«�Ö�ÒØ ÑÙÐØ � �×Ø Ð�Ý�Ö × Ï �...

Techniques and Results (2008)

Michael Mitzenmacher, Andrea W. Richa, Ramesh Sitaraman Z

To motivate this survey, we begin with a simple problem that demonstrates a

Abstract (2008)

Designing Stimulating Programming Assignments for an Algorithms Course: A Collection of Problems Based on Random Graphs (2008)

We suggest a novel approach for compressing images of text documents based on building up a simple derived font from patterns in the image, and present the results of a prototype implementation based...

An Economically-Principled Generative Model of AS Graph Connectivity ABSTRACT (2008)

The eld of random graphs contains many surprising and interesting results. Here we demonstrate how some of these results can be used to develop stimulating, open-ended problems for courses in...

Jacomo Corbo, Shaili Jain, Michael Mitzenmacher, David C. Parkes

We explore the problem of modeling Internet connectivity at the Autonomous System (AS) level and present an economically-principled dynamic model that reproduces key features of the AS graph...

Abstract Practical Loss-Resilient Codes (2008)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Volker Stemann

We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for...

Revisiting the COUNTER Algorithms for List Update (2008)

Revisiting the COUNTER Algorithms for List Update (2008)

COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook and Sleator [7]. They showed that for any>0, there exist COUNTER...

The hiring problem and Lake Wobegon strategies (2008)

COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...

Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii

We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...

The hiring problem and Lake Wobegon strategies (2008)

Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii

We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...

The hiring problem and Lake Wobegon strategies (2008)

Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal

We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...

Why simple hash functions work: Exploiting the entropy in a data stream (2008)

Michael Mitzenmacher, Salil Vadhan

Hashing is fundamental to many algorithms and data structures widely used in practice. For theoretical analysis of hashing, there have been two main approaches. First, one can assume that the hash...

Alan Frieze y (2007)

Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal

We consider the problem of extending the analysis of balls and bins processes to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions...

1 Fine-Grained Layered Multicast (2007)

In the bin packing problem, one is given a sequence (2007)

Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which enables coarse-grained congestion control and complies with...

1 Fine-Grained Layered Multicast (2007)

We prove that Best Fit bin packing has linear waste on the discrete distribution Ufj; kg (where items are drawn uniformly from the set f1=k; 2=3; \Delta \Delta \Delta; j=kg) for sufficiently large k...

Revisiting the COUNTER Algorithms for List Update (2007)

Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with TCP-friendliness...

Pattern-Based Compression of Text Images (2007)

COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator [7]. They showed that for any ffl ? 0, there exist COUNTER...

Designing Stimulating Programming Assignments for an Algorithms Course: A Collection of Problems Based on Random Graphs (2007)

We suggest a novel approach for compressing images of text documents based on building up a simple derived font from patterns in the image, and present the results of a prototype implementation based...

ABSTRACT A Complete and Effective Move Set for Simplified Protein Folding (2007)

The field of random graphs contains many surprising and interesting results. Here we demonstrate how some of these results can be used to develop stimulating, open-ended problems for courses in...

Michael Mitzenmacher, Sue Whitesides, Neal Lesh, Neal Lesh

We present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobic-hydrophilic model. We found these solutions with a generic implementation of tabu...

UNPUBLISHED MANUSCRIPT 1 Exact Sampling of TCP Window States (2007)

Ashish Goel, Michael Mitzenmacher

Abstract--- We demonstrate how to apply Coupling from the Past, a simulation technique for exact sampling, to Markov chains based on TCP variants. This approach provides a new, statistically sound...

S n is min-wise independent if for any set X (2007)

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher

We define and study the notion of min-wise independent families of permutations. We say that

A Brief History of Generative Models for Power Law and Lognormal Distributions (2007)

Power Law, Lognormal Distributions, Michael Mitzenmacher, Michael Mitzenmacher

Power law distributions are an increasingly common model for computer science applications; for example, they have been used to describe le size distributions and in- and out-degree distributions for...

Verification Codes: Simple Low-Density Parity-Check Codes for Large Alphabets (2007)

Michael Luby, Michael Mitzenmacher

Most work in low-density parity-check codes focuses on bit-level errors. In this paper, we introduce and analyze verification codes, which are simple low-density parity-check codes specifically...

Exact Sampling of TCP Window States (2007)

Ashish Goel, Michael Mitzenmacher

We demonstrate how to apply Coupling from the Past, a simulation technique for exact sampling, to Markov chains based on TCP variants. This approach provides a new, statistically sound paradigm for...

Alan Frieze (2007)

Eleni Drinea, Michael Mitzenmacher

We examine generalizations of the classical balls and bins models, where the probability a ball lands in a bin is proportional to the number of balls already in the bin raised to some exponent p....

Alan Frieze + (2007)

Eleni Drinea, Michael Mitzenmacher

We examine generalizations of the classical balls and bins models, where the probability a ball lands in a bin is proportional to the number of balls already in the bin raised to some exponent p....

Harvard University (2007)

SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY 100 Binary Intersymbol Interference Channels: Gallager Codes, Density Evolution and Code Performance Bounds (2007)

A Bloom filter is a simple space-e#cient randomized data structure for representing a set in order to support membership queries. Although Bloom filters allow false positives, for many applications...

Xiao Ma, Michael Mitzenmacher

We study the limits of performance of Gallager codes (low-density parity-check codes) over binary linear intersymbol interference (ISI) channels with additive Gaussian noise. Using the graph...

y (2007)

Eleni Drinea, Eleni Drinea, Mihaela Enachescu, Mihaela Enachescu, Michael Mitzenmacher, Michael Mitzenmacher

In this paper, we introduce variations on random graph models for Web-like graphs. As a basis, we recall a model rst presented in [5]. We add vertices to the graph, one per unit time, with each...

Compressed Bloom Filters [Extended Abstract] (2007)

Abstract A Digital Fountain Approach to Reliable Distribution of Bulk Data (2007)

A Bloom filter is a simple space-e#cient randomized data structure for representing a set in order to support membership queries. Although Bloom filters allow false positives, for many applications...

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Unscrambling Address Lines (2007)

Andrei Broder, Michael Mitzenmacher, Laurent Moll

A writer leaves a message in a write-once memory accessible via address lines. Before the intended recipient has a chance to get the message, the address lines are permuted by an adversary. We...

On the Hardness of Finding Optimal Multiple Preset Dictionaries (2007)

We describe Fair Layered Increase/Decrease with Dynamic (2007)

Preset dictionaries for Huffman codes are used effectively in fax transmission and JPEG encoding. A natural extension is to allow multiple preset dictionaries instead of just one. We show, however,...

John W. Byers, Gavin Horn, Michael Luby, Michael Mitzenmacher, William Shaver

We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLIDDL generalizes the receiver-driven...

Harvard University (2007)

Yan-cheng Chang, Michael Mitzenmacher

We consider the following problem: a user U wants to store his files in an encrypted form on a remote file server

Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream (2007)

Michael Mitzenmacher, Salil Vadhan

Hashing is fundamental to many algorithms and data structures widely used in practice. For theoretical analysis of hashing, there have been two main approaches. First, one can assume that the hash...

Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream ∗ (2007)

Michael Mitzenmacher, Salil Vadhan

Hashing is fundamental to many algorithms and data structures widely used in practice. For theoretical analysis of hashing, there have been two main approaches. First, one can assume that the hash...

Wired geometric routing (2007)

Jonathan Ledlie, Michael Mitzenmacher, Margo Seltzer

Routing substrates for overlay networks are an important building block for large distributed applications. Many existing substrates are based on a random identifier space and therefore do not...

Wired geometric routing (2007)

Jonathan Ledlie, Michael Mitzenmacher, Margo Seltzer

Routing substrates for overlay networks are an important building block for large distributed applications. Many existing substrates are based on a random identifier space and therefore do not...

Executive Summary (2006)

Joan Feigenbaum, Michael Mitzenmacher

The increasing prominence of the Internet, the Web, and large data-networks in general has profoundly affected social and commercial activity. It has also wrought one of the most profound shifts in...

Polynomial time low-density parity-check codes with rates very close to the capacity of the q-ary random deletion channel for large q (2006)

Stochastic shortest paths via quasi-convex maximization (2006)

Abstract—We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes � symbols from...

Evdokia Nikolova, Jonathan A. Kelner, Matthew Br, Michael Mitzenmacher

Abstract. We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed...

Stochastic shortest paths via quasi-convex maximization (2006)

Evdokia Nikolova, Jonathan A. Kelner, Matthew Br, Michael Mitzenmacher

Abstract. We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed...

Distance-Sensitive Bloom Filters (2006)

Networkaware overlays with network coordinates (2006)

A Bloom filter is a space-e#cient data structure that answers set membership queries with some chance of a false positive. We introduce the problem of designing generalizations of Bloom filters...

Peter Pietzuch, Jonathan Ledlie, Michael Mitzenmacher, Margo Seltzer

Network coordinates, which embed network distance measurements in a coordinate system, were introduced as a method for determining the proximity of nodes for routing table updates in overlay...

Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines (2006)

Flavio Bonomi, Michael Mitzenmacher, Sushil Singh

Many networking applications require fast state lookups in a concurrent state machine, which tracks the state of a large number of flows simultaneously. We consider the question of how to compactly...

Editorial: The Future of Power Law Research (2006)

An Improved Construction for Counting Bloom Filters (2006)

Abstract. I argue that power law research must move from focusing on observation, interpretation, and modeling of power law behavior to instead considering the challenging problems of validation of...

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese

Abstract. A counting Bloom filter (CBF) generalizes a Bloom filter data structure so as to allow membership queries on a set that can be changing dynamically via insertions and deletions. As with a...

Bloom Filters via d-left Hashing and Dynamic Bit Reassignment (2006)

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese

Abstract — In recent work, the authors introduced a data structure with the same functionality as a counting Bloom filter (CBF) based on fingerprints and the d-left hashing technique. This paper...

The Future of Power Law Research (2005)

Mitzenmacher, Michael

I argue that power law research must move from focusing on observation, interpretation, and modeling of power law behavior to instead considering the challenging problems of validation of models and...

Verification-based decoding for packet-based low-density parity check codes (2005)

Michael G. Luby, Michael Mitzenmacher

Abstract—We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units....

Simple Summaries for Hashing with Multiple Choices (2005)

Building a better Bloom filter (2005)

In a multiple-choice hashing scheme, each item is stored in one of d 2 possible hash table buckets. The availability of these multiple choices allows for a substantial reduction in the maximum load...

Less Hashing, Same Performance: Building a Better Bloom Filter (2005)

A technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(x). We demonstrate that this technique can...

Simple Summaries for Hashing with Multiple Choices (2005)

Abstract. A standard technique from the hashing literature is to use two hash functions h1(x)andh2(x) to simulate additional hash functions of the form gi(x)=h1(x)+ih2(x). We demonstrate that this...

Less Hashing, Same Performance: Building a Better Bloom Filter (2005)

In a multiple-choice hashing scheme, each item is stored in one of d ≥ 2 possible hash table buckets. The availability of these multiple choices allows for a substantial reduction in the maximum...

Privacy Preserving Keyword Searches on Remote Encrypted Data (2005)

A standard technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(x). We demonstrate that this...

Yan-cheng Chang, Michael Mitzenmacher

Abstract. We consider the following problem: a user U wants to store his files in an encrypted form on a remote file server S. Later the user U wants to efficiently retrieve some of the encrypted...

Geometric generalizations of the power of two choices (2004)

John W. Byers, Michael Mitzenmacher

A well-known paradigm for load balancing in distributed systems is the \power of two choices, " whereby an item is stored at the less loaded of two (or more) random alternative servers. We...

Geometric Generalizations of the Power of Two Choices (2004)

John Byers Jeffrey, Jeffrey Considine, Michael Mitzenmacher

A well-known paradigm for load balancing in parallel and distributed systems is the "power of two choices," whereby an item is stored at the less loaded of two (or more) random alternative...

Mitsubishi Electric Research Laboratories (2004)

Http Www Merl, Markus Chimani, Neal Lesh, Michael Mitzenmacher, Candy Sidner, A Case, ...

We describe lessons learned in developing a program for interactive optimization of large airlift scheduling problems. While for small problems one can create a visualization that both shows a...

Geometric generalizations of the power of two choices (2004)

John W. Byers, Jeffrey Considine, Michael Mitzenmacher

A Case Study in Large-Scale Interactive Optimization (2004)

Markus Chimani, Neal Lesh, Michael Mitzenmacher, Y Sidner, Hidetoshi Tanaka, Michael Mitzenmacher

We describe lessons learned in developing a program for interactive optimization of large airlift scheduling problems. While for small problems one can create a visualization that both shows a...

A Brief History of Generative Models for Power Law and Lognormal Distributions (2003)

Mitzenmacher, Michael

Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these...

Dynamic Models for File Sizes and Double Pareto Distributions (2003)

Mitzenmacher, Michael

In this paper, we introduce and analyze a new, dynamic generative user model to explain the behavior of file size distributions. Our Recursive Forest File model combines multiplicative models that...

Network Applications of Bloom Filters: A Survey (2003)

Broder, Andrei, Mitzenmacher, Michael

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters allow false positives but the space savings often...

Binary intersymbol interference channels: Gallager codes, density evolution and code performance bounds (2003)

Ar Kavčić, Xiao Ma, Michael Mitzenmacher

Abstract—We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise...

Simple Load Balancing for Distributed Hash Tables (2003)

John Byers, Jeffrey Considine, Michael Mitzenmacher

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable...

Simple Load Balancing for Distributed Hash Tables (2003)

John Byers, Michael Mitzenmacher

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable...

The Power Spectra of Good Codes for Partial Response Channels,”accepted for (2003)

Xiao Ma, Ar Kavčić, Michael Mitzenmacher, I. Extended Summary

Recently, a serial concatenation coding scheme was proposed to approach the capacity of a partial response (PR) channel [1]. The design of the inner trellis code (named a matched information rate...

Simple Load Balancing for Distributed Hash Tables (2003)

John Byers, Michael Mitzenmacher

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable...

Human-Guided Search for Jobshop Scheduling (2003)

Neal Lesh, Neal Lesh, Leonardo B. Lopes, Leonardo B. Lopes, Joe Marks, Joe Marks, ...

this paper, we present an interactive jobshop scheduling application developed with the HuGS framework and toolkit. The HuGS framework provides the user a greater degree of control than previous...

New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing (2003)

Neal Lesh, Joe Marks, Adam Mcmahon, Michael Mitzenmacher, N. Lesh, J. Marks, ...

this paper, we consider the two-dimensional rectangular strip packing problem

Optimal plans for aggregation (2002)

A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)

We consider the following problem, which arises in the con-text of distributed Web computations. An aggregator aims to combine specific data from n sources. The aggregator contacts all sources at...

Data-flow Distribution (2002)

Abstract—The proliferation of applications that must reliably distribute large, rich content to a vast number of autonomous receivers motivates the design of new multicast and broadcast protocols....

Power Law, Michael Mitzenmacher

Abstract. Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough...

Dynamic models for file sizes and double pareto distributions (2002)

Informed content delivery across adaptive overlay networks (2002)

Abstract. In this paper, we introduce and analyze a new, dynamic generative user model to explain the behavior of file size distributions. Our Recursive Forest File model combines multiplicative...

John W. Byers, Jeffrey Considine, Michael Mitzenmacher, Stanislav Rost

Abstract—Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive...

Network Applications of Bloom Filters: A Survey (2002)

The HuGS platform: A toolkit for interactive optimization (2002)

Abstract. ABloomfilter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters allow false positives but the space savings...

Gunnar W. Klau, Neal Lesh, Joe Marks, Michael Mitzenmacher, Guy T. Schafer, Gunnar W. Klau, ...

In this paper we develop a generalized approach to visualizing and controlling an optimization process. Our framework, called Human-Guided Search, actively involves people in the process of...

A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)

Bounds and improvements for BiBa signature schemes (2002)

Abstract The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe...

Michael Mitzenmacher, Michael Mitzenmacher, Adrian Perrig, Adrian Perrig

This paper analyzes and improves the recently proposed bins and balls signature (BiBa [23]), a new approach for designing signatures from one-way functions without trapdoors. We rst construct a...

Human-Guided Tabu Search (2002)

Gunnar W. Klau, Neal Lesh, Joe Marks, Michael Mitzenmacher

We present a human-guidable and general tabu search algorithm. Our work expands on previous interactive optimization techniques that provide for substantial human control over a simple, exhaustive...

Informed content delivery across adaptive overlay networks (2002)

John Byers, Jeffrey Considine, Michael Mitzenmacher, Stanislav Rost

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large, multipoint transfers across richly connected overlay...

Dynamic models for file sizes and double pareto distributions (2002)

Load balancing with memory (2002)

In this paper, we introduce and analyze a new generative user model to explain the behavior of le size distributions. Our Recursive Forest File model combines ideas from recent work by Downey with...

Michael Mitzenmacher, Balaji Prabhakar, Devavrat Shah

A standard load balancing model considers placing n balls into n bins by choosing d possible locations for each ball independently and uniformly at random and sequentially placing each in the least...

Fast Approximate Reconciliation of Set Differences (2002)

John Byers, Jeffrey Considine, Michael Mitzenmacher

We present new, simple, efficient data structures for approximate reconciliation of set differences, a useful standalone primitive for peer-to-peer networks and a natural subroutine in methods for...

Balls and Bins Models with Feedback (2002)

Eleni Drinea, Alan Frieze, Michael Mitzenmacher

michaelmeecs. harvard. edu We examine generalizations of the classical balls and bins models, where the probability a ball lands in a bin is proportional to the number of balls already in the bin...

Verification codes (2002)

Michael Luby, Michael Mitzenmacher

Most work in low-density parity-check codes focuses on bit-level errors. In this paper, we introduce and analyze verification codes, which are simple low-density parity-check codes specifically...

Optimal plans for aggregation (2002)

Andrei Broder, Altavista Corporation, Michael Mitzenmacher

We consider the following problem, which arises in the context of distributed Web computations. An aggregator aims to combine specific data from n sources. The aggregator contacts all sources at...

Dynamic models for file sizes and double pareto distributions (2002)

Mitsubishi Electric Research Laboratories (2002)

In this paper, we introduce and analyze a new generative user model to explain the behavior of file size distributions. Our Recursive Forest File model combines ideas from recent work by Downey with...

Http Www Merl, Gunnar W. Klau, Gunnar W. Klau, Neal Lesh, Neal Lesh, Joe Marks, ...

this paper were among the test subjects for num initial after 30 after 300 after 600 trials solut- minutes minutes minutes ion guided unguided unguided Delivery 4 61.46 60.86 60.97 60.94 Crossing 8...

The HuGS platform: A toolkit for interactive optimization (2002)

Gunnar W. Klau, Neal Lesh, Joe Marks, Michael Mitzenmacher, Guy T. Schafer

Dynamic models for file sizes and double pareto distributions (2002)

The HuGS platform: A toolkit for interactive optimization (2002)

In this paper, we introduce and analyze a new generative user model to explain the behavior of file size distributions. Our Recursive Forest File model combines ideas from recent work by Downey with...

Gunnar W. Klau, Gunnar W. Klau, Neal Lesh, Neal Lesh, Joe Marks, Joe Marks, ...

In this paper we develop a generalized approach to visualizing andrapid development of humanguided search systems. AVI ´02

Human-Guided Tabu Search (2002)

Gunnar W. Klau, Neal Lesh, Joe Marks, Michael Mitzenmacher

We present a human-guidable and general tabu search algorithm. Our work expands on previous interactive optimization techniques that provide for substantial human control over a simple, exhaustive...

Informed Content Delivery across Adaptive Overlay Networks (2002)

John Byers, Jeffrey Considine, Michael Mitzenmacher, Stanislav Rost

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive overlay...

Simple Load Balancing for Distributed Hash Tables (2002)

John Byers Byers, Michael Mitzenmacher

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable...

A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)

Human-Guided Search for Jobshop Scheduling (2002)

The proliferation of applications that must reliably distribute large, rich content to a vast number of autonomous receivers motivates the design of new multicast and broadcast protocols. We describe...

Neal Lesh, Leonardo B. Lopes, Joe Marks, Michael Mitzenmacher, Guy T. Schafer

We present an interactive jobshop scheduling application developed with the Human-Guided Search (HuGS) framework and toolkit. Our system leverages people’s abilities in areas in which they...

Microsoft Research (2002)

Ministère Recherche, Science Et Technologie, Ministère Recherche, Science Et Technologie, ...

34th ACM Symposium

Data-flow Distribution (2002)

Power Law, Michael Mitzenmacher

Abstract. Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough...

Efficient erasure correcting codes (2001)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman

Abstract—We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random...

A brief history of generative models for power law and lognormal distributions (2001)

Recently, I became interested in a current debate over whether le size distributions are best modelled by a power law distribution or a a lognormal distribution. In trying to learn enough about these...

Towards more complete models of TCP latency and throughput (2001)

Abstract. Search engines often employ techniques for determining syntactic similarity of Web pages. Such a tool allows them to avoid returning multiple copies of essentially the same page when a user...

Michael Mitzenmacher, Rajmohan Rajaraman

Recently, several researchers have developed equations for modeling TCP behaviors, such as the expected throughput or latency, based on Markov chains derived from TCP with additional simplifying...

Improved low-density parity-check codes using irregular graphs (2001)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman

Abstract—We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes. We improve on Gallager’s results by introducing irregular parity-check matrices...

Using multiple hash functions to improve ip lookups (2001)

Andrei Broder, Andrei Broder, Michael Mitzenmacher, Michael Mitzenmacher

High performance Internet routers require a mechanism for very ecient IP address look-ups. Some techniques used to this end, such as binary search on levels, need to construct quickly a good hash...

In this paper, we consider the problem of compressing graphs of the link structure of the World Wide Web. We provide efficient algorithms for such compression that are motivated by recently proposed...

Capacity approaching signal constellations for channels with memory (2001)

Abstract. Search engines often employ techniques for determining syntactic similarity of Web pages. Such a tool allows them to avoid returning multiple copies of essentially the same page when a user...

Xiao Ma, Michael Mitzenmacher, Nedeljko Varnica

The i.i.d. rate of a channel is the mutual information rate between the channel input and the channel output when the channel input symbols are independent, identically distributed (i.i.d.) and...

Towards more complete models of tcp latency and throughput (2001)

Michael Mitzenmacher, Rajmohan Rajaraman

Abstract. Recently, several researchers have developed equations for modeling TCP behaviors, such as the expected throughput or latency, based on Markov chains derived from TCP with additional...

A brief history of generative models for power law and lognormal distributions (2001)

The power of two random choices: a survey of techniques and results (2001)

Power law distributions are an increasingly common model for computer science applications; for example, they have been used to describe file size distributions and in- and out-degree distributions...

Michael Mitzenmacher, Andrea W. Richa, Ramesh Sitaraman

To motivate this survey, we begin with a simple problem that demonstrates a powerful fundamental idea. Suppose that n balls are thrown into n bins, with

We consider the problem of compressing graphs of the link structure of the World Wide Web. We provide efficient algorithms for such compression that are motivated by recently proposed random graph...

Fine-grained layered multicast (2001)

Abstract. Search engines often employ techniques for determining syntactic similarity of Web pages. Such a tool allows them to avoid returning multiple copies of essentially the same page when a user...

Using multiple hash functions to improve ip lookups (2001)

Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...

Abstract--- High performance Internet routers require a mechanism for very efficient IP address look-ups. Some techniques used to this end, such as binary search on levels, need to construct quickly...

Fine-grained layered multicast (2001)

We consider the problem of compressing graphs of the link structure of the World Wide Web. We provide efficient algorithms for such compression that are motivated by recently proposed random graph...

Fine-grained layered multicast (2001)

Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...

Efficient Erasure Codes (2001)

Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with TCP-friendliness...

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman, Volker Stemann

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graph and analyze the algorithm using the theory of discrete time random processes. As a result we...

Improved Results for Route Planning in Stochastic Transportation Networks (2001)

Justin Boyan, Michael Mitzenmacher

In the bus network problem, the goal is to generate a plan for getting from point X to point Y within a city using buses in the smallest expected time. Because bus arrival times are not determined by...

Improved low-density parity-check codes using irregular graphs (2001)

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman

We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...

Improved low-density parity-check codes using irregular graphs (2001)

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman

We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...

Towards more complete models of tcp latency and throughput (2001)

Abstract. Search engines often employ techniques for determining syntactic similarity ofWeb pages. Suchatoolallows them to avoid returning multiple copies of essentially the same page when a user...

Michael Mitzenmacher, Rajmohan Rajaraman Y

Abstract. Recently, several researchers have developed equations for modeling TCP behaviors, such as the expected throughput or latency, based on Markov chains derived from TCP with additional...

Using multiple hash functions to improve ip lookups (2001)

Abstract — High performance Internet routers require a mechanism for very efficient IP address look-ups. Some techniques used to this end, such as binary search on levels, need to construct quickly...

A brief history of generative models for power law and lognormal distributions (2001)

We consider the problem of compressing graphs of the link structure of the World Wide Web. We provide efficient algorithms for such compression that are motivated by recently proposed random graph...

Improved low-density parity-check codes using irregular graphs (2001)

Power law distributions are an increasingly common model for computer science applications; for example, they have been used to describe file size distributions and in- and out-degree distributions...

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman

We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...

An extension of path coupling and its application to the Glauber dynamics for graph colorings (2001)

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum, Michael Mitzenmacher

Abstract. A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps. The expected...

Linear waste of best fit bin packing on skewed distributions (2000)

Flid-dl: Congestion control for layered multicast (2000)

We prove that Best Fit bin packing has linear waste on the discrete distribution U{j, k} (where items are drawn uniformly from the set {1/k,

John W. Byers, Gavin Horn, Michael Luby, Michael Mitzenmacher, William Shaver

Abstract—We describe fair layered increase/decrease with dynamic layering (FLID-DL): a new multirate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the...

Improved Classification via Connectivity Information (2000)

Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher

The motivation for our work is the observation that Web pages on a particular topic are often linked to other pages on the same topic. We model and analyze the problem of how to improve the...

Linear waste of best fit bin packing on skewed distributions (2000)

Linear Waste of Best Fit Bin Packing on Skewed Distributions (2000)

We prove that Best Fit bin packing has linear waste on the discrete distribution U{j, k} (where items are drawn uniformly from the set {1/k,

FLID-DL: Congestion Control for Layered Multicast (2000)

We prove that Best Fit bin packing has linear waste on the discrete distribution U{j, k} where items are drawn uniformly from the set {1/k, 2/3, , j/k} for su#ciently large k when j = #k and .66 # #...

John Byers, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...

We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the receiver-driven...

FLID-DL: Congestion Control for Layered Multicast (2000)

John Byers Michael, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...

We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the receiver-driven...

Linear waste of best fit bin packing on skewed distributions (2000)

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum, Michael Mitzenmacher

ABSTRACT: We prove that Best Fit bin packing has linear waste on the discrete distribution U{j, k} (where items are drawn uniformly from the set {1/k, 2/k,...,j/k}) for sufficiently large kwhen j �...

the Glauber (2000)

extension of path coupling and its application to

Measuring index quality using random walks on the web (1999)

Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...

Measuring index quality using random walks on the web (1999)

Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...

Contents (1999)

Maxwell Krohn, Michael O. Rabin, Michael Mitzenmacher

1.1 Private and Public Key Cryptography..................... 5

The asymptotics of selecting the shortest of two, improved (1999)

Michael Mitzenmacher, Berhold Vocking

We investigate variations of a novel, recently proposed load balancing scheme based on small amounts of choice. The static setting is modeled as a balls-and-bins process. The balls are sequentially...

The asymptotics of selecting the shortest of two, improved (1999)

Berhold Voecking, Michael Mitzenmacher, Michael Mitzenmacher

We investigate variations of a novel, recently proposed load balancing scheme based on small amounts of choice. The static (hashing) setting is modeled as a balls-and-bins process. The balls are...

Measuring Index Quality using Random Walks on the Web (1999)

Monikar Henzinger Allan, Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...

Analysis of Timing Based Mutual Exclusion with Random Times (1999)

Eli Gafni, Michael Mitzenmacher

Various timing based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave when the...

Measuring Index Quality using Random Walks on the Web (1999)

Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...

The Asymptotics of Selecting the Shortest of Two, Improved (1999)

Michael Mitzenmacher, Berhold Vöcking

this paper, we consider a variation based on the work by Vocking [6]. In his basic model,

Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads (1999)

Studying Balanced Allocations with Differential Equations (1999)

Mirror sites enable client requests to be serviced by any of a number of servers, reducing load at individual servers and dispersing network load. Typically, a client requests service from a single...

Michael Mitzenmacher, Michael Mitzenmacher Y

Using differential equations, we examine the GREEDY algorithm studied by Azar, Broder, Karlin, and Upfal for distributed load balancing [1]. This approach yields accurate estimates of the actual load...

Completeness and robustness properties of min-wise independent permutations (1999)

Andrei Z. Broder, Michael Mitzenmacher

We provide several new results related to the concept of minwise independence. Our main result is that any randomized sampling scheme for the relative intersection of sets based on testing equality...

Measuring index quality using random walks on the web (1999)

Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork

Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a di erent measure for search engines, namely the quality...

Mitzenmacher: Completeness and robustness properties of min-wise independent permutations, Random Structures and Algorithms (1999)

Andrei Z. Broder, Michael Mitzenmacher

Abstract. We provide several new results related to the concept of minwise independence. Our main result is that any randomized sampling scheme for the relative intersection of sets based on testing...

The asymptotics of selecting the shortest of two, improved (1999)

Michael Mitzenmacher, Berhold Vocking

We investigate variations of a novel, recently proposed load balancing scheme based on small amounts of choice. The static (hashing) setting is modeled as a balls-and-bins process. The balls are...

Mitzenmacher: Completeness and robustness properties of min-wise independent permutations, Random Structures and Algorithms (1999)

Andrei Z. Broder, Michael Mitzenmacher

ABSTRACT: We provide several new results related to the concept of min-wise independence. Our main result is that any randomized sampling scheme for the relative intersection of sets based on testing...

Analysis of timing-based mutual exclusion with random times (1999)

Eli Gafni, Michael Mitzenmacher

Abstract. Various timing-based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave...

Studying Balanced Allocations with Differential Equations (1999)

Michael Mitzenmacher, Michael Mitzenmacher Y

Using differential equations, we examine the GREEDY algorithm studied by Azar, Broder, Karlin, and Upfal for distributed load balancing [1]. This approach yields accurate estimates of the actual load...

Min-wise Independent Permutations (1998)

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher

We define and study the notion of min-wise independent families of permutations. We say that F ⊆ Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in...

On Balls and Bins with Deletions (1998)

Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh Sitaraman, ...

Microsystems. The views and conclusions contained here are those of the authors and should not be interpreted as necessarily representing the official policies or

Analysis of Random Processes via And-Or Tree Evaluation (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi

We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the...

Delayed information and action in on-line algorithms (1998)

Susanne Albers, Moses Charikar, Michael Mitzenmacher

Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate e#ect. In many on-line problems, however, the time...

Min-wise Independent Permutations (1998)

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher

We define and study the notion of min-wise independent families of permutations. We say that F ⊆ Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in...

A digital fountain approach to reliable distribution of bulk data (1998)

Analysis of Random Processes via Or-And Tree Evaluation (1998)

Abstract—The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe...

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi

We introduce a new set of probabilistic analysis tools related to the amplification method introduced by [12] and further developed and used in [13], [5]. These tools provide a unifying, intuitive,...

On the Analysis of Randomized Load Balancing Schemes (1998)

A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper,...

John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (1998)

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Daniel A. Spielman

We construct new families of error-correcting codes based on Gallager's low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can...

A Note on Low Density Parity Check Codes for Erasures and Errors (1998)

How Useful is Old Information? (1998)

We analyze low density parity check codes that correct both errors and erasures using a simple decoding scheme. Our framework unifies previous analyses for low density parity check codes and erasure...

Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads (1998)

Michael Mitzenmacher # Abstract We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a...

Practical Loss-Resilient Codes (1998)

Mirror sites enable client requests to be serviced by any of a number of servers, reducing load at individual servers and dispersing network load. Typically, a client requests service from a single...

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman, Volker Stemann

We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for...

Analysis of Low Density Codes and Improved Designs Using Irregular Graphs (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density paritycheck codes. He suggests a natural decoding algorithm for these codes, and proves a...

Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1998)

On Balls and Bins with Deletions (1998)

We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...

Richard Cole Alan, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal

We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...

Delayed Information and Action in On-Line Algorithms (1998)

Susanne Albers, Moses Charikar, Michael Mitzenmacher

Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...

A Derandomization Using Min-Wise Independent Permutations (Extended Abstract) (1998)

Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher

Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The later has proven essential for the derandomization of many algorithms....

A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Analyses of Load Stealing Models Based on Differential Equations (1998)

Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1998)

In this paper we develop models for and analyze several randomized work stealing algorithms in a dynamic setting. Our models represent the limiting behavior of systems as the number of processors...

Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks (1998)

We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...

Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...

Analysis of Low Density Codes and Improved Designs Using Irregular Graphs (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, M. Amin, Shokrollahi Daniel, Daniel A. Spielman

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a...

On Balls and Bins with Deletions (1998)

Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Andr'ea W. Richa, ...

We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...

A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman

We construct new families of low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct more errors than previously known low-density...

Average-Case Analyses of First Fit and Random Fit Bin Packing (1998)

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

We prove that the First Fit bin packing algorithm is stable under the input distribution Ufk \Gamma 2; kg for all k 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...

John W. Byers (1998)

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (1998)

Michael Luby, Michael Mitzenmacher, M. Amin Shokrollahi, M. Amin, Daniel A. Spielman

We construct new families of error-correcting codes based on Gallager's low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can...

A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)

John Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Analysis of Low Density Codes and Improved Designs Using Irregular Graphs (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, M. Amin, Daniel A. Spielman

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a...

Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks (1998)

Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Friedhelm Meyer, Heide Michael Mitzenmacher, ...

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...

Analysis of Random Processes via And-Or Tree Evaluation (1998)

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, M. Amin

We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the...

A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)

John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Average-case analysis of first fit and random fit bin packing (1998)

Analysis of Random Processes via And-Or Tree Evaluation (1998)

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k − 2, k} for all k ≥ 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...

Michael G. Luby, Michael Mitzenmacher

We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the...

A derandomization using min-wise independent permutations (1998)

Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher

Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The later has proven essential for the derandomization of many algorithms....

A digital fountain approach to reliable distribution of bulk data (1998)

John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

A digital fountain approach to reliable distribution of bulk data (1998)

John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Average-case analysis of first fit and random fit bin packing (1998)

Min-wise Independent Permutations (1998)

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k − 2, k} for all k ≥ 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher

We define and study the notion of min-wise independent families of permutations. We say that F⊆Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, whenπ is chosen at random in F...

Delayed information and action in on-line algorithms (1998)

Susanne Albers, Moses Charikar, Michael Mitzenmacher

Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...

Average case analyses of list update algorithms, with applications to data compression (1998)

How Useful is Old Information? EXTENDED ABSTRACT (1998)

We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...

Analysis of low density codes and improved designs using irregular graphs (1998)

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multi-processor system where...

Michael G. Luby, Michael Mitzenmacher, M. Amin, Shokrollahi Daniel, A. Spielman

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a...

A note on low density parity check codes for erasures and errors. SRC technical note 1998-017 (1998)

: www.idealibrary.com on Min-Wise Independent Permutations (1998)

We analyze low density parity check codes that correct both errors and erasures using a simple decoding scheme. Our framework unifies previous analyses for low density parity check codes and erasure...

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher

We define and study the notion of min-wise independent families of permutations. We say that F Sn (the symmetric group) is min-wise independent if for any set X [n] and any x # X, when? is chosen at...

A digital fountain approach to reliable distribution of bulk data (1998)

John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal,...

Average-case analysis of first fit and random fit bin packing (1998)

Delayed information and action in on-line algorithms (1998)

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k − 2, k} for all k ≥ 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...

Susanne Albers, Moses Charikar, Michael Mitzenmacher

Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time...

How Useful is Old Information? EXTENDED ABSTRACT (1998)

Analysis of low density codes and improved designs using irregular graphs (1998)

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multi-processor system where...

Michael G. Luby, Michael Mitzenmacher, M. Amin, Shokrollahi Daniel, A. Spielman

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a...

Practical Loss-Resilient Codes (1997)

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman, Volker Stemann

We present a randomized construction of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for...

Studying Balanced Allocations with Differential Equations (1997)

Tight Thresholds for The Pure Literal Rule (1997)

Using differential equations, we examine the GREEDY algorithm studied by Azar, Broder, Karlin, and Upfal for distributed load balancing [1]. This approach yields accurate estimates of the actual load...

Average-Case Analysis of First Fit and Random Fit Bin Packing (1997)

We consider the threshold for the solvability of random k-SAT formulas (for k # 3) using the pure literal rule. We demonstrate how this threshold can be found by using differential equations to...

How Useful is Old Information? (1997)

We prove that the First Fit bin packing algorithm is stable under the input distribution U {k - 2, k} for all k # 3, settling an open question from the recent survey by Coffman, Garey, and Johnson...

Constant Time Per Edge is Optimal on Rooted Tree Networks (1997)

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multi-processor system where...

On the Analysis of Randomized Load Balancing Schemes (1997)

We analyze the relationship between the expected packet delay in rooted tree networks and the distribution of time needed for a packet to cross an edge using convexity-based stochastic comparison...

Tight thresholds for the pure literal rule (1997)

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper,...

Tight thresholds for the pure literal rule (1997)

We consider the threshold for the solvability of random k-SAT formulas (for k ≥ 3) using the pure literal rule. We demonstrate how this threshold can be found by using differential equations to...

How useful is old information (1997)

We consider the threshold for the solvability of random k-SAT formulas (for k ≥ 3) using the pure literal rule. We demonstrate how this threshold can be found by using differential equations to...

On the Analysis of Randomized Load Balancing Schemes (1997)

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multi-processor system where...

Practical Loss-Resilient Codes (1997)

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper,...

Michael Luby Michael, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman, Volker Stemann

We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for...

On the Analysis of Randomized Load Balancing Schemes (1997)

Distrib. Comput. (1997) 10: 189—197 Constant time per edge is optimal on rooted tree networks* (1996)

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper,...

Constant Time Per Edge is Optimal on Rooted Tree Networks (1996)

Abstract. We analyze the relationship between the expected packet delay in rooted tree networks and the distribution of time needed for a packet to cross an edge using convexity-based stochastic...

The power of two choices in randomized load balancing (1996)

We analyze how the expected packet delay in rooted tree networks is affected by the distribution of time needed for a packet to cross an edge using stochastic comparison methods. Our result...

AbstractÐWe consider the following natural model: Customers arrive as a Poisson stream of rate n, <1, at a collection of n servers. Each customer chooses some constant d servers independently and...

Maxwell N. Krohn, Advisors Professors, Michael O. Rabin, Michael Mitzenmacher

Computer systems, with emphasis on operating systems, security and distributed systems. 2007 – W5, or A World Wide Web Without Walls. Conceived of and now prototyping W5, a new architecture for the...

Maxwell N. Krohn, Advisors Professors, Michael O. Rabin, Michael Mitzenmacher

Computer systems, with emphasis on operating systems, security and distributed systems. 2007 – W5, or A World Wide Web Without Walls. Conceived of and now prototyping W5, a new architecture for the...

Maxwell N. Krohn, Advisors Professors, Michael O. Rabin, Michael Mitzenmacher

Computer systems, with emphasis on operating systems, security and distributed systems. 2007 – W5, or A World Wide Web Without Walls. Conceived of and now prototyping W5, a new architecture for the...

Maxwell N. Krohn, Advisors Professors, Michael O. Rabin, Michael Mitzenmacher

Computer systems, with emphasis on operating systems, security and distributed systems. 2007 – W5, or A World Wide Web Without Walls. Conceived of and now prototyping W5, a new architecture for the...

Parallel Randomized Load Balancing (1995)

Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen

It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al....

Parallel Randomized Load Balancing (1995)

Preliminary Version, Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen

It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al....

Parallel Randomized Load Balancing (1995)

Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen

It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds #(log n/ log log n) balls with high probability. More recently, Azar et al....

Average Case Analyses of List Update Algorithms, with Applications to Data Compression (1995)

Parallel randomized load balancing (1995)

We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such...

Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen

It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds Θ(log n / log log n) balls with high probability. More recently, Azar et al....

Parallel randomized load balancing (1995)

Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen

ABSTRACT: It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds �Ž log n�log log n. balls with high probability. More recently,...

Maxwell N. Krohn, Advisors Professors, Michael O. Rabin, Michael Mitzenmacher

Computer systems, with emphasis on operating systems, security and distributed systems. 2007 – W5, or A World Wide Web Without Walls. Conceived of and now prototyping W5, a new architecture for the...

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

We analyze the performance of greedy routing for array networks by providing bounds on the average delay and the average number of packets in the system for the dynamic routing problem. In this model...