This page is woefully out of date. You want the up-to-date list of papers by year!

I am trying to keep this page more up to date, but I probably still don't update it as often as I should. Please keep in mind all these papers are undoubtedly copyrighted by someone other than myself, so please use them in accordance with the proper legal principle. Along those lines, these might not be the final versions, because of copy-editing or other matters. You may want to check the respective journal. If there's a paper that you'd like that you don't see here, please contact me. Also, (almost) all of these files are now Postscript or PDF. I recently changed them so they are all uncompressed to avoid problems with Microsoft systems. If you have any problems, please let me know.

• Description of current projects
• Newest stuff (2002--)
• Load Balancing
• Analysis of Low Density Parity Check Codes
• Digital fountains, and other Multicast/Code Papers
• LDPC Codes For Channels with Memory
• On-line Algorithms
• Min-Wise Independence
• Human-Guided Search
• Algorithms for the World Wide Web
• Miscellaneous other topics

• The Power Spectra of Good Codes for Partial Response Channels
  A. Kavcic, X. Ma, and M. Mitzenmacher.
  To appear at ISIT 2003.
• Concatenated Codes for Deletion Channels
  J. Chen, M. Mitzenmacher, C. Ng, N. Varnica.
  To appear at ISIT 2003.
• Verification Codes for Deletion Channels
  M. Mitzenmacher.
  To appear at ISIT 2003.
• A Complete and Effective Move Set for Simplified Protein Folding
  N. Lesh, M. Mitzenmacher, and S. Whitesides.
  To appear at RECOMB 2003.
  ( Conf. version (pdf).)
• Simple Load Balancing for Distributed Hash Tables
  J. Byers, J. Considine, and M. Mitzenmacher.
  To appear at IPTPS 2003.
  ( Conf. version (pdf) , Conf. version (ps) .)
• Estimating and Comparing Entropies Across Written Natural Languages Using PPM Compression
  F. Behr, V. Fossum, M. Mitzenmacher, and D. Xiao.
  To appear (as a poster) in the 2003 Data Compression Conference.
  Note: this was an undergraduate research project from my CS222 class.
  ( 1 page Conf. version (pdf) , Technical Report (ps) .)
• Network Applications of Bloom Filters: A Survey
  A. Broder and M. Mitzenmacher.
  To appear in Allerton 2002.
  ( Conf. version (pdf) .)
• Fast Approximate Reconciliation of Set Differences
  J. Byers, J. Considine, and M. Mitzenmacher.
  Draft paper, available as BU Computer Science TR 2002-019.
  ( TR version (ps) .)
• A Scaling Result for Explosive Processes.
  M. Mitzenmacher and J. Spencer.
  Draft paper.
  ( Long version (pdf) .)
• Load Balancing with Memory.
  M. Mitzenmacher, B. Prabhakar, and D. Shah.
  To appear in FOCS 2002.
  ( Draft, to be updated (pdf) .)
• Informed Content Delivery Across Adaptive Overlay Networks.
  J. Byers, J. Considine, M. Mitzenmacher, and S. Rost.
  ( Conf. vers (pdf) .)
  To appear in SIGCOMM 2002.
• Verification Codes: Simple Low-Density Parity-Check Codes for Large Alphabets
  M. Luby and M. Mitzenmacher.
  To appear in Allerton 2002.
  ( Conf. version (pdf) .)
• Bounds and Improvements for BiBa Signature Schemes
  M. Mitzenmacher and A. Perrig.
  Harvard Computer Sciecne Technical Report TR-02-02; submitted.
  Working on the final draft.
  ( Abstract , TR (ps) , TR (pdf) .)
• Exact Sampling of TCP Window States
  A. Goel and M. Mitzenmacher.
  To appear in INFOCOM 2002.
  ( Abstract , Conference Version (ps) , Conference Version (pdf) .)
  Working on the final draft.
• Dynamic Models for File Sizes and Double Pareto Distributions
  M. Mitzenmacher.
  ( Abstract , Draft (ps) , Draft (pdf) .)
  Preprint-- not a final version.
• A Brief History of Generative Models for Power Law and Lognormal Distributions. Recently updated!
  M. Mitzenmacher.
  Allerton 2001; journal version to appear in Internet Mathematics.
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Binary Intersymbol Interference Channels: Gallager Codes, Density Evolution, and Code Performance Bounds.
  A. Kavcic, X. Ma, and M. Mitzenmacher.
  Accepted to IEEE Transactions on Information Theory (being revised).
  ( Abstract , Submitted version (ps) , Submitted version (pdf) ).

• Balls and Bins Models with Feedback
  E. Drinea, A. Frieze, and M. Mitzenmacher.
  SODA 2002.
  ( Draft (ps) , Draft (pdf) .)
• Variations on Random Graph Models for the Web
  E. Drinea, M. Enachescu, and M. Mitzenmacher.
  Harvard Technical Report TR-06-01
  ( Tech. Rep. (ps) , Tech. Rep. (pdf) .)
• Using Multiple Hash Functions to Improve IP Lookups
  A. Broder and M. Mitzenmacher.
  INFOCOM 2001
  ( Abstract , Not-final conference version (ps) , Not-final conference version (pdf) .)
• The Power of Two Random Choices: A Survey of Techniques and Results
  M. Mitzenmacher, A. Richa, and R. Sitaraman.
  Handbook of Randomized Algorithms.
  ( Abstract , The survey(ps) , The survey(pdf) .)
• The Asymptotics of Selecting the Shortest of Two, Improved
  M. Mitzenmacher and B. Voecking.
  Allerton99; also to appear in a memorial volume for F. Karpelevich.
  ( Abstract , Conference summary (ps) , Conference summary (pdf) , Full Tech. Report Version(ps) , Full Tech. Report Version(pdf) .)
• Analyses of Load Stealing Models Using Differential Equations.
  M. Mitzenmacher
  SPAA 98
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks.
  R. Cole, B.M. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, A. Richa, K. Schroder, R. Sitaraman, and B. Vocking
  STOC 98
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• How Useful is Old Information?
  M. Mitzenmacher
  PODC 97
  ( Abstract , Extended version (ps) , Extended version (pdf) .)
• The Power of Two Choices in Randomized Load Balancing
  M. Mitzenmacher
  Ph.D. Thesis
  ( Abstract , The whole big thing (ps) , The whole big thing (pdf) .)
• On the Analysis of Randomized Load Balancing Schemes
  M. Mitzenmacher
  SPAA 97
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Load Balancing and Density Dependent Jump Markov Processes
  M. Mitzenmacher
  FOCS 96
  ( Abstract , Conference version (ps) ,x Conference version (pdf) .)
• Parallel Randomized Load Balancing
  M. Adler, S. Chakarabarti, M. Mitzenmacher, and L. Rasmussen.
  STOC 1995, RSA
  ( Abstract , Conference version (ps) , Conference version (pdf) , Tech. report version (ps) , Tech. report version (pdf) .)

• A Note on Low Density Parity Check Codes for Erasures and Errors
  M. Mitzenmacher.
  SRC Technical Note, 1998
  ( Abstract , Technical Report (pdf) .)
• Improved Low Density Parity Check Codes Using Irregular Graphs and Belief Propagation
  M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman.
  ISIT 1998
  ( Abstract , Conference abstract (ps) , Conference abstract (pdf) , Technical Note (ps) , Technical Note x(pdf) .)
• Analysis of Low Density Codes and Improved Designs Using Irregular Graphs
  M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman.
  STOC 1998
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Analysis of Random Processes via And-Or Tree Evaluation
  M. Luby, M. Mitzenmacher, and A. Shokrollahi.
  SODA 98
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Practical Loss-Resilient Codes
  M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann.
  STOC 1997
  ( Abstract , Conference version (ps) , Conference version (pdf) .)

• FLID/DL: Congestion control for layered multicast
  J. Byers, M. Frumin, G. Horn, M. Luby, M. Mitzenmacher, A. Roetter, and W. Shaver.
  NGC 2000
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downlaods
  J. Byers, M. Luby, and M. Mitzenmacher.
  INFOCOM 99
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• A Digital Fountain Approach to the Reliable Distribution of Bulk Data
  J. Byers, M. Luby, M. Mitzenmacher, and A. Rege
  SIGCOMM 98
  ( Abstract , Conference version (ps) , Tech. report version (ps) , Tech. report version (pdf) .)

• Capacity Approaching Signal Constellations for Channels with Memory
  A. Kavcic, X. Ma, M. Mitzenmacher, and N. Varnica.
  Allerton 2001.
  ( Abstract , Conference version (ps) , Conference version (pdf) ).
• Binary Intersymbol Interference Channels: Gallager Codes, Density Evolution, and Code Performance Bounds.
  A. Kavcic, X. Ma, and M. Mitzenmacher.
  Submitted to IEEE Transactions on Information Theory.
  ( Abstract , Submitted version (ps) , Submitted version (pdf) ).
• Deriving Performance Bounds for ISI Channels Using Gallager Codes
  A. Kavcic, B. Marcus, M. Mitzenmacher, and B. Wilson.
  ISIT 2001.
  ( Abstract , Conference version (ps) , Conference version (pdf) ).

• Improved Results for Route Planning in Stochastic Transportation Networks
  J. Boyan and M. Mitzenmacher.
  SODA 01
  ( Abstract , Conference Version (ps) , Conference Version x(pdf) .)
• Linear Waste of Best Fit Bin Packing on Skewed Distributions
  C. Kenyon and M. Mitzenmacher.
  FOCS 00
  ( Abstract , Conference Version (ps) , Conference Version (pdf) .)
• Delayed Information and Action in On-Line Algorithms
  S. Albers, M. Charikar, and M. Mitzenmacher.
  FOCS 98
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Revisiting the COUNTER Algorithm for List Update
  S. Albers and M. Mitzenmacher.
  Inf. Proc. Letters
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Average Case Analyses of First Fit and Random Fit Bin Packing
  S. Albers and M. Mitzenmacher.
  SODA 98
  ( Abstract , Technical Note (ps) , Technical Note (pdf) .)
• Average Case Analyses of List Update Algorithms, with Applications to Data Compression
  S. Albers and M. Mitzenmacher.
  ICALP 96, Algorithmica
  ( Abstract , Journal Version (ps) Journal Version (pdf) .)

• Completeness and Robustness Properties of Min-Wise Independent Permutations
  A. Broder and M. Mitzenmacher.
  RANDOM 99
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• A Derandomization Using Min-wise Independent Permutations
  A. Broder, M. Charikar, and M. Mitzenmacher.
  RANDOM 98
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Min-wise Independent Permutations
  A. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher.
  STOC 98
  ( Abstract , Extended version (ps) , Extended version (pdf) .)

• Human-Guided Tabu Search.
  G. Klau, N. Lesh, J. Marks, and M. Mitzenmacher.
  To appear in AAAI 2002.
  ( Conf. vers (pdf) .)
• The HuGS Platform: A Toolkit for Interactive Optimization
  G. Klau, N. Lesh, J. Marks, M. Mitzenmacher, and G. Schafer.
  To appear in Advanced Visual Interfaces (AVI) 2002.
  ( Conf. vers (pdf) .)

• Compressed Bloom Filters
  M. Mitzenmacher.
  To appear in PODC 2001.
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Toward Compressing Web Graphs
  M. Adler and M. Mitzenmacher.
  To appear in the 2001 Data Compression Conference.
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• On Near-Uniform URL Sampling
  M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork.
  WWW9
  ( Conference version, html .)
• Improved Classification via Connectivity Information
  A. Broder, R. Krauthgamer, and M. Mitzenmacher.
  SODA 2000
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Measuring Index Quality using Random Walks on the Web
  M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork.
  WWW8
  ( Abstract , Conference version (ps) , Conference version (pdf) .)

• Towards More Complete Models of TCP Latency and Throughput
  M. Mitzenmacher and R. Rajaraman.
  To appear in the Journal of Supercomputing.
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Estimating Resemblance of MIDI documents
  M. Mitzenmacher and S. Owen.
  ALENEX 2001
  ( Abstract , Conference Version (ps) , Conference Version (pdf) .)
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
  M Dyer, L. A. Goldberg, C. Greenhill, M. Jerrun and M. Mitzenmacher.
  SODA 2000
  ( Abstract , Journal Version (ps) , Journal Version (pdf) .)
• Analysis of Timing-Based Mutual Exclusion with Random Times
  E. Gafni and M. Mitzenmacher.
  PODC 1999
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Pattern-based Compression of Text Images
  A. Broder and M. Mitzenmacher.
  Data Compression Conference 1996
  ( Abstract , Conference version (ps) , Conference version (pdf) .)
• Designing Stimulating Programming Assignments for an Algorithms Course: A Collection of Problems Based on Random Graphs
  M. Mitzenmacher.
  SIGCSE Bulletin
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Tight Thresholds for The Pure Literal Rule
  M. Mitzenmacher.
  Digital Systems Research Center Technical Note.
  ( Abstract , Technical Note (ps) , Technical Note (pdf) .)
• Constant Time per Edge is Optimal on Rooted Tree Networks
  M. Mitzenmacher.
  SPAA 96, DC
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Bounds on the Greedy Routing Algorithm for Array Networks
  M. Mitzenmacher.
  SPAA 94, JCSS
  ( Abstract , Journal version (ps) , Journal version (pdf) .)
• Computational Complexity of Loss Networks
  F. Kelly, G. Louth, and M. Mitzenmacher.
  Theoretical Computer Science.
  ( Abstract , Journal version (ps) , Journal version (pdf) .)