Now showing items 1-20 of 21

    • The Asymptotics of Selecting the Shortest of Two, Improved 

      Mitzenmacher, Michael D.; Vocking, Berhold (1999)
      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 sequentially placed into ...
    • Bounds and Improvements for BiBa Signature Schemes 

      Mitzenmacher, Michael D.; Perrig, Adrian (2002)
      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 first construct a general framework for ...
    • A Brief History of Generative Models for Power Law and Lognormal Distributions 

      Mitzenmacher, Michael D. (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 for the Web and Internet ...
    • Building a Better Bloom Filter 

      Kirsch, Adam; Mitzenmacher, Michael D. (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 be usefully applied to ...
    • Cleaning up the record on the maximal information coefficient and equitability 

      Reshef, David N.; Reshef, Yakir Abraham; Mitzenmacher, Michael D.; Sabeti, Pardis Christine (Proceedings of the National Academy of Sciences, 2014)
    • Codes for Deletion and Insertion Channels with Segmented Errors 

      Liu, Zhenming; Mitzenmacher, Michael D. (2006)
      We consider deletion channels and insertion channels under an additional segmentation assumption: the input consists of disjoint segments of b consecutive bits, with at most one error per segment. Under this assumption, ...
    • Concatenated Codes for Deletion Channels 

      Chen, Johnny; Mitzenmacher, Michael D.; Ng, Chaki; Varnica, Nedeljko (2003)
      We design concatenated codes suitable for the deletion channel. The inner code is a combination of a single deletion correcting Varshamov-Tenengolts block code and a marker code. The outer code is a low-density parity-check ...
    • Dynamic Models for File Sizes and Double Pareto Distributions 

      Mitzenmacher, Michael D. (2001)
      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 ideas from recent work ...
    • An Economically Principled Generative Model of AS Graph Connectivity 

      Corbo, Jacomo; Jain, Shaili; Mitzenmacher, Michael D.; Parkes, David C. (Association for Computing Machinery, 2007)
      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 structure. We view the graph ...
    • An Economically-Principled Generative Model of AS Graph Connectivity 

      Corbo, Jacomo; Jain, Shaili; Mitzenmacher, Michael D.; Parkes, David C. (Institute of Electrical and Electronics Engineers, 2009)
      End-to-end packet delivery in the Internet is achieved through a system of interconnections between the network domains of independent entities called autonomous systems (ASes). Inter-domain connections are the result of ...
    • Estimating and Comparing Entropy across Written Natural Languages Using PPM Compression 

      Behr, Jr., Frederic H.; Fossum, Victoria; Mitzenmacher, Michael D.; Xiao, David (2002)
      Previous work on estimating the entropy of written natural language has focused primarily on English. We expand this work by considering other natural languages, inluding Arabic, Chinese, French, Greek, Japanese, Korean, ...
    • Estimating Resemblance of MIDI Documents 

      Mitzenmacher, Michael D.; Owen, Sean (2000)
      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 makes a query. Here we describe ...
    • The Evolution of Two-Sided Markets: A Dynamic Model 

      Zhu, Feng; Mitzenmacher, Michael D. (2010)
      Static models of two-sided markets often lead to multiple equilibria as a result of increasing return to demand. Typically the market can be monopolistic or oligopolistic in equilibrium. We provide a simple dynamic model ...
    • On the Hardness of Finding Optimal Multiple Preset Dictionaries 

      Mitzenmacher, Michael D. (2000)
      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, that finding optimal ...
    • Practical Verified Computation with Streaming Interactive Proofs 

      Thaler, Justin R (2013-10-14)
      As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown urgent. Protocols for verifiable computation enable a weak client to outsource difficult computations to a powerful, ...
    • Probabilistic Algorithms for Information and Technology Flows in the Networks 

      Liu, Zhenming (2012-10-16)
      This thesis studies several probabilistic algorithms for information and technology flow in the networks. Information flow refers to the circulation of information in social or communication networks for the purpose of ...
    • Towards Better Definitions and Measures of Internet Security 

      Aspnes, James; Feigenbaum, Joan; Mitzenmacher, Michael D.; Parkes, David C. (2011-02-15)
    • Towards Compressing Web Graphs 

      Adler, Micah; Mitzenmacher, Michael D. (2000)
      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 random graph models for ...
    • Using Multiple Hash Functions to Improve IP Lookups 

      Mitzenmacher, Michael D.; Andrei, Broder (2000)
      High performance Internet routers require a mechanism for every efficient IP address look-ups. Some techniques used to this end, such as binary search on levels, need to construct quickly a good hash table for the appropriate ...
    • Variations on Random Graph Models for the Web 

      Drinea, Eleni; Enachescu, Mihaela; Mitzenmacher, Michael D. (2001)