Michael Mitzenmacher : Publications By Subject

Not all papers are necessarily listed here; I have only indexed papers from 2000 on. I have focused on organizing by semi-coherent subject instead of putting everything here. For a list of all papers, go to the listing by year. The most up-to-date version of a paper is listed.

Algorithms for the Internet

  • M. Mitzenmacher
    A Brief History of Generative Models for Power Law and Lognormal Distributions
    Accepted to Internet Mathematics
    A copy will be posted soon; please e-mail if you need it.

  • M. Mitzenmacher
    Dynamic Models for File Sizes and Double Pareto Distributions
    Accepted to Internet Mathematics
    A copy will be posted soon; please e-mail if you need it.

  • B. Conrad and M. Mitzenmacher
    Monkeys Typing Randomly, Revisited
    Accepted (pending revisions) to IEEE Trans. on Inf. Theory
    A copy will be posted soon; please e-mail if you need it.

  • 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
    To appear at Allerton 2003.
    Abstract         Conf. version (pdf)

  • A. Broder and M. Mitzenmacher
    Network Applications of Bloom Filters: A Survey
    Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 636-646, 2002.
    Abstract         Conference version (pdf)

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

  • 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)

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

  • 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)

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

    Coding Theory

  • 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)

  • 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)

  • 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)

  • 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)

  • M. Luby and M. Mitzenmacher
    Verification Codes
    Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 38-47, 2002.
    Abstract         Conference version (pdf)

  • 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)

  • 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)

    The Power of Two Choices/Balls and Bins

  • 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 (pdf)

  • M. Mitzenmacher, R. Oliveira, and J. Spencer.
    A Scaling Result for Explosive Processes.
    Submitted
    A copy will be posted soon; please e-mail if you need it.

  • 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)

  • 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)

  • 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)

  • 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)

  • 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)

  • 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)

  • 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)

  • 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)

    Applications of Digital Fountains

  • 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)

  • 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)

  • 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)

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

    Human-Guided Search

  • 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)

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

  • 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)

  • 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)

    Other Work

    Min-Wise Independent Permutations

  • A. Broder, M. Charikar, and M. Mitzenmacher
    A Derandomization Using Min-Wise Independent Permutations
    Journal of Discrete Algorithms, 2003.
    A copy will be posted soon; please e-mail if you need it.

  • 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)

  • 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)

  • 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)

    Compression

  • 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)

  • M. Mitzenmacher
    On the Hardness of Finding Multiple Preset Dictionaries
    Proceedings of the 2001 Data Compression Conference, pp. 411-418, 2001.
    Abstract         Conference version (pdf)

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

    On-Line Algorithms

  • 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)

  • 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)

  • 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)

    Networks

  • 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)

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

  • G. Louth, M. Mitzenmacher, and F. Kelly
    Computational Complexity of Loss Networks
    Theoretical Computer Science, vol. 125, pp. 45-59, May 1994.
  • 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)

    Teaching

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

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

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