You are here: Home → SEAS Directory → Michael D. Mitzenmacher
Document Actions

Michael D. Mitzenmacher

Faculty
  • Gordon McKay Professor of Computer Science
  • Area Dean for Computer Science
Michael D. Mitzenmacher

Contact Information

Office: Maxwell Dworkin 331
Email: michaelm [ AT ] seas [ DOT ] harvard [ DOT ] edu
Office Phone: (617) 496-7172
Office Fax: (617) 496-5508
Assistant: Phyllis Gorman
Office: Maxwell Dworkin Building 143
Email: pgorman [ AT ] seas [ DOT ] harvard [ DOT ] edu
Office Phone: 617/496-8360

Recruitment Status

Currently accepting graduate students.

Websites

Education

  1. B.A., 1991, Mathematics/Computer Science, Harvard University
  2. C.A.S., 1992, Mathematics, Cambridge University, England
  3. Ph.D., 1996, Computer Science, University of California at Berkeley

Research Interests

    • Applied Mathematics & Computational Science
    • Theory of Computation

Primary Teaching Area

Computer Science

Profile

Professor Mitzenmacher's research focuses on developing randomized algorithms and analyzing random processes, especially for large, distributed computer networks such as the Web.

He develops mathematical tools and methods to analyze complex systems and uses them to solve problems that arise in real applications. For example, he has analyzed simple randomized load balancing schemes for distributed systems such as banks of processors used to host Web services.

This analysis also applies to new hashing schemes. Hashing is a fundamental method for organizing and accessing data, so his analysis may prove effective for several applications. He is currently working on a paper showing how a new hashing scheme can improve current methods for IP routing (the standard protocol for routing data over the internet).

Professor Mitzenmacher has also worked to create new classes of erasure and error-correcting codes. Besides having novel theoretical properties and requiring a sophisticated mathematical analysis, the erasure codes are well-suited for distributing bulk data such as movies or software over the Internet.

He has also co-developed the theory of min-wise independence, which provides a mathematical framework for finding syntactically similar documents in a large collection of documents. The theory is applied in search engines to avoid storing multiple approximate copies of a document, reducing storage needs by about 30%. Recently, he has studied random walks on the Web and shown how they can be used to measure the size and quality of search engine indexes.

Positions & Employment

Harvard School/Division of Engineering and Applied Sciences

  • July 2010-Present: Area Dean for Computer Science 
  • 2005-Present: Professor
  • 2002-2005: Associate Professor
  • 1999-2002: Assistant Professor

Digital Systems Research Center, Palo Alto, CA

  • Fall 1996-Winter 1998: Research Scientist
Santa Clara University
  • Spring 1997: Guest professor for the undergraduate class “Introduction to Algorithms.”

Consulting

  • Adverplex, Akamai, AT&T, Digital Fountain, Google, IBM, ITA Software, Microsoft, and Mitsubishi Research Laboratories. Mitzenmacher also consults on intellectual property issues as an expert witness and in other capacities.

Honors

  • ACM SIGCOMM Test of Time Paper Award, 2009
  • IEEE Information Theory Society Best Paper Award, 2002
  • Alfred P. Sloan Research Fellowship, 2000
  • NSF CAREER Award, 2000
  • Sakrison Award (for Ph.D. thesis at Berkeley), 1997
  • NDSEG Graduate Fellowship, 1992-95
  • NSF Graduate Fellowship Winner, 1991
  • Churchill Fellowship, 1991-92
  • Hoopes Prize (for senior thesis at Harvard), 1991
  • Phi Beta Kappa, 1990
  • Harvard Distinction in Teaching Award, 1990
  • Goldwater Fellowship, 1989-91

Selected Publications

  1. “Streaming Graph Computations with a Helpful Advisor,” with G. Cormode and J. Thaler. To appear in Proceedings of ESA, 2010.
  2. “Tight Thresholds for Cuckoo Hashing via XORSAT,” with M. Dietzfelbinger, A. Goerdt, A. Montanari, R. Pagh, and M. Rink. In Proceedings of 37th International Colloquium on Automata, Languages, and Programming, pp. 213-225, 2010.
  3. “Local cluster aggregation models of explosive percolation,” with R.M. D’Souza. Physical Review Letters, 14(19), p. 104-107, 2010.
  4. “Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities,” with A. Kalai and M. Sudan. In Proceedings of the International Symposium on Information Theory, 2010.
  5. “An Improved Analysis of the Lossy Difference Aggregator,” with H. Finucane. Computer Communication Review, 40(2), pp. 4-11, 2010.
  6. “Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank,” with J. Byers and G. Zervas. In Proceedings of the ACM Conference on Electronic Commerce, pp.1-12, 2010.
  7. “Carousel: Scalable Logging for Intrusion Prevention Systems”, with T. Lam and G. Varghese. In Proceedings of NSDI 2010.
  8. “AMSWithout 4-Wise Independence on Product Domains,” with V. Braverman, K. Chung, Z. Liu, and R. Ostrovsky. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, pp. 119-130, 2010.
  9. “Adaptive Weighing Designs for Keyword Value Computation,” with J. Byers and G. Zervas. In Proceedings of the Third International Conference on Web Search and Web Data Mining pp. 331-340, 2010.
  10. “Designing Floating Codes for Expected Performance,” with F. Chierichetti, H. Finucane, and Z. Liu. IEEE Transactions on Information Theory, vol 56, Issue 3, pp. 968-978, 2010.

Patents Awarded

  1. “Method for finding optimal paths using a stochastic network model,” with Evdokia Nikolova and Matthew Brand. US Patent 07573866. Issued 8/11/2009.
  2. “Ranking search engine results,” with Monika Henzinger. US Patent 07541388. Issued 11/11/2008.
  3. “Distributed, compressed Bloom filter Web cache server.” US Patent 06920477. Issued 7/19/2005.
  4. “Method for packing rectangular strips,” with Neal Lesh and Joe Marks. US Patent 06832129. Issued 12/14/2004.
  5. “System and method for near-uniform sampling of web page addresses,” with Monika Henzinger, Allan Heydon, and Marc Najork. US Patent 06594694. Issued 7/15/2003.
  6. “On demand encoding with a window,” with Michael Luby, Gavin Horn, Jeffrey Persch, John Byers, and Armin Haken. US Patent 06486803. Issued 11/26/2002.
  7. “Generating high weight encoding symbols using a basis,” with Armin Haken, Michael Luby, Gavin Horn, Diane Hernek, and John Byers. US Patent 06411223. Issued 6/25/2002.
  8. “Space-efficient multi-cycle barrel shifter circuit,” with Laurent Moll. US Patent 06314156. Issued 11/6/2001.
  9. “Method for determining a random permutation of variables by applying a test function,” with Andrei Broder, Laurent Moll, and Mark Shand. US Patent 06292762. Issued 9/18/2001.
  10. “Loss resilient code with double heavy tailed series of redundant layers,” with Michael Luby. US Patent 06195777. Issued 2/27/2001.
  11. “Message encoding with irregular graphing,” with Michael Luby, Amin Shokrollahi, Dan Spielman, and Volker Stemann. US Patent 06163870. Issued 12/19/2000.
  12. “Compression of grey scale images of text,” with Andrei Broder. US Patent 06088309. Issued 7/11/2000.
  13. “Irregularly graphed encoding technique,” with Michael Luby, Amin Shokrollahi, Dan Spielman, and Volker Stemann. US Patent 06081909. Issued 6/27/2000.
  14. “Loss resilient decoding technique,” with Michael Luby, Amin Shokrollahi, Dan Spielman, and Volker Stemann. US Patent 06073250. Issued 6/6/2000.
  15. “Task processing optimization in a multiprocessor system,” with Andrei Broder. US Patent 05991808. Issued 11/23/1999.
  16. “Compression protocol with multiple preset dictionaries,” with Andrei Broder and Jeff Mogul. US Patent 05953503. Issued 9/14/1999.

Faculty CV

Mitzenmacher CV.pdf — PDF document, 132Kb