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.

    2022

  1. Can Learned Models Replace Hash Functions?
    I. Sabek, K. Vaidya, D. Horn, A. Kipf, M. Mitzenmacher, and T. Kraska.
    Proceedings of the VLDB Endowment, 16:3(532-545), 2022.

  2. T. Chen, B. Matajek, M. Mitzenmacher, and C. Tsourakakis.
    Algorithmic Tools for Mining the Motif Structure of Networks.
    To appear in ECML-PKDD 2022.

  3. T. Chen, B. Matajek, M. Mitzenmacher, H. Pfister, C. Tsourakakis, and D. Wei.
    Edge‑colored directed subgraph enumeration on the connectome.
    Nature Scientific Reports, (2022) 12:11349.
    Online link

  4. M. Mitzenmacher and S. Vassilvitskii.
    Algorithms with Predicctions.
    Communications of the ACM, Volume 65 Issue 7, pp. 33-35
    ACM Digital Library page
    [For more on this, as also listed below, our longer survey is a chapter in the book Beyond Worst Case Analysis (Cambridge Univ Press), draft at arxiv ]

  5. S. Vargaftik, R. Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, M. Mitzenmacher
    EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning
    To appear in ICML 2022.

  6. K. Vaidya, S. Chatterjee, E. Knorr, S. Idreos, M. Mitzenmacher, and T. Kraska
    SNARF: A Learning-Enhanced Range Filter
    To appear in VLDB 2022.

  7. E. Knorr, B. Lemaire, A. Lim, S. Luo, H. Zhang, S. Idreos, and M. Mitzenmacher.
    Proteus: A Self-Designing Range Filter.
    To appear in SIGMOD 2022.

  8. H. Metsky, N. Welch, P. Pillai, N. Haradhvala, L. Rumker, S. Mantena, Y. Zhang, D. Yang, C. Ackerman, J. Weller, P. Blainey, C. Myhrvold, M. Mitzenmacher, and Pardis C. Sabeti.
    Designing Sensitive Viral Diagnostics with Machine Learning.
    In Nature Biotechnology. (Online March 2022).
    Article at website

  9. M. Mitzenmacher, M. Dell'Amico.
    The Supermarket Model with Known and Predicted Service Times.
    To appear in IEEE Transactions on Parallel and Distributed Systems.
    Draft at arxiv

  10. Z. Scully, I. Grosof, and M. Mitzenmacher.
    Uniform Bounds for Scheduling with Job Size Estimates
    To appear in ITCS 2022.
    Draft at arxiv

    2021

  11. J. Langlet, R. Basat, S.S. Ramanathan, G. Oliaro, M. Yu, M.Mitzenmacher, G. Antichi.
    Zero-CPU Collection with Direct Telemetry Access
    Proceedings of the 20th {ACM} Workshop on Hot Topics in Networks, pp. 108-115.


  12. S. Vargaftik, R. Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, M. Mitzenmacher
    DRIVE: One-bit Distributed Mean Estimation
    In Proceedings of Advances in Neural Information Processing Systems (NeurIPS) 34, pp. 362-377.

  13. M. Lam, G. Wei, D. Brooks, V. Reddi, M. Mitzenmacher.
    Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix.
    To appear in ICML 2021.

  14. E. Du, M. Mitzenmacher, and F. Wang.
    Putting the ``Learning'' into Learning-Augmented Algorithms for Frequency Estimation
    To appear in ICML 2021.

  15. M. Mitzenmacher.
    Queues with Small Advice.
    To appear in ACDA 2021.
    Draft on arxiv

  16. R. Basat, M. Mitzenmacher, and S. Vargaftik.
    How to Send a Real Number Using a Single Bit (and Some Shared Randomness)
    To appear in ICALP 2021.

  17. R. Basat, G. Einziger, M. Mitzenmacher, and S. Vargaftik.
    SALSA: Self-Adjusting Lean Streaming Analytics.
    To appear in ICDE 2021.

  18. K. Vaidya, E. Knorr, M. Mitzenmacher, and T. Kraska.
    Partitioned Learned Bloom Filters.
    To appear in ICLR 2021.

  19. M. Mitzenmacher and S. Seddighin.
    Sublinear Time Algorithms for Longest Increasing Subsequence.
    To appear in SODA 2021.

    2020

  20. M. Mitzenmacher and S. Vassilvitskii.
    Algorithms with Predicctions.
    Currently on arxiv
    A chapter in book Beyond Worst Case Analysis (Cambridge Univ Press).

  21. K. Chung, M. Mitzenmacher, and S. Vadhan
    Why Simple Hash Function Suffice
    Currently available here
    A chapter in book Beyond Worst Case Analysis (Cambridge Univ Press).

  22. J. Kucera, R. Basat, M. Kuka, G. Antichi, M. Yu, and M. Mitzenmacher.
    Detecting Routing Loops in the Data Plane
    To appear in CoNEXT 2020.

  23. R. Basat, S. Ramanathan, Y. Li, G. Antichi, M. Yu, M. Mitzenmacher.
    PINT: Probabilistic In-band Network Telemetry
    To appear in SIGCOMM 2020.

  24. K. Larsen, M. Mitzenmacher, and C. Tsourakakis.
    Optimal Learning of Joint Alignments with a Faulty Oracle
    To appear in ISIT 2020.

  25. M. Mitzenmacher and S. Seddighin.
    Dynamic Algorithms for LIS and Distance to Monotonicity
    To appear in STOC 2020.

  26. K. Larsen, M. Mitzenmacher, and C. Tsourakakis
    Clustering with a Faulty Oracle
    To appear in WebConf (WWW) 2020.

  27. H. Esfandiari, M. Hajiaghayi, B. Lucier, and M. Mitzenmacher
    Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
    To appear in AISTATS 2020.

  28. M. Mitzenmacher
    Scheduling with Predictions and the Price of Misprediction
    To appear in ITCS 2020.

  29. R. Basat, G. Einziger, M. Mitzenmacher, and S. Vargaftik.
    Faster and More Accurate Measurement through Additive-Error Counters
    To appear in INFOCOM 2020.

    2019

  30. J. Byers, M. Luby, and M. Mitzenmacher.
    A Digital Fountain Retrospective.
    Available at https://ccronline.sigcomm.org/2019/ccr-october-2019/a-digital-fountain-retrospective
    Computer Communication Review.
    Volume 49, Issued 5, pages 82-85, October 2019.

  31. S. Pontarelli, P. Reviriego, and M. Mitzenmacher.
    Adaptive Cuckoo Filters.
    To appear in ACM Journal of Experimental Algorithmics.
    Preliminary version at arXiv

  32. Yakir Reshef, David Reshef, Pardis Sabeti, Michael Mitzenmacher.
    Equitability, Interval Estimation, and Statistical Power
    To appear in Statistical Science.

  33. M. Mitzenmacher and T. Morgan.
    Robust Set Reconciliation via Locality Sensitive Hashing
    Available at https://arxiv.org/abs/1807.09694
    To appear in PODS 2019.

  34. H. Esfandiari, M. Hajiaghayi, B. Lucier, and M. Mitzenmacher
    Online Pandora's Boxes and Bandits
    To appear in AAAI 2019.

  35. M. Mitzenmacher.
    Arithmetic Progression Hypergraphs: Examining the Second Moment Method
    To appear at ANACLO 2019.
    https://arxiv.org/abs/1712.01781

    2018

  36. M. Mitzenmacher.
    A Model for Learned Bloom Filters and Optimizing by Sandwiching
    Proceedings of the 31st Conference on Neural Information Processing Systems, pp. 462-471, 2018.

  37. R. Adams, D, Cai, and M. Mitzenmacher.
    A Bayesian Nonparametric View on Count-Min Sketch
    Proceedings of the 31st Conference on Neural Information Processing Systems, pp. 8782-8791, 2018.

  38. H. Esfandiari and M. Mitzenmacher
    Metric Sublinear Algorithms via Linear Sampling
    Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, pp. 11-22, 2018.

  39. B. Reagen, U. Gupta, R. Adolf, M. Mitzenmacher, A. Rush, G. Wei, D. Brooks
    Weightless: Lossy Weight Encoding for Deep Neural Network Compression
    Proceedings of the 35th International Conference on Machine Learning, pp. 4321-4330, 2018.
    An arxiv version
    (Summary versions also appeared at SYSML, ICLR)

  40. M. Mitzenmacher, K. Panagiotou, and S. Walzer
    Load Thresholds for Cuckoo Hashing with Double Hashing
    Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 29:1-29:9, 2018.

  41. M. Mitzenmacher and C. Tsourakakis
    Joint Alignment From Pairwise Differences with a Noisy Oracle
    Proceedings of the 15th Workshop on Algorithms and Models for the Web Graph, pp. 59-69, 2018.

  42. M. Mitzenmacher and T. Morgan.
    Reconciling Graphs and Sets of Sets.
    em Proceedings of the 37th Symposium on Principles of Database Systems, pp. 33-47, 2018.
    Preliminary version at arXiv

  43. M. Hopkins, M. Mitzenmacher, and S. Wagner-Carrera.
    Simulated Annealing for JPEG Quantization
    Proceedings of the 2018 IEEE Data Compression Conference, p. 414.
    Preliminary full version at arXiv

  44. S. Pontarelli, P. Reviriego, and M. Mitzenmacher.
    Adaptive Cuckoo Filters.
    Proceedings of the ALENEX Conference, pp. 36-47, 2018.
    Preliminary version at arXiv

  45. Yakir A. Reshef, David N. Reshef, Pardis C. Sabeti, Michael Mitzenmacher.
    An empirical study of the maximal and total information coefficients and leading measures of dependence.
    Preliminary version at arXiv
    Annals of Applied Statistics.
    Vol 12, No.1, pp. 123-155.

  46. M. Mitzenmacher, R. Rajaraman, and S. Roche.
    Better Bounds for Coalescing-Branching Random Walks
    ACM Transactions on Parallel Computing, 5(1), 2:1-2:23, 2018.

  47. M. Mitzenmacher, S. Pontarelli, and P. Reviriego.
    EMOMA: Exact Match in One Memory Access
    IEEE Transactions on Knowledge and Data Engineering, 30(11):2120-2133, 2018.

  48. M. Mitzenmacher and R. Pagh.
    Simple Multi-Party Set Reconciliation.
    Preliminary version at arXiv
    Distributed Computing 31(6):441-453, 2018.

    2017

  49. M. Mitzenmacher.
    Technical Perspective: Building a Better Hash Function.
    Communications of the ACM.
    Vol. 60 No. 7, Page 93.
    At CACM site

  50. M. Goodrich, E. Kornaropoulos, M. Mitzenmacher, R. Tamassia.
    Auditable Data Structures.
    Proceedings of the European Symposium on Security and Privacy, pp. 285-300, 2017

  51. D. Haehn, F. Lekschas, B. Matejek, M. Mitzenmacher, H. Pfister.
    Compresso: Efficient Compression of Segmentation Data For Connectomics
    Proceedings of the 20th International Conference on Medical Image Computing and Computer Assisted Intervention, pp. 781-788, 2017.

  52. David Eppstein, Michael Goodrich, Michael Mitzenmacher and Manuel Torres.
    2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection
    Proceedings of the 36th Symposium on Principles of Database Systems, pp. 247-260, 2017.

  53. Charalampos Tsourakakis, Jakub Pachocki and Michael Mitzenmacher.
    Scalable motif-aware graph clustering
    Proceedings of the 26th International Conference on the World Wide Web, pp. 1451-1460, 2017.

    2016

  54. Yakir A. Reshef, David N. Reshef, Hilary K. Finucane, Pardis C. Sabeti, Michael Mitzenmacher.
    Measuring Dependence Powerfully and Equitably
    Journal of Machine Learning Research, 17(212):1−63, 2016.
    Paper at JMLR site

  55. Ping Li, Michael Mitzenmacher, Martin Slawski
    Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
    NIPS, 2016.
    Paper at NIPS Proceedings

  56. J. Jiang, M. Mitzenmacher, and J. Thaler.
    Parallel Peeling Algorithms.
    ACM Transactions on Parallel Computing, 3(1), 2016.

  57. M. Mitzenmacher and V. Nathan
    Hardness of Peeling with Stashes.
    Information Processing Letters, 116(11), pp. 682-688, 2016.

  58. M. Mitzenmacher.
    Analyzing Distributed Join-Idle-Queue: A Fluid Limit Approach.
    To appear at Allerton 2016.
    Preliminary version at arXiv:1606.01833.

  59. Michael Goodrich, Evgenios Kornaropoulos, Michael Mitzenmacher and Roberto Tamassia.
    More Practical and Secure History-Independent Hash Tables.
    To appear in ESORICS (European Symposium on Research in Computer Security) 2016.

  60. David Eppstein, Michael Goodrich, Jenny Lam, Nil Mamano, Michael Mitzenmacher and Manuel Torres.
    Models and Algorithms for Graph Watermarking.
    To appear in ISC (Information Security Conference) 2016.

  61. M. Mitzenmacher, R. Rajaraman, and S. Roche.
    Better bounds for coalescing-branching random walks on graphs
    To appear in SPAA 2016.

  62. M. Mitzenmacher, S. Pontarelli, and P. Reviriego.
    OMASS: One Memory Access Set Separation
    To appear in IEEE Transactions on Knowledge and Data Engineering.

  63. Meena Boppana, Rani Hod, Michael Mitzenmacher and Tom Morgan
    Voronoi Choice Games
    To appear in ICALP 2016.

  64. E. Liberty, M. Mitzenmacher, J. Thaler, and J. Ullman.
    Space Lower Bounds for Itemset Frequency Sketches
    To appear in PODS 2016.
    Preliminary version at arXiv

  65. M. Mitzenmacher and J. Thaler.
    Technical Perspective: Catching Lies (and Mistakes) in Offloaded Computation.
    Communications of the ACM.
    Vol. 59 No. 2, Page 102.
    At CACM site

  66. M. Mitzenmacher.
    A New Approach to Analyzing Robin Hood Hashing.
    Accepted to ANALCO.
    Preliminary version at arXiv

  67. M. Mitzenmacher.
    More Analysis of Double Hashing for Balanced Allocations
    Accepted to ANALCO.
    Preliminary version at arXiv

    2015

  68. M. Mitzenmacher.
    Theory Without Experiments: Have We Gone Too Far?
    Communications of the ACM, 58(9), pp. 40-42, 2015.
    Link to CACM version

  69. M. Mitzenmacher, J. Pachocki, R. Peng, C. Tsourakakis, S. Chen Xu.
    Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
    KDD 2015

  70. D. Zhou, B. Fan, H. Lim, R. Wang, M. Kaminsky, D. Andersen, M. Mitzenmacher, A. Singh.
    Scaling Up Clustered Network Appliances with XBricks
    SIGCOMM 2015

    2014

  71. B. Haeupler and M. Mitzenmacher.
    Repeated Deletion Channels.
    ITW: IEEE Information Theory Workshop, 2014.

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

  73. 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.

  74. 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.


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

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

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

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

  79. 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

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

  81. 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

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

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

  84. 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

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

  86. 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)

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

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

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

  90. 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

  91. 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

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

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

  94. 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]

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

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

  97. 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

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

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

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

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

  102. 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

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

    2011

  104. 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.

  105. 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

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

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

  108. 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).

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

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

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

  112. 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.

  113. 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.

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

  115. 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)

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

    2010

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

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

  119. 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)

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

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

  122. 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.

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

  124. 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.

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

  126. 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.

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

  128. 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)

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

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

  131. 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

  132. 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).

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

  134. 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.

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

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

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

  138. 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)

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

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

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

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

  143. 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.

  144. 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.

  145. 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.

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

  147. 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).

  148. 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

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

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

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

  152. 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).

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

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

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

  156. 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)

  157. 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.

  158. 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.

  159. 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.

  160. 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

  161. 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)

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

  163. 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)

  164. 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)

  165. 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)

  166. 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)

  167. 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)

  168. 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

  169. 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.

  170. 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)

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

  172. 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.

  173. 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.

  174. 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.

  175. 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.

  176. 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.

  177. 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)

  178. 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)

  179. 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.

  180. 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).

  181. 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)

  182. 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.

  183. 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

  184. 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.

  185. 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)

  186. 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.

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

  188. 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)

  189. 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)

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

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

  192. 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

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

  194. 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.

  195. 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)

  196. 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)

  197. 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)

  198. 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)


  199. 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)

  200. 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)

  201. 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)

  202. 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)

  203. 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.

  204. 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)

  205. 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

  206. 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

  207. 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)

  208. 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)

  209. 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)

  210. 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)

  211. 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)

  212. 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)

  213. 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)

  214. 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).

  215. 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

  216. 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)

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

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

  219. 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)

  220. 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

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

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

  223. 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)

  224. 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)

  225. 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)

  226. 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)

  227. 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)

  228. 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)

  229. 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)

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

  231. 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

  232. 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)

  233. 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)

  234. 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)

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

  236. 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)

  237. 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)

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

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

  240. 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.

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

  242. 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)

  243. 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)

  244. 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)

  245. 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)

  246. 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)

  247. 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)

  248. 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

  249. 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)

  250. 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)

  251. 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

  252. 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)

  253. 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)

  254. 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

  255. 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)

  256. 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

  257. 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)

  258. 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)

  259. 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.

  260. 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)

  261. 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

  262. 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

  263. 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)

  264. 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)

  265. 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.

  266. 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.

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

  268. 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.

  269. 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.

  270. 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

  271. 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.

  272. 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)

  273. 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)

  274. 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

  275. 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.

  276. 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)

  277. 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.

  278. 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.

  279. 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

  280. 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.

  281. 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)

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

  283. 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.

  284. 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

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

  286. 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.

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

  288. 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.

  289. 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)

  290. 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

  291. 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.

  292. 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.

  293. 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.

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

  295. 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)

  296. 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.

  297. 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

  298. 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

  299. 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.

  300. 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.