Michael Mitzenmacher
Encyclopedia
Michael D. Mitzenmacher is an American
computer scientist working in algorithms. He
is professor of computer science in the
School of Engineering and Applied Sciences at Harvard University
and area dean of computer science since July 2010.
in computer science at the University of California, Berkeley
in 1996 under the supervision of Alistair Sinclair
. He joined Harvard University
in 1999.
he is the author of a textbook on randomized algorithms and probabilistic techniques in
computer science. His Ph.D. thesis was on the analysis of simple randomised load balancing
schemes. He is a leading expert in hash function
applications such as Bloom filter
s, cuckoo hashing
, 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.
Mitzenmacher has also worked on erasure codes and error-correcting codes. His joint paper on low-density parity-check codes received the 2002 IEEE Information Theory Society
Best Paper Award. His joint paper on fountain code
s received the
2009 ACM SIGCOMM
Test of Time Paper Award.
Mitzenmacher has written over 100 conference and journal publications. He has served on dozens of programme committees in computer science, information theory, and networks, and chaired the programme 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
.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
computer scientist working in algorithms. He
is professor of computer science in the
School of Engineering and Applied Sciences at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
and area dean of computer science since July 2010.
Education
Michael Mitzenmacher received his Ph.D.Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
in computer science at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
in 1996 under the supervision of Alistair Sinclair
Alistair Sinclair
Alistair Sinclair is a British computer scientist and computational theorist.Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh in 1988 under the supervision of Mark Jerrum...
. He joined Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
in 1999.
Research
Mitzenmacher’s research covers the design an analysis of randomised algorithms and processes. With Eli UpfalEli Upfal
Eli Upfal is a computer science researcher currently a professor in the computer science department at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University, Israel in 1978, received an M.Sc...
he is the author of a textbook on randomized algorithms and probabilistic techniques in
computer science. His Ph.D. thesis was on the analysis of simple randomised load balancing
Load balancing (computing)
Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...
schemes. He is a leading expert in hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
applications such as Bloom filter
Bloom filter
A Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not; i.e. a query returns either "inside set " or "definitely not in set"...
s, cuckoo hashing
Cuckoo hashing
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table. Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in 2001...
, and locality sensitive hashing
Locality sensitive hashing
Locality-sensitive hashing is a method of performing probabilistic dimension reduction of high-dimensional data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability .-Definition:An LSH family \mathcal F is defined fora...
. His work on min-wise independence gives a fast way to estimate similarity of electronic documents, and is used in internet search engines.
Mitzenmacher has also worked on erasure codes and error-correcting codes. His joint paper on low-density parity-check codes received the 2002 IEEE Information Theory Society
IEEE Information Theory Society
The IEEE Information Theory Society , formerly the IEEE Information Theory Group, is a professional society of the Institute of Electrical and Electronics Engineers focused on several aspects of information: its processing, transmission, storage, and usage; and the "foundations of the...
Best Paper Award. His joint paper on fountain code
Fountain code
In coding theory, fountain codes are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of...
s received the
2009 ACM SIGCOMM
SIGCOMM
SIGCOMM is the Association for Computing Machinery's Special Interest Group on Data Communications, which specializes in the field of communication and computer networks. It is also the name of an annual 'flagship' conference, organized by SIGCOMM, which is considered to be the leading conference...
Test of Time Paper Award.
Mitzenmacher has written over 100 conference and journal publications. He has served on dozens of programme committees in computer science, information theory, and networks, and chaired the programme committee of the Symposium on Theory of Computing
Symposium on Theory of Computing
STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...
in 2009. He belongs to the editorial board of SIAM Journal on Computing
SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics . As of September 2008, Éva Tardos serves as editor-in-chief.-External links:** on DBLP...
, Internet Mathematics, and Journal of Interconnection Networks
Journal of Interconnection Networks
The Journal of Interconnection Networks was established in 2000 and is published by World Scientific. It covers the field of interconnection networks from theory and analysis to design and implementation, as well as corresponding issues of communication, computing and function...
.