s Publications - Michael Mitzenmacher

Michael Mitzenmacher : Publications By Year


All conference and journal papers are listed. If a conference paper later appeared as a journal paper, the pdf or postscript of the journal paper is provided when possible; otherwise, the pdf or postscript of the conference paper appears when possible. Technical reports are listed only if they did not appear elsewhere.

    Submitted or Accepted but Otherwise Unpublished Works

  1. M. Mitzenmacher.
    A New Approach to Analyzing Robin Hood Hashing.
    Preliminary version at arXiv

  2. D. Reshef, Y. Reshef, M. Mitzenmacher, and P. Sabeti.
    Equitability Analysis of the Maximal Information Coefficient, with Comparisons.
    Preliminary version at arXiv

  3. M. Mitzenmacher and R. Pagh.
    Simple Multi-Party Set Reconciliation.
    Preliminary version at arXiv
    Submitted.

    2014

  4. A. Boral and M. Mitzenmacher.
    Multi-Party Set Reconciliation Using Characteristic Polynomials
    Arxiv version at arXiv
    Allerton 2014.

  5. M. Mitzenmacher.
    Cuckoo Filter: Practically Better than Bloom
    B. Fan, D. G. Andersen, M. Kaminsky, M. Mitzenmacher
    Conference version (pdf)
    To appear at ACM CoNext 2014.

  6. D. Reshef, Y. Reshef, M. Mitzenmacher, and P. Sabeti.
    Cleaning up the record on the maximal information coefficent and equitability.
    PNAS 2014 111(33) E3362-E3363.


  7. M. Mitzenmacher and E. Upfal
    Some Practical Randomized Algorithms and Data Structures
    In Computing Handbook, Third Edition: Computer Science and Software Engineering
    Chapter 11

  8. P. Li, M. Mitzenmacher, and A. Shrivastava.
    Coding for Random Projections
    To appear at ICML 2014.
    Preliminary version at arXiv

  9. M. Mitzenmacher
    Balanced Allocations and Double Hashing
    To appear at SPAA 2014.
    Preliminary version at arXiv

  10. J. Jiang, M. Mitzenmacher, and J. Thaler.
    Parallel Peeling Algorithms.
    To appear at SPAA 2014.
    Preliminary version at arXiv

  11. D. Eppstein, M. Goodrich, M. Mitzenmacher, and P. Pszona.
    Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket
    To appear at SEA 2014.
    Version at arXiv

  12. S. Pontarelli, P. Reviriego, and M. Mitzenmacher.
    Improving the performance of Invertible Bloom Lookup Tables.
    Inf. Process. Lett. 114(4): 185-191 (2014)

  13. M. Mitzenmacher, R. Pagh, and N. Pham.
    Efficient Estimation for High Similarities using Odd Sketches.
    To appear in the WWW Conference, 2014.
    Preliminary version online here

    2013

  14. G. Cormode, M. Mitzenmacher, and J. Thaler.
    Streaming Graph Computations with a Helpful Advisor
    Algorithmica: Volume 65, Issue 2 (2013), Pages 409-442.

  15. E. Angelino, M. Goodrich, M. Mitzenmacher, and J. Thaler.
    External-Memory Multimaps
    Algorithmica: Volume 67, Issue 1 (2013), Pages 23-48.

  16. K. Chung, M. Mitzenmacher, and S. Vadhan
    Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream
    Theory of Computing , vol 9, pp. 897-945.

    2012

  17. J. Byers, M. Mitzenmacher, and G. Zervas.
    The Daily Deals Marketplace: Empirical Observations and Managerial Implications
    SIGEcom Exchanges, Dec 2012.

  18. Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco Servedio, and Chris Umans.
    Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009)
    SIAM J. Comput. 41-6 (2012)

  19. M. Mitzenmacher, J. Thaler.
    Peeling Arguments and Double Hashing
    To appear in Allerton 2012.

  20. M. Mitzenmacher, G. Varghese.
    The Complexity of Object Reconciliation, and Open Problems Related to Set Difference and Coding
    To appear in Allerton 2012.

  21. M. Goodrich, D. Hirschberg, M. Mitzenmacher, J. Thaler.
    Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability
    To appear in MedAlg 2012.

  22. J. Feigenbaum, M. Mitzenmacher, and G. Zervas.
    An Economic Analysis of User-Privacy Options in Ad-Supported Services
    To appear in WINE 2012.
    Preliminary version at arXiv

  23. A. Kirsch, M. Mitzenmacher, A. Pietracaprina, G. Pucci, E. Upfal, F. Vandin
    An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
    Journal of the ACM
    Vol 59, Issue 3, June 2012.
    ACM DL link

  24. M. Mitzenmacher, H. Pfister, M. Roberts, J. Thaler.
    Verifiable Computation with Massively Parallel Interactive Proofs
    To appear in HotCloud 2012.
    Arxiv version

  25. M. Goodrich and M. Mitzenmacher.
    Anonymous Card Shuffling and its Applications to Parallel Mixnets
    To appear in ICALP 2012.
    Arxiv version

  26. M. Mitzenmacher and G. Varghese.
    Biff (Bloom Filter) Codes: Fast Error Correction for Large Data Sets
    To appear in ISIT 2012.
    ISIT version (pdf) [note: with some typos corrected]

  27. I. Ivan, M. Mitzenmacher, J. Thaler, and H. Yuen.
    Continuous Time Channels with Interference.
    To appear in ISIT 2012.
    Arxiv version

  28. J. Byers, M. Mitzenmacher, and G. Zervas.
    The Groupon Effect on Yelp Ratings: A Root Cause Analysis
    To appear in EC 2012.
    Arxiv version

  29. K. Chung, H. Lam, Z. Liu and M. Mitzenmacher.
    Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
    To appear in STACS 2012.
    Arxiv version

  30. M. Goodrich, M. Mitzenmacher, O. Ohrimenko and R. Tamassia.
    Practical Oblivious Storage
    To appear in CODASPY 2012.
    Arxiv version

  31. M. Mitzenmacher, T. Steinke, J. Thaler.
    Hierarchical Heavy Hitters with the Space Saving Algorithm
    To appear in ALENEX 2012.
    Arxiv version

  32. J. Byers, M. Mitzenmacher, and G. Zervas.
    Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications
    To appear in WSDM 2012.
    Arxiv version

  33. G. Cormode, M. Mitzenmacher, and J. Thaler.
    Practical Verified Computation with Streaming Interactive Proofs
    To appear in ITCS 2012.
    Arxiv version

  34. H. Lam, Z. Liu, M. Mitzenmacher, X. Sun, Y. Wang.
    Information Dissemination via Random Walks in d-Dimensional Space
    To appear in SODA 2012.
    Arxiv version

  35. M.Goodrich, M. Mitzenmacher, O. Ohrimenko, R. Tamassia.
    Privacy-Preserving Group Data Access via Stateless Oblivious
    To appear in SODA 2012.
    Arxiv version

    2011

  36. D. Reshef, Y. Reshef, H. Finucane, S. Grossman, G. McVean, P. Turnbaugh, E. Lander, M. Mitzenmacher, P. Sabeti.
    Detecting novel associations in large datasets.
    In Science. Here's a link to the project page, where you can get a link to the paper.

  37. D. Alcantara, V. Volkov, S. Sengupta, M. Mitzenmacher, J. Owens, and N. Amenta.
    Building an Efficient Hash Table on the GPU
    In GPU Computing Gems Jade Edition

  38. M. Goodrich, M. Mitzenmacher.
    Invertible Bloom Lookup Tables
    To appear at Allerton 2011.
    Arxiv version (pdf)

  39. E. Angelino, M. Goodrich, M. Mitzenmacher, J. Thaler.
    External-Memory Multimaps
    To appear in ISAAC 2011.
    Arxiv version (pdf)

  40. M.Goodrich, M. Mitzenmacher, O. Ohrimenko, R. Tamassia.
    Oblivious RAM Simulation with Efficient Worst-Case Access Overhead.
    To appear in CCSW (ACM Cloud Computing Security Workshop).

  41. M. Dietzfelbinger, M. Mitzenmacher, M. Rink.
    Cuckoo Hashing with Pages
    To appear in ESA.
    Arxiv version (pdf)

  42. M. Goodrich, M. Mitzenmacher.
    Mapreduce Parallel Cuckoo Hashing and Oblivious RAM Simulations
    To appear in ICALP.
    Arxiv version (pdf)

  43. M. Goodrich, M. Mitzenmacher.
    Brief announcement: large-scale multimaps
    SPAA 2011.
    Improved by Multimaps paper listed above.

  44. J.K. Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher, and J. Barros.
    Network Coding Meets TCP: Theory and Implementation.
    In Proceedings of the IEEE.

  45. M. Iliofotou, H. Kim, M. Faloutsos, M. Mitzenmacher, P. Pappu, and G. Varghese.
    Graption: A graph-based P2P traffic classification framework for the internet backbone.
    In Computer Networks.

  46. A. Frieze, P. Melsted, and M. Mitzenmacher.
    An Analysis of Random-Walk Cuckoo Hashing.
    In SIAM Journal of Computing.

  47. I. Kash, M. Mitzenmacher, J. Thaler, J. Ullman.
    On the Zero-Error Capacity Threshold for Deletion Channels.
    Appears in the ITA 2011 workshop.
    Arxiv version (pdf)

  48. J. Byers, B. Heeringa, M. Mitzenmacher, and G. Zervas.
    Heapable Sequences and Subsequences.
    ANALCO 2011.
    Arxiv version (pdf)

    2010

  49. M. Mitzenmacher.
    Codes -- Protecting Data Against Loss and Errors.
    Chapter in Algorithms Unplugged.

  50. M. Mitzenmacher.
    An introduction to human-guided search.
    ACM Crossroads.

  51. S. Schechter, C. Herley, and M. Mitzenmacher.
    Popularity is Everything: A New Approach to Protecting Passwords from Statistical-Guessing Attacks
    To appear in HOTSEC 2010.
    Conference version (pdf)

  52. G. Cormode, M. Mitzenmacher, and J. Thaler.
    Streaming Graph Computations with a Helpful Advisor.
    To appear in ESA 2010.

  53. A. Kirsch and M. Mitzenmacher.
    The Power of One Move: Hashing Schemes for Hardware.
    To appear in IEEE/ACM Transactions on Networking.

  54. Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink.
    Tight Thresholds for Cuckoo Hashing via XORSAT
    Arxiv version (pdf)
    To appear in ICALP 2010.

  55. Raissa M. D' Souza and Michael Mitzenmacher
    Local cluster aggregation models of explosive percolation
    To appear in Physical Review Letters.
    PRL link

  56. A. Kalai, M. Mitzenmacher, and M. Sudan.
    Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities
    Draft version (pdf)
    To appear at ISIT 2010.

  57. H. Finuance and M. Mitzenmacher.
    An impproved analysis of the lossy difference aggregator.
    Submitted version (pdf)
    To appear in Computer Communications Review.

  58. J. Byers, M. Mitzenmacher, and G. Zervas.
    Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank
    Extended version from arxiv (pdf)
    To appear in EC (Electronic Commerce) 2010.

  59. T. Lam, M. Mitzenmacher, and G. Varghese.
    Carousel: Scalable Logging for Intrusion Prevention Systems.
    Conference version (pdf)
    To appear in NSDI 2010.

  60. V. Braverman, K. Chung, Z. Liu, M. Mitzenmacher, and R. Ostrovsky.
    AMS Without 4-Wise Independence on Product Domains.
    To appear in STACS 2010.
    Conference version (pdf)
    This paper is the result of a merge. For historical reasons, and for a slightly different proof, please see:
    Testing k-Wise Independence over Streaming Data
    K. Chung, Z. Liu, and M. Mitzenmacher.
    Early version (pdf)

  61. J. Byers, M. Mitzenmacher, and G. Zervas.
    Adaptive Weighing Designs for Keyword Value Computation
    To appear in WSDM 2010.

  62. F. Chierichetti, H. Finucane, Z. Liu, and M. Mitzenmacher
    Designing Floating Codes for Expected Performance
    To appear in IEEE Transactions on Information Theory.

  63. Z. Liu and M. Mitzenmacher
    Codes for Deletion and Insertion Channels with Segmented Errors
    Submitted version (ps)
    To appear in IEEE Transactions on Information Theory.

    2009

  64. A. Z. Broder, A. Kirsch, R. Kumar, M. Mitzenmacher, E. Upfal, and S. Vassilvitskii.
    The Hiring Problem and Lake Wobegon Strategies.
    SIAM Journal on Computing, 39(4).

  65. A. Kirsch, M. Mitzenmacher, and U. Wieder.
    More Robust Hashing: Cuckoo Hashing with a Stash.
    SIAM Journal on Computing, 39(4).

  66. D. Alcantara, A. Sharf, F. Abbasinejad, S. Sengupta, M. Mitzenmacher, J. Owens, and N. Amenta.
    Real-Time Parallel Hashing on the GPU
    SIGGRAPH Asia 2009.

  67. M. Iliofotou, M. Faloutsos, and M. Mitzenmacher.
    Exploiting Dynamicity in Graph-based Traffic Analysis: Techniques and Applications
    ACM Co-NEXT 2009.

  68. A. Frieze, P. Melsted, and M. Mitzenmacher.
    An Analysis of Random-Walk Cuckoo Hashing.
    APPROX/RANDOM 2009.

  69. M. Mitzenmacher.
    Some Open Questions Related to Cuckoo Hashing.
    ESA 2009.
    Conference version (pdf)

  70. H. Finucane and M. Mitzenmacher.
    Worst-Case and Average-Case Floating Codes for Flash Memory
    Harvard Computer Science Technical Report TR-04-09.
    TR (pdf)

  71. M. Mitzenmacher
    Bloom Filters
    Entry for Encyclopedia of Database Systems. (Springer)

  72. A. Kirsch, M. Mitzenmacher, and G. Varghese
    Hash-Based Techniques for High-Speed Packet Processing
    Submitted version (pdf)
    Chapter for a DIMACS book.

  73. M. Mitzenmacher
    New Results and Open Problem for Channels with Synchronization
    Probability Surveys

  74. G. Klau, N. Lesh, J. Marks, and M. Mitzenmacher.
    Human-guided search.
    Journal version (pdf)
    Journal of Heuristics (online vesion) 2009.

  75. F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan.
    On Compressing Social Networks.
    Conference version (pdf)
    To appear in KDD 2009.

  76. A. Kirsch, M. Mitzenmacher, A. Pietracaprina, G. Pucci, E. Upfal, and F. Vandin.
    An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
    Conference version (pdf)
    To appear in PODS 2009.

  77. S. Lumetta and M. Mitzenmacher
    Using the Power of Two Choics to Improve Bloom Filters
    Journal version (pdf)
    Internet Mathematics, vol 4 number 1, p. 17-33, 2009.

  78. J.K. Sundararajan, D. Shah, M. Medard, M. Mitzenmacher, and J. Barros.
    Network coding meets TCP.
    Arxiv link
    To appear in INFOCOMM 2009.

  79. Jacomo Corbo, Shaili Jain, Michael Mitzenmacher, and David Parkes.
    An Economically Principled Generative Model of AS Graph Connectivity.
    To appear in INFOCOMM 2009 (Mini-conference).

  80. Marios Iliofotou, Hyun-chul Kim, Michalis Faloutsos, Michael Mitzenmacher, Prashanth Pappu, and George Varghese.
    Graph-based P2P Traffic Classification at the Internet Backbone
    Workshop version (pdf)
    Global Internet Symposium.

    2008

  81. H. Finucane, Z. Liu, and M. Mitzenmacher.
    Designing Floating Codes for Expected Performance
    Conference version (pdf)
    Allerton 2008.

  82. A. Kirsch and M. Mitzenmacher.
    On the Performance of Multiple Choice Hash Tables with Moves on Deletes and Inserts
    Conference version (pdf)
    Allerton 2008.

  83. M. Mitzenmacher
    A survey of results for deletion channels and related synchronization channels.
    Draft version (pdf)
    To be submitted. Summary appeared in SWAT 2008.

  84. A. Kirsch, M. Mitzenmacher, and U. Wieder.
    More Robust Hashing: Cuckoo Hashing with a Stash.
    Submitted journal version (pdf)
    European Symposium on Algorithms (conference version).

  85. A. Kirsch and M. Mitzenmacher
    Less Hashing, Same Performance: Building A Better Bloom Filter
    Journal version (pdf)
    Random Structures and Algorithms.

  86. M. Johnson and K. Ramchandran and M. Mitzenmacher
    Distributed Beamforming with Binary Signaling.
    Submitted version (pdf)
    Accepted to ISIT 2008.

  87. A. Kirsch and M. Mitzenmacher.
    The Power of One Move: Hashing Schemes for Hardware.
    Submitted version (pdf)
    Accepted to INFOCOM 2008.

  88. A. Kirsch and M. Mitzenmacher
    Simple Summaries for Hashing with Choices
    IEEE/ACM Transactions on Networking, volume 16, number 1, pages 218-231, February 2008.
    Journal version (pdf)

  89. A. Z. Broder, A. Kirsch, R. Kumar, M. Mitzenmacher, E. Upfal, and S. Vassilvitskii.
    The Hiring Problem and Lake Wobegon Strategies.
    Conference version (pdf)
    Accepted to SODA 2008.

  90. M. Mitzenmacher and S. Vadhan.
    Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream
    Extended version of SODA paper (pdf)
    Accepted to SODA 2008.

  91. Thomas Holenstein and Michael Mitzenmacher and Rina Panigrahy and Udi Wieder
    Trace reconstruction with constant deletion probability and related results
    Conference paper (pdf)
    Accepted to SODA 2008.

  92. M. Mitzenmacher
    Capacity Bounds for Sticky Channels
    IEEE Trans. on Information Theory, volume 54, issue 1, pages 72-77, January 2008.
    Journal version (pdf)

    2007

  93. Marios Iliofotou, Prashanth Pappu, George Varghese, Michalis Faloutsos, Michael Mitzenmacher, Sumeet Singh.
    Network Monitoring Using Traffic Dispersion Graphs (TDGs)
    Proceedings of the Internet Measurement Conference 2007.
    Conference version (pdf)

  94. Sailesh Kumar, Jonathan Turner, Patrick Crowley, Michael Mitzenmacher.
    HEXA: Compact Data Structures for Faster Packet Processing.
    Proceedings of IEEE ICNP'07.
    Conference version (pdf)

  95. A. Kirsch and M. Mitzenmacher
    Using a Queue to De-amortize Cuckoo Hashing in Hardware
    Proceedings of the 45th Annual Allerton Conference on Communication, Control, and Computing, 2007.
    Conference version (pdf)

  96. E. Drinea and M. Mitzenmacher
    Improved lower bounds for the capacity of i.i.d. deletion and duplication channels.
    IEEE Transactions on Information Theory, vol 53, Issue 8, pp. 2693-2714, 2007.
    Journal version (pdf)

  97. Jacomo Corbo, Shaili Jain, Michael Mitzenmacher, and David Parkes.
    An Economically Principled Generative Model of AS Graph Connectivity.
    Joint Workshop on The Economics of Networked Systems and Incentive-Based Computing
    Workshop version (pdf)

  98. J. Ledlie, P. Pietzuch, M. Mitzenmacher, and M. Seltzer.
    Wired Geometric Routing.
    Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS), 2007.
    Also Harvard University Computer Science Technical Report TR-19-06, November 2006.
    Conference version (pdf)
    Technical report version (ps)

  99. S. Diggavi and M. Mitzenmacher and H. Pfister
    Capacity Upper Bounds for Deletion Channels
    Proceedings of the 2007 Int'l Symposium on Information Theory (ISIT), 2007, pp. 1716-1720.
    Conference Version (pdf)

  100. Z. Liu and M. Mitzenmacher
    Codes for Deletion and Insertion Channels with Segmented Errors
    Proceedings of the 2007 Int'l Symposium on Information Theory (ISIT), 2007, pp. 846-850.
    Conference Version (pdf)

    2006

  101. J. Feigenbaum and M. Mitzenmacher
    Towards a theory of networked computation
    ACM SIGACT News, Issue 4, pp. 22-26, December 2006.
    Executive Summary (pdf)
    This is the executive summary of a fuller report which can be found at the ToNC home page.

  102. M. Mitzenmacher
    Polynomial Time Low-Density Parity-Check Codes with Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q
    Journal version of Verification Codes for Deletion Channels listed below.
    IEEE Transactions on Information Theory, vol 52, Issue 12, pp. 5496-5501, 2006.
    Journal version (pdf)

  103. M. Mitzenmacher.
    Editorial: The Future of Power Law Research
    Journal version (pdf)
    Internet Mathematics, vol. 2. no. 4, pp. 525-534, 2006.

  104. F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese.
    Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment
    Conference version (pdf)
    To appear in Allerton 2006.
    This will probably be folded into the journal version of the ESA paper below.

  105. F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese.
    Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines
    Conference version (pdf)
    To appear in SIGCOMM 2006.
    A journal version will be submitted soon.

  106. F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese.
    An Improved Construction for Counting Bloom Filters.
    Conference version (pdf)
    To appear in ESA 2006.
    A journal version will be submitted soon.

  107. A. Kirsch and M. Mitzenmacher
    Less Hashing, Same Performance: Building A Better Bloom Filter
    Conference version (pdf)
    To appear in ESA 2006.
    Technical Report version (pdf)
    A journal version will be submitted soon.

  108. E. Nikolova and J. Kelner and M. Brand and M. Mitzenmacher
    Stochastic Shortest Paths via Quasi-Convex Maximization
    Conference version (pdf)
    To appear in ESA 2006.

  109. E. Drinea and M. Mitzenmacher
    On Lower Bounds for the Capacity of Deletion Channels
    IEEE Transactions on Information Theory, vol 52, Issue 10, pp. 4648-4657, 2006.
    Journal version (pdf)

  110. E. Drinea and M. Mitzenmacher
    A simple lower bound for the capacity of the deletion channel.
    IEEE Transactions on Information Theory, vol 52, Issue 10, pp. 4657-4660, 2006.
    Journal version (pdf)

  111. M. Mitzenmacher
    On the Theory and Practice of Data Recovery with Multiple Versions
    Preprint version (ps)
    This is being revised and will appear at ISIT.
    Replication and error-correction are standard mechanisms to cope with data corruption. We consider how these two approaches can be combined for preservation of digital data. We provide an information-theoretic model and theoretical framework, and discuss how recent breakthroughs such as the development of Raptor codes may play a part in future practical systems.

  112. P. Pietzuch, J. Ledlie, M. Mitzenmacher, M. Seltzer.
    Network-Aware Overlays with Network Coordinates
    Preprint version (pdf)
    To appear in the International Workshop on Dynamic Distributed Systems (held in conjunction with ICDCS).

  113. J. Byers, Gu-In Kwon, M. Luby, and M. Mitzenmacher.
    Fine-Grained Layered Multicast with STAIR
    IEEE/ACM Transactions on Networking, 14:1, pp. 81-93, February 2006.
    Journal version (pdf)

  114. A. Kirsch and M. Mitzenmacher
    Distance-Sensitive Bloom Filters
    Conference version (pdf)
    Appeared in ALENEX 06.
    We introduce and consider the notion of an "approximate Bloom filter", that allows approximate instead of exact matches under a distance metric.

  115. N. Lesh and M. Mitzenmacher
    BubbleSearch: A Simple Heuristic for Improving Priority-Based Greedy Algorithms
    (Information Processing Letters, Volume 97, Issue 4, Pages 161-169, 28 February 2006.
    Journal version (pdf)

    2005

  116. A. Kirsch and M. Mitzenmacher
    Simple Summaries for Multiple Choice Hashing
    Allerton conference version (ps)
    This has been revised and submitted as a journal version.

  117. S. Mitra, S. Lumetta, M. Mitzenmacher, and N. Patil.
    X-Tolerant Test Response Compaction
    IEEE Design and Test of Computers, vol. 22, no. 6, pp. 566-574, Nov/Dec 2005.
    Journal version (pdf)

  118. N. Lesh, J. Marks, A. McMahon, and M. Mitzenmacher.
    New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing
    Journal of Experimental Algorithmics (JEA).
    Journal version (ps)
    Vol. 10, Article No. 1.2, 2005.

  119. Y. Cheng and M. Mitzenmacher.
    Privacy Preserving Keyword Searches on Remote Encrypted Data
    Applied Cryptography and Network Security 2005.
    Extended version (pdf)

  120. J. Cheng and M. Mitzenmacher.
    The Markov Expert for Finding Episodes in Time Series
    (Note: J. Cheng was a Harvard Master's student; this work was done as a course project.)
    Accepted (1 page poster) to the 2005 Data Compression Conference.
    Extended version (pdf)

  121. M. Chimani, N. Lesh, M. Mitzenmacher, and C. Sidner.
    A case study in large-scale interactive optimization.
    International Conference on Artificial Intelligence and Applications.
    Conference version (pdf)

  122. A. Broder and M. Mitzenmacher
    Multi-dimensional balanced allocations.
    SODA 2005 (short paper), pp. 195-196.
    Conference version (pdf)

  123. M. Luby and M. Mitzenmacher
    Verification Codes
    IEEE Trans. on Inf. Theory, vol. 50, no. 1, pp. 120-127, January 2005.
    Journal version (pdf)

  124. A. Broder and M. Mitzenmacher.
    Network Applications of Bloom Filters: A Survey.
    Internet Mathematics, vol. 1. no. 4, pp. 485-509, 2005.
    Journal version (pdf) ; recently improved.

    2004

  125. M. Mitzenmacher
    Dynamic Models for File Sizes and Double Pareto Distributions
    Internet Mathematics, vol 1, No. 3, pp. 305-334, 2004.
    Journal version (pdf)

  126. M. Mitzenmacher
    Digital Fountains: A Survey and Look Forward.
    To appaear at the 2004 Information Theory Workshop.
    Conference version (pdf)
    I am considering extending this survey for Internet Mathematics. Please feel free to send comments and suggestions, particularly if there is other work I should be referring to in the survey.

  127. J. Byers, J. Considine, M. Mitzenmacher, and S. Rost
    Informed Content Delivery Across Adaptive Overlay Networks
    IEEE/ACM Transactions on Networking, vol. 12, no. 5, pp. 767-780, October 2004.
    Journal version (pdf)

  128. M. Mitzenmacher
    A Brief History of Generative Models for Power Law and Lognormal Distributions
    Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
    Journal version (pdf)
    I am also leaving up this slightly outdated submission version. The editors asked me to leave out a few things in the journal -- including excerpts from the back-and-forth discussion between Mandelbrot and Simon -- that might be fun for some people to read.
    Submission version (ps)

  129. E. Drinea and M. Mitzenmacher
    Improved Lower Bounds for I.I.D. Deletion Channels
    Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and Computing, pp. ???-???, 2004.
    Abstract         Conf. version (pdf)

  130. S. Mitra, S. Lumetta, and M. Mitzenmacher.
    X-Tolerant Signature Analysis
    To appear at the 2004 International Testing Conference.
    Journal version appears above as X-Tolerant Test Response Compaction.
    Conf. version (ps)


  131. B. Conrad and M. Mitzenmacher
    Power Laws for Monkeys Typing Randomly: The Case of Unequal Probabilities
    IEEE Transactions on Information Theory, 50:7, pp. 1403-1414, 2004.
    Abstract         Journal version (pdf)

  132. M. Mitzenmacher.
    On the Hardness of Finding Multiple Preset Dictionaries
    IEEE Transactions on Information Theory, 50:7, pp. 1536-1539, 2004.
    Abstract         Journal version (pdf)

  133. N. Lesh, A. McMahon, J. Marks, and M. Mitzenmacher.
    An Exhaustive Approach to 2D Strip Packing.
    Information Processing Letters, 90:1, pp.7-14, 2004.
    Abstract         Journal version (pdf)

  134. M. Mitzenmacher, R. Oliveira, and J. Spencer.
    A Scaling Result for Explosive Processes.
    Electronic Journal of Combinatorics, vol 11(1), R31, 2004.
    Abstract         Journal version (pdf)

  135. E. Drinea and M. Mitzenmacher
    Improved Lower Bounds on the Capacity of Deletion Channels Accepted to ISIT, June 2004.
    Conf. version (1 page, ps)         Tech. report (ps)
    Journal version appears above.

  136. J. Byers, J. Considine, and M. Mitzenmacher.
    Geometric Generalizations of the Power of Two Choices.
    Accepted to the 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2004.
    Abstract         Conf. version (ps)

  137. N. Lesh and M. Mitzenmacher.
    Interactive Data Summarization: An Example Application.
    Accepted to the Workshop on Advanced Visual Interfaces, 2004.
    Abstract         Conf. version (pdf)

    2003

  138. A. Broder, M. Charikar, and M. Mitzenmacher
    A Derandomization Using Min-Wise Independent Permutations
    Journal of Discrete Algorithms, vol 1:1, pp. 11-20, 2003.
    Abstract         Journal version (ps) -- just the journal proofs, not final

  139. M. Mitzenmacher and B. Tworetzky
    (Note: Brent Tworetzky was a Harvard undergraduate; this work was done as his senior thesis.)
    New Models and Methods for File Size Distributions
    Proceedings of the 41st Annual Allerton Conference on Communication, Control, and Computing, pp. 603-612, 2003.
    Abstract         Conf. version (pdf)

  140. N. Lesh, A. McMahon, J. Marks, and M. Mitzenmacher.
    New Exhaustive and Interactive Approaches to 2D Rectangular Strip Packing
    IJCAI Workshop on Stochastic Search, 2003.
    Abstract         Technical report version (pdf)

  141. A. Kavcic, X. Ma, and M. Mitzenmacher
    Capacity Approaching Signal Constellations for Channels with Memory
    IEEE Transactions on Information Theory, 49:7, pp. 1636-1652, 2003.
    Abstract         Journal version (pdf)

  142. A. Kavcic, X. Ma, and M. Mitzenmacher
    The Power Spectra of Good Codes for Partial Response Channels
    Proceedings of the 2003 Int'l Symposium on Information Theory (ISIT), 2003, p. 45.
    Abstract         Conf. version (pdf)

  143. J. Chen, M. Mitzenmacher, C. Ng, N. Varnica
    Concatenated Codes for Deletion Channels
    Proceedings of the 2003 Int'l Symposium on Information Theory (ISIT), 2003, p. 218.
    Abstract         Conf. version (pdf)         Tech. report (ps)

  144. M. Mitzenmacher
    Verification Codes for Deletion Channels
    Proceedings of the 2003 Int'l Symposium on Information Theory (ISIT), 2003, p. 217.
    Abstract         Conf. version (ps)

  145. F. Behr, V. Fossum, M. Mitzenmacher, and D. Xiao
    (Note: F. Behr, V. Fossum, and D. Xiao were Harvard undergraduates; this work was done as a course project.)
    Estimating and Comparing Entropies Across Written Natural Languages Using PPM Compression
    Proceedings of the 2003 Data Compression Conference, p. 416.
    Abstract         1 page Conf. version (pdf)         Technical Report (ps)

  146. N. Lesh, M. Mitzenmacher, and S. Whitesides
    A Complete and Effective Move Set for Simplified Protein Folding
    Proceedings of the 7th Annual Int'l Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp. 188-195.
    Abstract         Conf. version (pdf).

  147. J. Byers, J. Considine, and M. Mitzenmacher
    Simple Load Balancing for Distributed Hash Tables
    Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2003.
    Abstract         Conf. version (ps)

    2002

  148. E. Drinea, A. Frieze, and M. Mitzenmacher
    Balls and Bins Models with Feedback
    Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 308-315, 2002.
    Abstract         Conference version (pdf)

  149. M. Mitzenmacher
    Unbiasing Random Bits
    Dr. Dobbs Journal, No. 335, pp. 101-104, April 2002.
    Article

  150. M. Mitzenmacher
    Good Hash Tables & Multiple Hash Functions
    Dr. Dobbs Journal, No. 336, pp. 28-32, May 2002.
    Article

  151. C. Kenyon and M. Mitzenmacher
    Linear Waste of Best Fit Bin Packing on Skewed Distributions
    Random Structures and Algorithms, 20(3), pp. 441-464, 2002.
    Abstract         Journal version (pdf)

  152. M. Luby and M. Mitzenmacher
    Verification Codes
    Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 38-47, 2002.
    Journal version listed above

  153. A. Broder and M. Mitzenmacher
    Network Applications of Bloom Filters: A Survey
    Journal version listed above

  154. A. Goel and M. Mitzenmacher
    Exact Sampling of TCP Window States
    Proceedings of IEEE INFOCOM 2002, pp. 259-265, 2002.
    Abstract         Conference version (pdf)

  155. A. Broder and M. Mitzenmacher
    Optimal Plans for Aggregation
    Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, pp. 144-152, 2002.
    Abstract         Conference version (pdf)

  156. J. Byers, M. Luby, and M. Mitzenmacher
    A Digital Fountain Approach to the Reliable Distribution of Bulk Data
    IEEE Journal on Selected Areas in Communications, 20:8, pp. 1528-1540, October 2002.
    Abstract         Journal version (pdf)

  157. G. Klau, N. Lesh, J. Marks, M. Mitzenmacher, and G. Schafer.
    The HuGS Platform: A Toolkit for Interactive Optimization
    Proceedings of the Workshop on Advanced Visual Interfaces, pp. 324-330, 2002.
    Abstract         Conference version (pdf)

  158. G. Klau, N. Lesh, J. Marks, and M. Mitzenmacher.
    Human-Guided Tabu Search
    Proceedings of the 18th National Conference on Artificial Intelligence, pp. 41-47, 2002.
    Abstract         Conference version (pdf)

  159. J. Byers, G. Horn, M. Luby, M. Mitzenmacher, and W. Shaver.
    FLID/DL: Congestion Control for Layered Multicast
    IEEE Journal on Selected Areas in Communications, 20:8, pp. 1558-1570, October 2002.
    Abstract         Journal version (pdf)

  160. J. Byers, J. Considine, M. Mitzenmacher, and S. Rost
    Informed Content Delivery Across Adaptive Overlay Networks
    Proceedings of ACM SIGCOMM '02, available as Computer Communications Review, vol. 32:4, pp. 47-60, 2002.
    Abstract         Conference version (pdf)

  161. M. Mitzenmacher and B. Voecking
    The Asymptotics of Selecting the Shortest of Two, Improved
    Extended version appears as a chapter in Analytic Methods in Applied Probability: In Memory of Fridrih Karpelevich, American Mathematical Society, pp. 165-176, 2002.
    Abstract         Technical report version (ps)

  162. M. Mitzenmacher
    Compressed Bloom Filters
    IEEE/ACM Transactions on Networks, 10:5, pp. 613-620, October 2002.
    Abstract         Journal version (pdf)

  163. M. Mitzenmacher, B. Prabhakar, and D. Shah.
    Balls and Bins with Memory
    Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 799-808, 2002.
    Abstract         Conference version (pdf)

    2001

  164. E. Drinea, M. Enachescu, and M. Mitzenmacher
    Variations on Random Graph Models for the Web
    Harvard Computer Science Technical Report TR-06-1.
    Conference version (pdf)

  165. M. Mitzenmacher and S. Owen
    (Note: Sean Owen was a Harvard undergraduate; this work was done as his senior thesis.)
    Estimating Resemblance of MIDI Documents
    Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments, available as Lecture Notes in Computer Science 2153, pp. 78-90, 2001.
    Abstract         Conference version (pdf)

  166. J. Boyan and M. Mitzenmacher
    Improved Results for Route Planning in Stochastic Transportation Networks
    Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 895-902, 2001.
    Abstract         Conference version (pdf)

  167. J. Byers, M. Luby, and M. Mitzenmacher
    Fine-Grained Layered Multicast
    Proceedings of IEEE INFOCOM 2001, pp. 1143-1151, 2001.
    Abstract         Conference version (ps)

  168. A. Broder and M. Mitzenmacher
    Using Multiple Hash Functions to Improve IP Lookups
    Proceedings of IEEE INFOCOM 2001, pp. 1454-1463, 2001.
    Abstract         Conference version (ps)

  169. M. Mitzenmacher
    Analyses of Load Stealing Models Using Differential Equations
    Theory of Computing Systems, 34:1, pp. 77-98, January 2001.
    Abstract         Journal version (pdf)

  170. M. Mitzenmacher
    Challenging Students with Creative Assignments
    SIGACT News, 32(1):70-73, 2001.
    Newsletter version (pdf)

  171. M. Mitzenmacher
    An Experimental Assignment on Random Processes
    SIGACT News, 32(1):74-78, 2001.
    Newsletter version (pdf)

  172. M. Mitzenmacher
    On the Hardness of Finding Multiple Preset Dictionaries
    Journal version listed above
    Proceedings of the 2001 Data Compression Conference, pp. 411-418, 2001.

  173. M. Adler and M. Mitzenmacher
    Toward Compressing Web Graphs
    Proceedings of the 2001 Data Compression Conference, pp. 203-212, 2001.
    Abstract         Conference version (pdf)

  174. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman
    Efficient Erasure Correcting Codes
    IEEE Transactions on Information Theory, 47(2), pp 569-584, 2001.
    Abstract         Journal version (pdf)

  175. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman
    Improved Low-Density Parity-Check Codes Using Irregular Graphs
    IEEE Transactions on Information Theory, 47(2), pp 585-598, 2001.
    Abstract         Journal version (pdf)

  176. S. Albers, M. Charikar, and M. Mitzenmacher
    Delayed Information and Action in On-Line Algorithms
    Information and Computation, 170(2), pp. 135-152, 2001.
    Abstract         Journal version (pdf)

  177. A. Broder and M. Mitzenmacher
    Completeness and Robustness Properties of Min-Wise Independent Permutations
    Random Structures and Algorithms, 18(1), pp. 18-30, January 2001.
    Abstract         Journal version (pdf)

  178. E. Gafni and M. Mitzenmacher
    Analysis of Timing Based Mutual Exclusion with Random Times
    SIAM Journal on Computing, 31:3, pp. 816-837, 2001.
    Abstract         Journal version (pdf)

  179. M. Mitzenmacher, A. Richa, and R. Sitaraman
    The Power of Two Random Choices: A Survey of Techniques and Results
    Book chapter, in Handbook of Randomized Computing: volume 1, edited by P. Pardalos, S. Rajasekaran, and J. Rolim, pp. 255-312.
    Draft version (pdf)

  180. M. Mitzenmacher
    A Brief History of Lognormal and Power Law Distributions
    Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing}, pp. 182-191, 2001.
    Journal version listed above

  181. A. Kavcic, X. Ma, M. Mitzenmacher, and N. Varnica.
    Capacity Approaching Signal Constellations for Channels with Memory
    Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing, pp. 311-320, 2001.
    Abstract         Conference version (pdf)

  182. A. Kavcic, B. Marcus, M. Mitzenmacher, and B. Wilson.
    Deriving Performance Bounds for ISI Channels Using Gallager Codes
    Proceedings of the 2001 Int'l Symposium on Information Theory, p. 345, 2001.
    Abstract         Conference version (pdf)

  183. M. Mitzenmacher
    Compressed Bloom Filters
    Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing, pp. 144-150, 2001.
    Journal version listed above

  184. M. Mitzenmacher and R. Rajaraman
    Towards More Complete Models of TCP Throughput
    Journal of Supercomputing, 20(2), pp. 137-160, September 2001.
    Abstract         Journal version (pdf)

  185. M. Mitzenmacher
    The Power of Two Choices in Randomized Load Balancing
    IEEE Transactions on Parallel and Distributed Computing, 12(10), pp. 1094-1104, 2001.
    Abstract         Journal version (pdf)

  186. M. Dyer, L. Goldberg, C. Greenhill, M. Jerrum, and M. Mitzenmacher
    An Extension of Path Coupling and Its Application to the Glauber Dynamics for Path Coupling
    SIAM Journal on Computing, 30(6), pp. 1962-1975, 2001.
    Abstract         Journal version (pdf)

    2000

  187. A. Broder, R. Krauthgamer, and M. Mitzenmacher
    Improved Classification via Connectivity Information
    Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 576-585, 2000.
    Abstract         Conference version (pdf)

  188. M. Dyer, L. Goldberg, C. Greenhill, M. Jerrum, and M. Mitzenmacher
    An Extension of Path Coupling and Its Application to the Glauber Dynamics for Path Coupling
    Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 616-623, 2000.
    Journal version listed above

  189. M. Mitzenmacher
    How Useful is Old Information?
    IEEE Transactions on Parallel and Distributed Systems, 11:1, pp. 6-20, January 2000.
    Abstract         Journal version (pdf)

  190. A. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher.
    Min-Wise Independent Permutations
    Journal of Computer and System Sciences, 60(3), pp. 630-659, 2000.
    Abstract         Journal version (pdf)

  191. M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork
    On Near-Uniform URL Sampling
    Proceedings of the Ninth International World Wide Web Conference, pp. 295-308, 2000.
    Journal version under review.

  192. S. Albers and M. Mitzenmacher
    Average Case Analyses of First Fit and Random Fit Bin Packing
    Random Structures and Algorithms, 16(3), pp. 240-259, 2000.
    Abstract         Journal version (pdf)

  193. C. Kenyon and M. Mitzenmacher
    Linear Waste of Best Fit Bin Packing on Skewed Distributions
    Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 582-589, 2000.
    Journal version listed above

  194. J. Byers, M. Frumin, G. Horn, M. Luby, M. Mitzenmacher, A. Roetter, and W. Shaver.
    FLID/DL: Congestion Control for Layered Multicast
    Proceedings of the 2nd International Workshop on Networked Group Communication (NGC 2000), pp. 71-81, 2000.
    Journal version listed above

    1999

  195. A. Broder, M. Mitzenmacher, and L. Moll.
    Unscrambling Address Lines
    Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 870-871, 1999.
    Abstract         Conference version (pdf)

  196. J. Byers, M. Luby, and M. Mitzenmacher
    Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads
    Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '99), pp. 275-284, 1999.
    Abstract         Conference version (pdf)

  197. E. Gafni and M. Mitzenmacher
    Analysis of Timing Based Mutual Exclusion with Random Times
    Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 13-21, 1999.
    Journal version listed above.

  198. A. Broder and M. Mitzenmacher
    Completeness and Robustness Properties of Min-Wise Independent Permutations
    Proceedings of Random '99, available as Lecture Notes in Computer Science 1671, pp. 1-10, 1999.
    Journal version listed above.

  199. M. Mitzenmacher
    Studying Balanced Allocations with Differential Equations
    Combinatorics, Probability, and Computing, vol. 8, pp. 473-482, 1999.
    Abstract         Journal version (pdf)

  200. M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork
    Measuring Index Quality Using Random Walks on the Web
    Proceedings of the Eighth International World Wide Web Conference, pp. 213-225, Elsevier Science, 1999.
    Journal version under review.

  201. M. Mitzenmacher and B. Voecking
    The Asymptotics of Selecting the Shortest of Two, Improved
    Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, pp. 326-327, 1999.
    Extended version listed above as a book chapter.

  202. M. Mitzenmacher
    On the Analysis of Randomized Load Balancing Schemes
    Theory of Computing Systems, 32(3):361-386, June 1999.
    Abstract         Journal version (pdf)


    1998

  203. S. Albers and M. Mitzenmacher
    Average Case Analyses of First Fit and Random Fit Bin Packing
    Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 290-299, 1998.
    Journal version listed above.

  204. M. Luby, M. Mitzenmacher, and A. Shokrollahi
    Analysis of Random Processes via And-Or Tree Evaluation
    Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 364-373, 1998.
    Abstract         Conference version (pdf)

  205. S. Albers and M. Mitzenmacher
    Average Case Analyses of List Update Algorithms, with Applications to Data Compression
    Algorithmica, 21:3, pp. 312-329, 1998.
    Abstract         Journal version (pdf)

  206. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman
    Analysis of Low Density Codes and Improved Designs Using Irregular Graphs
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 249-258, May 23-26, 1998.
    Journal version listed above, under title: Improved Low-Density Parity-Check Codes Using Irregular Graphs

  207. A. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher
    Min-Wise Independent Permutations
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 327-336, May 23-26, 1998.
    Journal version listed above.

  208. R. Cole, B. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, K. Schroeder, R. Sitaraman, and B. Voecking
    Load Adaptive Routing on Butterfly Networks
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 378-388, May 23-26, 1998.
    Abstract         Conference version (pdf)

  209. S. Albers, M. Charikar, and M. Mitzenmacher
    Delayed Information and Action in On-Line Algorithms
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 378-388, May 23-26, 1998.
    Journal version listed above.

  210. M. Mitzenmacher
    Analyses of Load Stealing Models Using Differential Equations
    Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 212-221, 1998.
    Journal version listed above.

  211. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman
    Improved Low Density Parity Check Codes Using Irregular Graphs and Belief Propagation
    Proceedings of the 1998 Int'l Symposium on Information Theory (ISIT), p. 45, 1998.
    Journal version listed above, under title: Improved Low-Density Parity-Check Codes Using Irregular Graphs

  212. J. Byers, M. Luby, M. Mitzenmacher, and A. Rege
    A Digital Fountain Approach to the Reliable Distribution of Bulk Data
    Proceedings of ACM SIGCOMM '98, available as Computer Communications Review, vol. 28:4, pp. 56-67, 1998.
    Journal version listed above.

  213. M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen
    Parallel Randomized Load Balancing
    Random Structures and Algorithms, vol. 13:2, pp. 159-188, September 1998.
    Abstract         Journal version (pdf)

  214. M. Mitzenmacher
    A Note on Low Density Parity Check Codes for Erasures and Errors
    SRC Technical Note 1998-017
    Abstract         Technical Note (pdf)

  215. A. Broder, M. Charikar, and M. Mitzenmacher
    A Derandomization Using Min-Wise Independent Permutations
    Proceedings of Random '98, available as Lecture Notes in Computer Science 1518, pp. 15-24, October 1998.
    Journal version listed above.

  216. R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. Sitaraman, and E. Upfal
    On Balls and Bins with Deletions
    Proceedings of Random '98, available as Lecture Notes in Computer Science 1518, pp. 145-158, October 1998.
    Abstract         Conference version (pdf)

    1997

  217. S. Albers and M. Mitzenmacher
    Revisiting the COUNTER Algorithms for List Update
    Information Processing Letters, 64:155-160, 1997.
    Abstract         Journal version (pdf)

  218. M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann
    Practical Loss-Resilient Codes
    Proceedings of the 29th ACM Symposium on the Theory of Computing, pp. 150-159, 1997.
    Journal version listed above, under title: Efficient Erasure Correcting Codes.

  219. M. Mitzenmacher
    Tight Threshholds for the Pure Literal Rule
    SRC Technical Note 1997-011
    Abstract         Technical Note (pdf)

  220. M. Mitzenmacher
    How Useful is Old Information?
    Proceedings of the 16th ACM Symposium on Principles of Distributed Computing, pp. 83-91, 1997.
    Journal version listed above.

  221. M. Mitzenmacher
    Constant Time per Edge is Optimal in Rooted Tree Networks
    Distributed Computing, vol. 10:4, pp. 189-197, 1997.
    Abstract         Journal version (pdf)

  222. M. Mitzenmacher
    On the Analysis of Randomized Load Balancing Schemes
    Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures, pp. 292-301, 1997.
    Journal version listed above.


    1996

  223. S. Albers and M. Mitzenmacher
    Average Case Analyses of List Update Algorithms, with Applications to Data Compression
    Proceedings of the 1996 International Colloquium on Automata, Languages, and Programming, pp. 514-525, 1998.
    Journal version listed above.

  224. M. Mitzenmacher
    Constant Time per Edge is Optimal in Rooted Tree Networks
    Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures, pp. 162-169, 1996.
    Journal version listed above.

  225. A. Broder and M. Mitzenmacher
    Pattern-based Compression of Text Images
    1996 Data Compression Conference, pp. 300-309.
    Abstract         Conference version (pdf)
    Get from E.

  226. M. Mitzenmacher
    The Power of Two Choices in Randomized Load Balancing
    Ph.D. Thesis
    Abstract         Thesis (ps)         Thesis (pdf)

  227. M. Mitzenmacher
    Designing Stimulating Programming Assignments for an Algorithms Course: A Collection of Problems Based on Random Graphs
    SIGCSE Bulletin, 28:3, pp. 29-36, September 1996.
    Abstract         Journal version (pdf)

  228. M. Mitzenmacher
    Load Balancing and Density Dependent Jump Markov Processes
    Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 213-222, 1996.
    Journal version listed above, under title: The Power of Two Choices in Randomized Load Balancing.

  229. M. Mitzenmacher
    Bounds on the Greedy Routing Algorithm for Array Networks
    Journal of Computer and System Sciences, vol. 53:3, pp. 317-327, December 1996.
    Abstract         Journal version (pdf)


    1995

  230. M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen
    Parallel Randomized Load Balancing
    Proceedings of the 27th ACM Symposium on the Theory of Computing, pp. 238-247, 1995.
    Journal version listed above.


    1994

  231. M. Mitzenmacher
    Bounds on the Greedy Routing Algorithm for Array Networks
    Proceedings of the 6th ACM Symposium on Parallel Algorithms and Architectures, pp. 346-353, 1994.
    Journal version listed above.

  232. G. Louth, M. Mitzenmacher, and F. Kelly
    Computational Complexity of Loss Networks
    Theoretical Computer Science, vol. 125, pp. 45-59, May 1994.
    A copy will be posted soon; please e-mail if you need it.
© Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.