Michael D. Mitzenmacher

Michael D. Mitzenmacher

  • Thomas J. Watson, Sr. Professor of 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.

Contact Information

Office:331 Maxwell Dworkin
Email:michaelm@seas.harvard.edu
Office Phone:(617) 496-7172
Assistant:Mike Donohoe
Assistant Office:Maxwell Dworkin 247
Assistant Phone:617-495-0871

Primary Teaching Area

Computer Science

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

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.