Publications - Michael Mitzenmacher
I don't usually put up talks, but sometimes people ask me to, so
when they do, I'll put them here. They're in Powerpoint unless
Learning-Augmented Algorithms: How ML can Lead to Provably Better Algorithms
[ALGO 2019 Keynote TALK]
Worst-Case Analysis: Our Strenth is Our Weakness. [Beyond Worst Case Analysis Workshop, 2011]
Rabin's Information Dispersal Algorithm : A Prescienct Look at Coding on Networks. [Rabin 80th Birthday Workshop, 2011]
Some Uses of Hashing in Networking Problems. [UCL, Cambridge 2010]
Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank. [Liverpool, Cambridge (MSR) 2010]
Some Open Questions on Cuckoo Hashing. [ESA 2009, MSRSV 2009, Stanford 2009]
An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets [Google 2009]
- Some Results on Codes for Flash Memory [London 2009]
- Network Coding Meets TCP [London 2009]
- A History of and New Directions for
Research for Power Laws [SUNY Buffalo 2008]
- Toward Validation and Control of Network Models [IPAM 2008]
Talk given at IPAM meeting, November 2008.
- Designing Floating Codes for Expected Performance [Allerton 2008]
A possible "new direction" for floating codes, with some theory and experiments.
- Moves on Inserts and Deletes [Allerton 2008]
Improving Multi-Level Hash Tables.
- Cuckoo Hashing and CAMs [Cisco/Google 2008]
How to use Content Addressable Memories to make cuckoo hashing even better.
- Why Simple Hash Functions Work [Cisco 2008]
Extended version of SODA paper talk below.
- New Results and Open Problem for Channels
with Synchronization [SWAT2008]
Update on previous talks on deletion channels and related channels.
Comes now with a tasty Survey Article!
- Why Simple Hash Functions Work [SODA2008]
- Cuckoo Hashing in Hardware [Allerton 2007]
This talk covers how to use a CAM as a queue to effectively de-amortize
cuckoo hashing for practical use in hardware (particularly routers).
- Packet Level Algorithms [DIMACS 2007]
This (poorly named) talk was a DIMACS tutorial covering my work on hashing/Bloom filters in network architectures.
- Hashing and Packet Based Algorithms [Cisco 2007]
This (still poorly named) talk was a somewhat modified version of the DIMACS tutorial I gave at Cisco covering my work on hashing/Bloom filters in network architectures.
- Codes for Insertion/Deletion Channels with Segmented Errors
We have high performance linear time encodable/decodable codes for binary channels with deletions (or insertions) as
long as the errors are segmented -- say, at most one error per byte. Given at ISIT 2007.
- Upper Bounding the Capacity of the Deletion Channel
First non-trivial upper bound techniques (at least that I know of) for the binary iid deletion channel.
Given at ISIT 2007.
- Beyond Bloom Filters
All about approximate concurrent state machines (ACSMs), and new constructions of Bloom filters/counting Bloom filters. Given at Stanford, UC Santa Cruz, Stochastic Networks workshop, etc.
- New Results and Open Problem for Insertion/Deletion Channels
Update of a talk given at ANALCO (and elsewhere).
- New Directions for Power Law Research
Recently given at a Radcliffe workshop (and elsewhere).
- Digital Fountains: Applications and Related Issues
Recently given at INFORMS (invited by Bruce Hajek); a previous version was given at ITW 2004.