Michael Mitzenmacher

Last updated
Michael Mitzenmacher
Nationality American
Alma mater Harvard University
University of Cambridge
University of California, Berkeley
Awards ACM Fellow (2014)
Scientific career
Fields Algorithms
Institutions Harvard University
Doctoral advisor Alistair Sinclair
Website http://mybiasedcoin.blogspot.com/

Michael David Mitzenmacher is an American computer scientist working in algorithms. He is Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences and was area dean of computer science July 2010 to June 2013. He also runs My Biased Coin , a blog about theoretical computer science.

Contents

Education

In 1986, Mitzenmacher attended the Research Science Institute. Mitzenmacher earned his AB at Harvard, where he was on the team that won the 1990 North American Collegiate Bridge Championship. He attended the University of Cambridge on a Churchill Scholarship from 1991–1992. Mitzenmacher received his PhD in computer science at the University of California, Berkeley in 1996 under the supervision of Alistair Sinclair. [1] He joined Harvard University in 1999. [2]

Research

Mitzenmacher’s research covers the design and analysis of randomised algorithms and processes. With Eli Upfal he is the author of a textbook Mitzenmacher & Upfal (2005) on randomized algorithms and probabilistic techniques in computer science. Mitzenmacher's PhD thesis was on the analysis of simple randomised load balancing schemes. He is an expert in hash function applications such as Bloom filters, [3] cuckoo hashing, [4] and locality-sensitive hashing. His work on min-wise independence gives a fast way to estimate similarity of electronic documents and is used in internet search engines. [5] Mitzenmacher has also worked on erasure codes and error-correcting codes.

Mitzenmacher has authored over 100 conference and journal publications. He has served on dozens of program committees in computer science, information theory, and networks, and chaired the program committee of the Symposium on Theory of Computing in 2009. He belongs to the editorial board of SIAM Journal on Computing, Internet Mathematics, and Journal of Interconnection Networks.

Awards and honors

Mitzenmacher became a fellow of the Association for Computing Machinery in 2014. [6] His joint paper ( Luby et al. 2001 ) on low-density parity-check codes received the 2002 IEEE Information Theory Society Best Paper Award. His joint paper ( Byers et al. 1998 ) on fountain codes received the 2009 ACM SIGCOMM Test of Time Paper Award. [7] In 2019, he was elected as an IEEE Fellow. [8]

Selected publications

Related Research Articles

<span class="mw-page-title-main">Michael O. Rabin</span> Israeli mathematician and computer scientist (born 1931)

Michael Oser Rabin is an Israeli mathematician, computer scientist, and recipient of the Turing Award.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Madhu Sudan</span> Indian-American computer scientist (born 1966)

Madhu Sudan is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015.

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed ; the more items added, the larger the probability of false positives.

In coding theory, Tornado codes are a class of erasure codes that support error correction. Tornado codes require a constant C more redundant blocks than the more data-efficient Reed–Solomon erasure codes, but are much faster to generate and can fix erasures faster. Software-based implementations of tornado codes are about 100 times faster on small lengths and about 10,000 times faster on larger lengths than Reed–Solomon erasure codes. Since the introduction of Tornado codes, many other similar erasure codes have emerged, most notably Online codes, LT codes and Raptor codes.

Scott J. Shenker is an American computer scientist, and professor of computer science at the University of California, Berkeley. He is also the leader of the Extensible Internet Group at the International Computer Science Institute in Berkeley, California.

<span class="mw-page-title-main">Andrei Broder</span> American computer scientist

Andrei Zary Broder is a distinguished scientist at Google. Previously, he was a research fellow and vice president of computational advertising for Yahoo!, and before that, the vice president of research for AltaVista. He has also worked for IBM Research as a distinguished engineer and was CTO of IBM's Institute for Search and Text Analysis.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">Cuckoo hashing</span> Data structure hashing scheme

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.

<span class="mw-page-title-main">Noga Alon</span> Israeli mathematician

Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.

<span class="mw-page-title-main">Michael Luby</span> Information theorist and cryptographer

Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, senior research scientist at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former chief technology officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes. In cryptography he is known for his contributions showing that any one-way function can be used as the basis for private cryptography, and for his analysis, in collaboration with Charles Rackoff, of the Feistel cipher construction. His distributed algorithm to find a maximal independent set in a computer network has also been influential.

Franco P. Preparata is a computer scientist, the An Wang Professor, Emeritus, of Computer Science at Brown University.

Krishna V. Palem is a computer scientist and engineer of Indian origin and is the Kenneth and Audrey Kennedy Professor of Computing at Rice University and the director of Institute for Sustainable Nanoelectronics (ISNE) at Nanyang Technological University (NTU). He is recognized for his "pioneering contributions to the algorithmic, compilation, and architectural foundations of embedded computing", as stated in the citation of his 2009 Wallace McDowell Award, the "highest technical award made solely by the IEEE Computer Society".

Eli Upfal is a computer science researcher, currently the Rush C. Hawkins Professor of Computer Science at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University, Israel in 1978, received an M.Sc. in computer science from the Feinberg Graduate School of the Weizmann Institute of Science, Israel in 1980, and completed his PhD in computer science at the Hebrew University in 1983 under Eli Shamir. He has made contributions in a variety of areas. Most of his work involves randomized and/or online algorithms, stochastic processes, or the probabilistic analysis of deterministic algorithms. Particular applications include routing and communications networks, computational biology, and computational finance.

Hari Balakrishnan is the Fujitsu Professor of Computer Science and Artificial Intelligence in the Department of Electrical Engineering and Computer Science at MIT, and the Co-founder and CTO at Cambridge Mobile Telematics.

<span class="mw-page-title-main">Amin Shokrollahi</span> Iranian mathematician

Amin Shokrollahi is a German-Iranian mathematician who has worked on a variety of topics including coding theory and algebraic complexity theory. He is best known for his work on iterative decoding of graph based codes for which he received the IEEE Information Theory Paper Award of 2002. He is one of the inventors of a modern class of practical erasure codes known as tornado codes, and the principal developer of raptor codes, which belong to a class of rateless erasure codes known as Fountain codes. In connection with the work on these codes, he received the IEEE Eric E. Sumner Award in 2007 together with Michael Luby "for bridging mathematics, Internet design and mobile broadcasting as well as successful standardization" and the IEEE Richard W. Hamming Medal in 2012 together with Michael Luby "for the conception, development, and analysis of practical rateless codes". He also received the 2007 joint Communication Society and Information Theory Society best paper award as well as the 2017 Mustafa Prize for his work on raptor codes.

In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; later work by Carter and Wegman extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings.

The balls into binsproblem is a classic problem in probability theory that has many applications in computer science. The problem involves m balls and n boxes. Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look at the number of balls in each bin; we call this number the load on the bin. The problem can be modelled using a Multinomial distribution, and may involve asking a question such as: What is the expected number of bins with a ball in them?

<span class="mw-page-title-main">Craig Partridge</span> American computer scientist

Craig Partridge is an American computer scientist, known for his contributions to the technical development of the Internet.

References

  1. ↑ Michael Mitzenmacher at the Mathematics Genealogy Project
  2. ↑ Short bio at Mitzenmacher’s web page
  3. ↑ Broder & Mitzenmacher (2005)
  4. ↑ Mitzenmacher (2009)
  5. ↑ Michael D. Mitzenmacher profile at Harvard University.
  6. ↑ ACM Names Fellows for Innovations in Computing Archived 2015-01-09 at the Wayback Machine , ACM, January 8, 2015, retrieved 2015-01-08.
  7. ↑ SIGCOMM test of time awards
  8. ↑ "About the IEEE Fellow Program". IEEE . Retrieved 2019-12-09.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.