Research
`Interests
`
`Education
`
`Employment
`
`Michael Mitzenmacher
`michaelmeecs.harvard .edu
`
`617-496-7172
`
`Design and Analysis of Algorithms Networks and Data Transmission Information Theory
`
`UNIVERSITY OF CALIFORNIA AT BERKELEY Berkeley CA
`Ph.D in Computer Science awarded December 1996
`Dissertation The Power of Two Choices in Randomized Load Balancing
`Advisor Alistair Sinclair GPA 4.0/4.0
`
`CAMBRIDGE UNIVERSITY Cambridge England
`Attended as one of ten recipients of the Churchill Fellowship
`Cambridge C.A.S in Mathematics with highest distinction awarded
`
`June 1992
`
`HARVARD COLLEGE Cambridge MA
`B.A in Mathematics with Computer Science summa cum laude awarded June 1991
`
`HARVARD UNIVERSITY Cambridge MA Spring 1999-present
`-July 2002 Associate professor
`from Jan
`from July
`Assistant professor
`1999
`from Jan 2005-present Area Dean for Computer
`2002-January 2005 Professor
`Science from July 2010-June 2013
`Teach the undergraduate course Introduction to
`algorithms and data structures and graduate courses covering topics in randomized al
`and information
`gorithms algorithms for networks
`compression coding cryptography
`retrieval
`
`DIGITAL SYSTEMS RESEARCH CENTER Palo Alto CA Fall 1996- Winter 1998
`Research scientist Projects included work on information retrieval on the Web era
`sure codes error-correcting codes on-line algorithms and load balancing Co-inventor
`twelve submitted patents
`
`for
`
`SANTA CLARA UNIVERSITY Santa Clara CA Spring 1997
`Guest professor
`for the undergraduate class Introduction to Algorithms
`
`Consultant
`consult on intellectual property issues as an expert witness and in other
`have also consulted
`have testified in multiple trials
`capacities As an expert witness
`technology companies and research laboratories including Adverplex Cogo
`for several
`labs Akamai ATT Cisco Digital Fountain eHarmony Fluent Mobile Fiksu Google
`ITA Software JobSync Microsoft Mitsubishi Research Laboratories and Yahoo
`Huawei
`
`Funding
`
`NSF CCF-1320231 AF Small Collaborative Data Synchronization
`Theory Algo
`rithms and Practice P1 Michael Mitzenmacher
`Total grant $399370 9/13-8/16
`
`NSF CNS-1228598 TWC Medium Collaborative Privacy-Preserving Distributed Stor
`age and Computation P1 Michael Goodrich co-PIs Michael Mitzenmacher Roberto
`Tamassia Total grant $400000 8/12-8/16
`
`NSF IIS-0964473 HCC Medium Collaborative Research Data-Parallel Hash Tables
`co-PI Nina Amenta Total
`Theory Practice and Applications P1 Michael Mitzenmacher
`grant $171095 8/10-7/13
`
`Petitioner IBM – Ex. 1008, p. 1
`
`

`
`NSF CCF-09 15922 AF Small
`The Theory and Practice of Hash-Based Algorithms and
`PT Michael Mitzenmacher
`Data Structures
`Total grant $441956 8/09-7/12
`
`NSF CNS-0721491 NeTS FIND
`Network-Wide Hashing Infrastructure for Monitoring
`and Measurement P1 Michael Mitzenmacher
`Total grant $330000 9/07-8/10
`
`NSF CCF-0634923
`of Channels with Synchronization
`Towards
`Basic Understanding
`Errors P1 Michael Mitzenmacher
`Total grant $200000 9/06-8/09
`
`NSF CCR-0121154
`ITR/SY Algorithmic Issues in Large Scale Dynamic Networks
`Eli Upfal Brown Subcontract
`to Harvard Total grant $502000 9/01-8/06
`
`P1
`
`Low Density Parity Check Codes for Channels with Memory PT
`NSF CCR-0118701
`co-PT Alek Kavcic Total grant $510000 9/01-8/04
`Michael Mitzenmacher
`
`NSF CCR-9983832 Dynamic Processes and Network Algorithms CAREER $200000
`7/00-6/04
`
`Google University Research Program 8/13-8/14 PIs Eddie Kohler and Michael Mitzen
`macher $56000
`
`Google University Research Program 12/11-12/12
`
`$25000
`
`Yahoo University Research Program 7/11-6/12
`
`$10000
`
`Google University Research Program 12/09-12/10
`
`$60000
`
`Yahoo University Research Program 9/09-8/10
`
`$10000
`
`Google University Research Program 8/08-7/09
`
`$75000
`
`Yahoo University Research Program 9/07-8/08
`
`$25000
`
`Yahoo University Research Program 9/06-8/07
`
`$50000
`
`Cisco University Research Program 8/08-7/09
`
`$80000
`
`Cisco University Research Program 8/07-7/08
`
`$83000
`
`Cisco University Research Program 8/06-7/07
`
`$80000
`
`Cisco University Research Program 8/05-7/06
`
`$72000
`
`Alfred
`
`Sloan Research Fellowship
`
`$40000 Awarded in 2000
`
`IBM Faculty Research Grant $10000 Awarded in 2005
`
`IBM Faculty Research Grant $10000 Awarded in 2003
`
`Mitsubishi Electronic Research Laboratory $10000 for undergraduate research projects
`Awarded in 2002
`
`Honors
`
`ACM Symposium on Parallelism in Algorithms and Architectures Best Paper Award 2014
`World Wide Web Conference Best Paper Award 2014
`Royal Academy of Engineering Distinguished Visiting Fellowship 2010
`
`Petitioner IBM – Ex. 1008, p. 2
`
`

`
`ACM SIGCOMM Test of Time Paper Award 2009
`IEEE Information Theory Society Best Paper Award 2002
`Sloan Research Fellowship 2000
`Alfred
`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
`
`Professional
`
`Activities
`
`Editorships
`Editorial Board Leibniz International Proceedings
`Editorial Board Communications of the ACM
`Guest Editor SIAM Journal of Computing special
`SIAM Journal on Computing Edtior 2006-2010
`Internet Mathematics Managing Edtior
`Guest Editor Theory of Computing System special
`Journal of Interconnection Networks Edtior
`
`in Informatics
`
`issue for STOC 2009
`
`issue for SPAA 2002
`
`Organizing Committees
`EADS Summer School on Hashing Theory and Applications 2014
`ICERM Workshop on Stochastic Graph Models 2014
`WAW 2013 Organizing Committee
`SIGACT Vice-Chair 2009-2012
`General Chair STOC 2010
`Workshop on Randomized Algorithms and Random Graphs 2010
`DARPA Information Science and Technology Study Groups 2007-2008
`SIGACT Committee for the Advancement of Theoretical Computer Science 2005-2008
`MSRI Workshop on Models of Real-World Random Networks 2005
`FOCS 2003 Local Arrangements Chair
`Second Workshop on Randomized Algorithms and Random Graphs 2003
`Workshop on Algorithms and Models for the Web Graph 2002
`First Workshop on Randomized Algorithms and Random Graphs 2002
`DIMACS Workshop on Quality of Service Issues in the Internet 2001
`BU/NSF Workshop on Internet Measurement
`Instrumentation and Characterization 1999
`FOCS 1998 Local Arrangements Chair
`
`Program Committees
`ITCS 2015 Program Committee
`ICALP 2015 Program Committee
`SIGCOMM 2014 Program Committee
`ACM CoNEXT 2014 Program Committee
`WSDM 2014 Senior Program Committee
`WAW 2013 Program Committee Co-Chair
`STOC 2013 Executive Committee
`WSDM 2013 Senior Program Committee
`SIGCOMM 2012 Program Committee
`ISIT 2012 Program Committee
`
`Petitioner IBM – Ex. 1008, p. 3
`
`

`
`NSDI 2012 Program Committee
`WAW 2011 Program Committee
`ACM CoNEXT 2010 Program Committee
`SIGCOMM 2010 Program Committee
`NSDI 2010 Program Committee
`FUN 2010 Program Committee
`LATIN 2010 Program Committee
`NetSciCom 2009 Program Committee
`SIGCOMM 2009 Program Committee
`STOC 2009 Program Committee PC Chair
`NSDI 2009 Program Committee
`ICALP 2008 Program Committee
`SPAA 2008 Program Committee
`WAW 2007 Program Committee
`Analysis of Algorithms 2007 Program Committee
`ANALCO 2007 Program Committee
`ICALP 2007 Program Committee
`RANDOM 2007 Program Committee
`NCA 2006 Program Committee
`STOC 2006 Program Committee
`PODC 2005 Program Committee
`ANALCO 2005 Program Committee
`PODC 2004 Program Committee
`SIGCOMM 2004 Program Committee
`IPTPS 2004 Program Committee
`Data Compression Conference
`2004 Program Committee
`ESA 2004 Program Committee
`WAW 2003 Program Committee
`FOCS 2003 Program Committee
`Data Compression Conference
`2003 Program Committee
`ESA 2002 Program Committee
`PODC 2002 Program Committee
`SPAA 2002 Program Committee
`STOC 2002 Program Committee
`Data Compression Conference
`2002 Program Committee
`ALENEX 2002 Program Committee
`HiPC 2001 Program Committee
`ISAAC 2000 Program Committee
`RANDOM 2000 Program Committee
`STACS 2000 Program Committee
`FOCS 99 Program Committee
`RANDOM 98 Program Committee
`
`Reviewer
`
`for several conferences
`
`journals and grant panels
`
`Probability and Computing Randomized Algorithms and Probabilistic Analysis by Michael
`Mitzenmacher and Eli Upfal Published by Cambridge University Press in 2005 This is
`textbook meant for an advanced undergraduate or beginning graduate class The textbook
`Berkeley Univ of Victoria Tufts Univ
`has been used in courses at Brown Harvard
`of Mass at Amherst Purdue
`Penn and several other universities
`
`Multi-Party Set Reconciliation Using Characteristic Polynomials with
`
`Boral
`
`In
`
`Books
`
`Conference
`and Journal
`Publications
`
`Petitioner IBM – Ex. 1008, p. 4
`
`

`
`the 52nd Annual Allerton Conference
`Proceedings
`of
`Computing 2014
`
`on Communication Control and
`
`Cleaning Up the Record on the Maximal Information Coefficent and Equitability with
`Boral Proceedings of the National Academy of Sciences 11133E3362-3 2014
`
`Fan D.G Andersen
`Cuckoo Filter Practically Better
`than Bloom with
`and
`Kaminsky In Proceedings of the 10th International on Emerging Networks Experiments
`and Technologies CoNEXT 2014
`
`Coding for Random Projections with
`Li and
`on Machine Learning ICML 2014
`1st International Conference
`Balanced Allocations and Double Hashing In Proceedings of the 26th ACM Symposium
`on Parallel Algorithms and Architectures SPAA 2014
`
`In Proceedings of the
`
`Shrivastava
`
`Thaler
`Jiang and
`Parallel Peeling Algorithms with
`In Proceedings
`ACM Symposium on Parallel Algorithms and Architectures SPAA 2014
`
`of the 26th
`
`How Not
`Wear Minimization for Cuckoo Hashing
`Lot of Eggs into One
`to Throw
`Basket with
`Pszona In Proceedings of the Symposium
`Goodrich and
`Eppstein
`on Experimental Algorithms 2014
`
`Efficient Estimation for High Similarities using Odd Sketches with
`Pham In Proceedings of the World Wide Web Conference 2014
`
`Pagh and
`
`Improving the Performance of Invertible Bloom Lookup Tables with
`Reviriego Information Processing Letters 1144 pp 185-191 2014
`
`Pontarelli and
`
`on the Forty-First Annual ACM Symposium on Theory of Computing
`Special Section
`Umans SIAM Journal
`STOC 2009 with
`Servedio and
`Katz
`Immorlica
`on Computing 4161591-1592 2012
`
`The Daily Deals Marketplace
`Empirical Observations and Managerial
`Zervas AC SlCecom Exchanges 11229-31 2012
`with
`Byers and
`
`Implications
`
`Peeling Arguments and Double Hashing with
`Thaler
`the 50th
`In Proceedings of
`Annual Allerton Conference
`on Communication Control and Computing pp 1118-1125
`2012
`
`The Complexity of Object Reconciliation
`and Open Problems Related to Set Difference
`of the 50th Annual Allerton Conference
`and Coding with
`Varghese In Proceedings
`on Communication Control and Computing pp 1126-1132
`2012
`
`Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability with
`and
`Thaler
`of the First Mediterranean
`In Proceedings
`Goodrich
`Hirschberg
`on Algorithms pp 203-218 2012
`
`Conference
`
`An Economic Analysis of User-Privacy Options in Ad-Supported Services with
`Feigen
`baum and
`on Internet and Network Eco
`Zervas In Proceedings
`of the 8th Workshop
`nomics pp 30-43 2012
`
`Interactive Proofs with
`Verifiable Computation with Massively Parallel
`Pfister
`of the USENIX HotCloud Workshop 2012
`Thaler
`Roberts and
`In Proceedings
`
`Petitioner IBM – Ex. 1008, p. 5
`
`

`
`Buff Bloom Filter Codes Fast Error Correction for Large Data Sets with
`Varghese
`In Proceedings of the International Symposium on Information Theory pp 483-487 2012
`
`Yuen In
`Continuous Time Channels with Interference with
`Thaler and
`Ivan
`Proceedings of the International Symposium on Information Theory pp 860-864 2012
`
`The Groupon Effect on Yelp Ratings
`Byers and
`Root Cause Analysis with
`the ACM Conference
`on Electronic Commerce pp 248-265
`Zervas
`In Proceedings
`of
`
`2012
`
`Anonymous Card Shuffling and Its Applications to Parallel Mixnets with
`In Proceedings of 39th International Colloquium on Automata Languages
`ming pp 549-560 2012
`
`Goodrich
`and Program
`
`Chernoff-Hoeffding Bounds for Markov Chains Generalized and Simplified with
`Lam and
`Chung
`Liu In Proceedings
`the 29th International Symposium on
`of
`Theoretical Aspects of Computer Science pp 124-135 2012
`
`Practical oblivious storage with
`Ohrimenko and
`Tamassia
`Goodrich
`In
`Proceedings of the Second ACM Conference
`on Data and Application Security and Privacy
`pp 13-24 2012
`
`Hierarchical Heavy Hitters with the Space Saving Algorithm Steinke and
`Thaler
`In Proceedings of 2012 Meeting on Algorithm Engineering and Experiments pp 160-174
`
`Daily Deals Prediction Social Diffusion and Reputational Ramifications with
`Byers
`on Web Search and Web
`and
`Zervas In Proceedings of the 5th International Conference
`Data Mining pp 543-552 2012
`
`Cormode
`Practical Verified Computation with Streaming Interactive Proofs with
`Thaler In Proceedings of Innovations in Theoretical Computer Science pp 90-112
`and
`
`2012
`
`Lam
`Information Dissemination via Random Walks in d-Dimensional Space with
`Wang In Proceedings of the 23rd Annual ACM-SIAM Symposium on
`Sun and
`Liu
`Discrete Algorithms pp 1612-1622
`2012
`
`Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation with
`Tamassia In Proceedings of the 23rd Annual ACM-
`and
`Mitzenmacher
`M.Goodrich
`SIAM Symposium on Discrete Algorithms pp 157-167 2012
`
`An Efficient Rigorous Approach for
`sets with
`Kirsch
`Pietracaprina
`ACM 593 2012
`
`Identifying Statistically Significant Frequent
`Item-
`Vandin Journal of the
`Upfal and
`
`Pucci
`
`Detecting Novel Associations in Large Datasets with
`Grossman
`McVean
`Turnbaugh
`Lander and
`No 6602 pp 1518-1524 December
`2011
`
`Finucane
`Reshef
`Reshef
`Sabeti Science Vol 3004
`
`Thaler
`In Proceed
`Goodrich and
`External-Memory Multimaps with
`Angelino
`ings of the 22nd International Symposium on Algorithms and Computation pp 384-394
`2011 Journal version Algorithmica 671 pp 23-48 2013
`
`Petitioner IBM – Ex. 1008, p. 6
`
`

`
`large-scale multimaps with
`Brief announcement
`Goodrich
`23rd ACM Symposium on Parallel Algorithms and Architectures SPAA pp 259-260
`2011
`
`In Proceedings of the
`
`Oblivious RAM Simulation with Efficient Worst-Case Access Overhead with
`Goodrich
`Tamassia In Proceedings of 3rd ACM Cloud Computing Workshop
`Ohrimenko and
`pp 95-100
`
`Invertible Bloom Lookup Tables with
`Goodrich
`In Proceedings of the 9th Annual
`on Communication Control and Computing pp 792-799 2011
`Allerton Conference
`
`Rink In Proceedings of the
`Cuckoo Hashing with Pages with
`and
`Dietzfelbinger
`19th Annual Europeans Symposium on Algorithms pp 615-627 2011
`
`Network Coding Meets TCP Theory and Implementation with J.K Sundararajan
`Barros Proceedings of the IEEE 993 pp 490-
`Shah
`Medard
`and
`Jakubczak
`510 2011
`
`Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation with
`In Proceedings of 38th International Colloquium on Automata Languages
`Goodrich
`Programming pp 576-587 2011
`
`and
`
`Graph-based P2P Traffic Classification Framework for the Internet Back
`Graption
`Kim
`bone with
`Pappu and
`Faloutsos
`Varghese Computer
`Networks 558 pp 1909-1920
`2011
`
`Iliofotou
`
`On the Zero-Error Capacity Threshold for Deletion Channels with
`Kash
`Thaler
`Ullman In Proceedings of the Information Theory and Applications Workshop pp 1-5
`2011
`
`Heapable Sequences and Subsequences with
`Proceedings of ANALCO pp 3-4 2011
`
`Byers
`
`Heeringa and
`
`Zervas
`
`In
`
`Human-Guided Search with
`163289-310 2010
`
`Klau
`
`Marks and
`
`Lesh
`
`Journal of Heuristics
`
`An Introduction
`
`to Human Guided Search ACM Crossroads 17234-35 2010
`
`New Approach to Protecting Passwords
`Popularity is Everything
`Guessing Attacks with
`and
`Herley
`Schechter
`In Proceedings
`on Hot Topics in Security pp 1-8 2010
`Workshop
`
`from Statistical
`
`of the 5th Usenix
`
`Cormode and
`Streaming Graph Computations with Helpful Advisor with
`Thaler
`the European Symposium on Algorithms pp 231-242 2010 Journal
`In Proceedings
`version Algorithmica 652 pp 409-442 2013
`
`of
`
`Tight Thresholds for Cuckoo Hashing via XORSAT with
`Goerdt
`Dietzfelbinger
`Rink In Proceedings of 37th International Colloquium on
`Montanan
`Pagh and
`and Programming pp 213-225 2010
`Automata Languages
`
`Local cluster aggregation models of explosive percolation with R.M DSouza Physical
`Review Letters 1419
`104-107 2010
`
`Petitioner IBM – Ex. 1008, p. 7
`
`

`
`Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities
`Sudan In Proceedings of the International Symposium on Informa
`with
`Kalai and
`tion Theory pp 997-1001 2010
`
`An Improved Analysis of the Lossy Difference Aggregator with
`Communication Review 402 pp 4-11 2010
`
`Finucane Computer
`
`Information Asymmetries in Pay-Per-Bid Auctions How Swoopo Makes Bank with
`Zervas In Proceedings of the ACM Conference
`on Electronic Commerce pp
`Byers and
`1-12 2010
`
`Carousel Scalable Logging for Intrusion Prevention Systems with
`ese In Proceedings of NSDI 2010 pp 361-376
`
`Lam and
`
`Vargh
`
`AMS Without 4-Wise Independence
`on Product Domains with
`Chung
`Braverman
`of the 27th International Symposium on Theo
`Liu and
`Ostrovsky
`In Proceedings
`retical Aspects of Computer Science pp 119-130 2010
`
`for Keyword Value Computation with
`Byers and
`Adaptive Weighing Designs
`on Web Search and Web
`Zervas
`the Third International Conference
`In Proceedings
`of
`Data Mining pp 33 1-340 2010
`
`Human-guided search with
`163 pp 289-310 2010
`
`Klau
`
`Lesh and
`
`Marks
`
`Journal of Heuristics
`
`Real-Time Parallel Hashing on the GPU with
`Abbasinejad
`Alcantara
`Sharf
`Amenta ACM Transactions on Graphics 285
`Owens and
`Sengupta
`2009
`
`154
`
`and Applications
`Exploiting Dynamicity in Graph-based Traffic Analysis Techniques
`Faloutsos In Proceedings of ACM Co-NEXT pp 241-252 2009
`Iliofotou and
`with
`
`An Analysis of Random-Walk Cuckoo Hashing with
`Mellsted
`Frieze and
`In
`of 2009 APPROX-RANDOM pp
`Journal version SIAM
`490-503 2009
`Journal on Computing 402 pp 291-308 2011
`
`Proceedings
`
`Some Open Questions Related to Cuckoo Hashing
`European Symposium on Algorithms pp 1-10 2009
`
`In Proceedings
`
`of the 17th Annual
`
`On Compressing Social Networks with
`Kumar
`Lattanzi
`of the 15th ACM SIGKDD Intl Conference
`Raghavan In Proceedings
`conesi and
`Knowledge Discovery and Data Miming pp 219-228 2009
`
`Chierichetti
`
`Pan
`on
`
`An Efficient Rigorous Approach for
`Item
`Identifying Statistically Significant Frequent
`Vandin In Proceedings
`sets with
`Upfal and
`Pucci
`Kirsch
`Pietracaprina
`of the 28th Symposium on Principles of Database Systems pp 117-126 2009
`
`Using the Power of Two Choices
`no
`ternet Mathematics vol
`
`to Improve Bloom Filters with Steven Lumetta In
`pp 17-33 2009
`
`Network coding meets TCP with
`Sundararajan
`In Proceedings of IEEE INFOCOM pp 280-288 2009
`
`Shah
`
`Medard and
`
`Barros
`
`Petitioner IBM – Ex. 1008, p. 8
`
`

`
`An Economically Principled Generative Model of AS Graph Connectivity with Corbo
`Parkes In Proceedings of IEEE INFOCOM Mini-conference pp 291-
`Jam and
`295 2009
`
`Liu In Pro
`Finucane and
`Designing floating codes for expected performance with
`on Communication Control and Com
`ceedings of the 6th Annual Allerton Conference
`Liu IEEE
`puting 2008
`and
`Journal version with
`Finucane
`Chierichetti
`pp 968-978 2010
`Transactions on Information Theory vol 56 Issue
`
`On the performance of multiple choice hash tables with moves on deletions and inserts
`with
`Kirsch In Proceedings of the 6th Annual Allerton Conference on Communication
`Control and Computing pp 1284-1290 2008
`
`More Robust Hashing Cuckoo Hashing with
`Wieder
`Stash with
`Kirsch and
`In Proceedings of the 16th Annual European Symposium on Algorithms pp 611-622 2008
`Journal version SIAM Journal on Computing 394 pp 1543-1561
`2009
`
`and related synchronization channels In Pro
`survey of results for deletion channels
`on Algorithm Theory pp 1-3 2008 Journal
`ceedings of the 2008 Scandinavian Workshop
`version New Results and Open Problem for Channels with Synchronization Probability
`Surveys 2009
`
`The Power of One Move Hashing Schemes for Hardware with
`Kirsch In Proceedings
`of IEEE INFOCOM pp 106-110 2008 Journal version
`IEEE/ACM Transactions on
`Networking 1861752-1765 2010
`
`Ramchandran
`Johnson and
`Distributed Beamforming with Binary Signaling with
`In Proceedings of the 2008 Intl Symposium on Information Theory ISIT pp 890-894
`2008
`
`The Hiring Problem and Lake Wobegon Strategies with
`Kumar
`Broder
`Kirsch
`In Proceedings of the 1th Annual ACM-SIAM Symposium on
`Upfal and
`Vassilvitskii
`2008 Journal version SIAM Journal on Computing
`Discrete Algorithms pp 1184-1193
`394 pp 1233-1255 2009
`
`Why Simple Hash Functions Work Exploiting the Entropy in
`Data Stream with
`of the 14th Annual ACM-SIAM Symposium on Discrete Algo
`Vadhan
`In Proceedings
`rithms pp 746-755 2008
`
`Trace reconstruction with constant deletion probability and related results with
`In Proceedings of the 14th Annual ACM-SIAM
`Wieder
`and
`Holenstein
`Panigrahy
`Symposium on Discrete Algorithms pp 389-398 2008
`
`Capacity bounds for sticky channels IEEE Transactions on Information Theory vol 54
`pp 72-77 2008
`Issue
`
`Network Monitoring Using Traffic Dispersion Graphs with
`Pappu
`Singh In Proceedings of the 7th ACM SICCOMM Confer
`Faloutsos and
`Varghese
`ence on Internet Measurement pp 315-320 2007
`HEXA Compact Data Structures
`Kumar
`for Faster Packet Processing with
`on Net
`of the IEEE International Conference
`Turner and
`Crowley In Proceedings
`work Protocols pp 246-255 2007
`
`Iliofotou
`
`Petitioner IBM – Ex. 1008, p. 9
`
`

`
`Queue to De-amortize Cuckoo Hashing in Hardware with
`Using
`Kirsch and
`Mitzenmacher
`In Proceedings of the 5th Annual Allerton Conference on Communication
`Control and Computing 2007
`
`deletion and duplication channels with
`Improved lower bounds for the capacity of i.i.d
`Drinea IEEE Transactions on Information Theory vol 53 Issue
`pp 2693-2714
`2007
`
`Wired Geometric Routing with
`of the 6th International Workshop
`
`Pietzuch and
`Seltzer
`In Proceedings
`Ledlie
`on Peer-to-Peer Systems IPTPS 2007
`
`Capacity Upper Bounds for Deletion Channels with
`Diggavi and
`Pfister
`In
`the 2007 Intl Symposium on Information Theory ISIT pp 1716-1720
`
`Proceedings of
`2007
`
`Codes for Deletion and Insertion Channels with Segmented Errors with
`the 2007 Intl Symposium on Information Theory ISIT pp
`846-850
`Proceedings
`of
`IEEE Transactions on Information Theory vol 56 Issue
`pp
`2007 Journal version
`224-232 2010
`
`Liu In
`
`Towards
`theory of networked computation Executive Summary with
`ACM SICACT News 422-26 2006
`
`Feigenbaum
`
`Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment with
`Bonomi
`the Allerton Conference pp
`Singh and
`Panigrahy
`Varghese
`In Proceedings
`of
`877-883 2006
`
`Beyond Bloom Filters From Approximate Membership Checks
`Machines with
`Bonomi
`Singh and
`Panigrahy
`Varghese In Proceedings
`ACM SICCOMM pp 315-326 2006
`An Improved Construction for Counting Bloom Filters with
`Bonomi
`Panigrahy
`Singh and
`of the European Symposium on Algorithms
`In Proceedings
`Varghese
`2006
`
`to Approximate State
`
`of
`
`Better Bloom Filter with
`Less Hashing Same Performance Building
`Kirsch In
`Proceedings of the European Symposium on Algorithms pp 456-467 2006 Journal version
`Random Structures and Algorithms 332 pp 187-218 2008
`
`Brand
`Stochastic Shortest Paths via Quasi-Convex Maximization with
`Kelner
`In Proceedings of the European Symposium on Algorithms pp 552-563
`and
`Nikolova
`
`2006
`
`Polynomial Time Low-Density Parity-Check Codes with Rates Very Close to the Capacity
`of the q-ary Random Deletion Channel
`IEEE Transactions on Information
`for Large
`Theory vol 52 Issue 12 pp 5496-5501 2006
`
`simple lower bound for the capacity of the deletion channel with
`Transactions on Information Theory vol 52 Issue 10 pp 4657-4660 2006
`On Lower Bounds for the Capacity of Deletion Channels with
`Drinea IEEE Trans
`actions on Information Theory vol 52 Issue 10 pp 4648-4657 2006
`
`Drinea IEEE
`
`On the Theory and Practice of Data Recovery with Multiple Versions In Proceedings
`of the International Symposium on Information Theory pp 982-986 2006
`
`Petitioner IBM – Ex. 1008, p. 10
`
`

`
`Fine-Grained Layered Multicast with STAIR with
`Byers Gu-In Kwon and
`IEEE/A CM Transactions on Networking 11 pp 81-93 2006
`Kirsch In Proceedings of the ALENEX con
`
`Luby
`
`Distance-Sensitive Bloom Filters with
`ference pp 41-50 2006
`
`BubbleSearch
`Simple Heuristic
`for Improving Priority-Based Greedy Algorithms
`Lesh Information Processing Letters 974 pp 161-169 2006
`
`with
`
`Network-Aware Overlays with Network Coordinates with
`Ledlie and
`Pietzuch
`on Dynamic Distributed Systems
`the International Workshop
`Seltzer
`In Proceedings of
`
`2006
`
`Editorial The Future of Power Law Research
`525-534 2006
`
`Internet Mathematics vol
`
`no
`
`pp
`
`Lumetta and
`X-Tolerant Test Response Compaction with Mitra
`pp 566-574 Nov/Dec
`Design and Test of Computers vol 22 no
`2005
`
`Patil
`
`IEEE
`
`Privacy preserving keyword searches on remote encrypted data with Y.-C Chang
`In
`on Applied Cryptography and Network Security
`Proceedings of the Third Intl Conference
`pp 442-455 2005
`
`Simple Summaries for Multiple Choice Hashing with
`Kirsch In Proceedings of the
`rd Annual Allerton Conference on Communication Control and Computing 2005 Jour
`nal version IEEE/ACM Transactions on Networking 161 pp 218-231 2008
`
`Lesh and
`Chimani
`case study in large-scale interactive optimization with
`Intelligence and Applications 2005 pp 24-29
`Sidner
`In Proceedings of Artificial
`
`New heuristic and interactive approaches
`to 2D rectangular strip packing with
`Marks ACM Journal of Experimental Algorithms 10 2005
`McMahon
`and
`
`Lesh
`
`Broder
`Multidimensional Balanced Allocations with
`In Proceedings
`Annual ACM-SIAM Symposium on Discrete Algorithms pp 195-196 2005
`
`of
`
`the 11th
`
`Digital Fountains
`
`Survey and Look Forward 2004 Information Theory Workshop
`
`Improved Lower Bounds on the Capacity of lID Deletion Channels with
`Drinea
`In Proceedings of the 2nd Annual Allerton Conference
`on Communication Control and
`Computing 2004
`
`Drinea
`Improved Lower Bounds on the Capacity of Deletion Channels with
`Proceedings of the 200 IEEE International Symposium on Information Theory
`
`In
`
`Geometric Generalizations of the Power of Two Choices with
`Consi
`Byers and
`dine In Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures
`SPAA pp 54-63 2004
`
`Interactive Data Summarizaton An Example Application with
`of the 200 Workshop
`Interfaces pp 183-187
`on Advanced Visual
`
`Lesh In Proceedings
`
`On Power Law Distributions for Monkeys Typing Randomly The Case of Unequal Proba
`Conrad IEEE Transactions on Information Theory 507 pp 1403-1414
`bilities with
`2004
`
`Petitioner IBM – Ex. 1008, p. 11
`
`

`
`Dynamic Models for File Sizes and Double Pareto Distributions Internet Mathematics
`No
`pp 305-334 2004
`vol
`
`for Explosive Processes with
`Scaling Result
`Journal of Combinatorics 111 R31 2004
`An Exhaustive Approach to 2D Strip Packing with
`Information Processing Letters 901 pp 7-14 2004
`
`Oliveira and
`
`Spencer Electronic
`
`Lesh
`
`McMahon and Marks
`
`New Models and Methods for File Size Distributions with
`In Proceedings
`Tworetzky
`on Communication Control and Computing pp
`of the j1st Annual Allerton Conference
`603-612 2003
`
`Capacity Approaching Signal Constellations for Channels with Memory with
`Kavèié
`Ma IEEE Transactions on Information Theory 497 pp 1636-1652
`and
`2003
`
`The Power Spectra of Good Codes for Partial Response Channels with
`Kavcic
`and
`Ma In Proceedings of the 2003 IEEE International Symposium on Information Theory
`45
`
`Ng and
`Chen
`Codes for Deletion Channels with
`Varnica In
`Concatenated
`218
`Proceedings of the 2003 IEEE International Symposium on Information Theory
`
`Verification Codes for Deletion Channels In Proceedings of the 2003 IEEE International
`217
`Symposium on Information Theory
`
`Languages Using PPM
`Estimating and Comparing Entropies Across Written Natural
`Xiao In Proceedings of the 2003 IEEE
`Compression with
`Fossum and
`Behr
`416
`Data Compression Conference
`
`Considine
`Byers and
`Simple Load Balancing for Distributed Hash Tables with
`Appears in the 2nd International Workshop on Peer-to-Peer Systems IPTPS pp 80-87
`2003
`
`Complete and Effective Move Set
`Lesh and
`for Simplified Protein Folding with
`on Research in
`Whitesides
`of the 7th Annual
`In Proceedings
`International Conference
`Computational Molecular Biology pp 188-195 2003
`
`Network Applications of Bloom Filters
`Survey with
`Broder
`In Proceedings
`of
`Control and Computing pp
`on Communication
`the j0th Annual Allerton Conference
`636-646 2002 Journal version to appear in Internet Mathematics
`
`Verification Codes with
`Luby In Proceedings of the j0th Annual Allerton Conference
`IEEE
`on Communication Control and Computing pp 38-47 2002 Journal version
`Transactions on Information Theory 511 pp 120-127 2005
`
`Balls and Bins with Memory with
`Shah In Proceedings of the
`Prabhakar and
`IEEE Symposium on Foundations of Computer Science pp 799-808 2002
`j3rd Annual
`
`Consi
`Informed Content Delivery Across Adaptive Overlay Networks with
`Byers
`In Proceedings of ACM SICCOMM 02 available as Computer Commu
`Rost
`dine and
`nications Review vol 324 pp 47-60 2002 Journal version IEEE/ACM Transactions
`on Networking 125 pp 767-780 2004
`
`Petitioner IBM – Ex. 1008, p. 12
`
`

`
`In Proceedings of the 21st Annual ACM
`Optimal Plans for Aggregation with
`Broder
`Symposium on Principles of Distribtted Computing pp 144-152 2002
`
`Human-Guided Tabu Search with
`the 18th National Conference
`on Artificial
`
`Marks In Proceedings
`Lesh and
`Klau
`Intelligence pp 41-47 2002
`
`of
`
`The HuGS Platform
`Schafer
`Marks and
`pp 324-330 2002
`
`Toolkit
`
`for Interactive Optimization with
`Klau
`on Advanced Visual
`In Proceedings
`of the Workshop
`
`Lesh
`
`Interfaces
`
`Exact Sampling of TCP Window States with
`COM pp 259-265 2002
`
`God In Proceedings of IEEE INFO
`
`Balls and Bins Models with Feedback with
`Drinea and
`Frieze In Proceedings
`the 11th Annual ACM-SIAM Symposium on Discrete Algorithms pp 308-315 2002
`
`of
`
`Brief History of Lognormal and Power Law Distributions In Proceedings of the 9th
`on Communication Control and Computing pp 182-191
`Annual Allerton Conference
`2001 Journal version to appear in Internet Mathematics
`
`Capacity Approaching Signal Constellations for Channels with Memory with
`Ma and
`Varnica In Proceedings of the 9th Annual Allerton Conference
`munication Control and Computing pp 311-320 2001
`the 20th Annual ACM Symposium on
`Compressed Bloom Filters In Proceedings
`of
`Principles of Distributed Computing pp
`IEEE/ACM
`144-150 2001 Journal version
`Transactions on Networks 105 pp 613-620 October 2002
`
`Kavié
`on Com
`
`Towards More Completed Models of TCP Throughput with
`Supercomputing 202 pp 137-160 September 2001
`
`Rajaraman Journal of
`
`Kavié
`Deriving Performance Bounds for ISI Channels Using Gallager Codes with
`Marcus and Wilson In Proceedings of the 2001 International Symposium on Infor
`mation Theory
`345 2001
`
`Toward Compressing Web Graphs with
`Compression Conference pp 203-212 2001
`
`Adler
`
`In Proceedings
`
`of
`
`the 2001 Data
`
`On the Hardness of Finding Multiple Preset Dictionaries
`of the 2001
`In Proceedings
`Data Compression Conference pp 411-418 2001 Journal version IEEE Transactions on
`Information Theory 507 pp 1536-1539 2004
`
`Luby In Proceedings of IEEE
`Byers and
`Fine-Grained Layered Multicast with
`INFOCOM 2001 pp 1143-1151
`2001 Journal version Fine-Grained Layered Multi-
`cast with STAIR with
`Byers Gu-In Kwon and
`Luby To appear in IEEE/ACM
`Transactions on Networking
`
`Using Multiple Hash Functions to Improve IP Lookups with
`of IEEE INFOCOM 2001 pp 1454-1463
`2001
`
`Broder
`
`In Proceedings
`
`Improved Results for Route Planning in Stochastic Transportation Networks with
`Boyan In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
`pp 895-902 2001
`
`Petitioner IBM – Ex. 1008, p. 13
`
`

`
`Owen
`of MIDI Documents with
`Estimating Resemblance
`of the
`In Proceedings
`on Algorithm Engineering and Experiments available as Lecture Notes
`in
`3rd Workshop
`Computer Science 2153 pp 78-90 2001
`
`on Skewed Distributions with Claire Kenyon In
`Linear Waste of Best Fit Bin Packing
`IEEE Symposium on Foundations of Computer Science
`of the 1st Annual
`Proceedings
`issue of Random Structures and
`pp 582-589 2000 Journal version invited to special
`Algorithms 203 pp 441-464 2002
`
`FLID/DL Congestion Control for Layered Multicast with
`Horn
`Frumin
`Byers
`Shaver
`Roetter and
`In Proceedings of the 2nd International Workshop
`Luby
`on Networked Group Communication NGC 2000 pp 71-81 2000
`Journal version
`IEEE Journal on Selected Areas
`with
`Shaver
`Luby and
`Horn
`Byers
`Communications 208 pp 1558-1570 October 2002
`
`in
`
`On Near-Uniform URL Sampling with
`Heydon and
`Najork
`Henzinger
`Proceedings of the Ninth International World Wide Web Conference pp 295-308 2000
`
`In
`
`An Extension of Path Coupling and Its Application to the Glauber Dynamics for Path
`Jerrum In Proceedings of the
`Coupling with
`Dyer
`Greenhill and
`Goldberg
`11th Annual ACM-SIAM Symposium on Discrete Algorithms pp 616-623 2000 Journal
`version SIAM Journal on Computing 306 pp 1962-1975
`2001
`
`Krauthgamer
`Improved Classification via Connectivity Information with
`Broder and
`the 11th Annual ACM-SIAM Symposium on Discrete Algorithms pp
`In Proceedings
`576-585 2000
`
`of
`
`The Asymptotics of Selecting
`Vöcking In Pro
`the Shortest of Two Improved with
`on Communication Control and Com
`ceedings of the 37th Annual Allerton Conference
`puting pp 326-327 1999 Extended version appears
`chapter in Analytic M