Michael Mitzenmacher
`michaelm@eecs.harvard.edu
`617-496-7172
`
`Research
`Interests
`
`Education
`
`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.
`
`Employment HARVARD UNIVERSITY, Cambridge, MA Spring 1999-present
`Assistant professor (from Jan. 1999 -July 2002), Associate professor (from July
`2002-January 2005), Professor (from Jan. 2005-present), Area Dean for Computer
`Science (from July 2010-June 2013). Teach the undergraduate course “Introduction to
`algorithms and data structures” and graduate courses covering topics in randomized al-
`gorithms, algorithms for networks, compression, coding, cryptography, and information
`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 for
`twelve submitted patents.
`
`SANTA CLARA UNIVERSITY, Santa Clara, CA Spring 1997
`Guest professor for the undergraduate class “Introduction to Algorithms.”
`
`Consultant: I consult on intellectual property issues as an expert witness and in other
`capacities. As an expert witness, I have testified in multiple trials. I have also consulted for
`several technology companies and research laboratories, including Adverplex (Cogolabs),
`Akamai, AT&T, Digital Fountain, eHarmony, Fluent Mobile (Fiksu), Google, Huawei, ITA
`Software, JobSync, Microsoft, Mitsubishi Research Laboratories, and Yahoo.
`
`Funding
`
`NSF CCF-1563710: CIF: NeTS: Medium: Collaborative Research: Unifying Data Synchro-
`nization. co-PIs: David Starobinksi, Ari Trachtenberg. Total grant: $400,000. 7/16-6/20.
`
`NSF CCF-1535705: AitF: FULL: Collaborative Research: Better Hashing for Applications:
`From Nuts & Bolts to Asymptotics. co-PIs: David Andersen. Total grant: $250,000. 9/15-
`8/19.
`
`NSF CCF-1320231: AF: Small: Data Synchronization : Theory, Algorithms, and Practice
`PI: Michael Mitzenmacher. Total grant: $399,370. 9/13-8/16.
`
`NSF CNS-1228598: TWC: Medium: Collaborative: Privacy-Preserving Distributed Stor-
`age and Computation. PI: Michael Goodrich. co-PIs: Michael Mitzenmacher, Roberto
`Tamassia. Total grant: $400,000. 8/12-8/16.
`
`0001
`
`CALTECH - EXHIBIT 2005
`Apple Inc. v. California Institute of Technology
`IPR2017-00701
`
`

`

`NSF IIS-0964473: HCC: Medium: Collaborative Research: Data-Parallel Hash Tables:
`Theory, Practice and Applications. PI: Michael Mitzenmacher, co-PI: Nina Amenta. Total
`grant: $171,095. 8/10-7/13.
`
`NSF CCF-0915922: AF : Small : The Theory and Practice of Hash-Based Algorithms and
`Data Structures. PI: Michael Mitzenmacher. Total grant: $441,956. 8/09-7/12.
`
`NSF CNS-0721491: NeTS FIND: A Network-Wide Hashing Infrastructure for Monitoring
`and Measurement. PI: Michael Mitzenmacher. Total grant: $330,000. 9/07-8/10.
`
`NSF CCF-0634923: Towards a Basic Understanding of Channels with Synchronization
`Errors. PI: Michael Mitzenmacher. Total grant: $200,000. 9/06-8/09.
`
`NSF CCR-0121154: ITR/SY Algorithmic Issues in Large Scale Dynamic Networks. PI:
`Eli Upfal, Brown. Subcontract to Harvard. Total grant: $502,000. 9/01-8/06.
`
`NSF CCR-0118701: Low Density Parity Check Codes for Channels with Memory. PI:
`Michael Mitzenmacher, co-PI: Alek Kavcic. Total grant: $510,000. 9/01-8/04.
`
`NSF CCR-9983832: Dynamic Processes and Network Algorithms (CAREER). $200,000.
`7/00-6/04.
`
`Google University Research Program. 8/13-8/14. PIs: Eddie Kohler and Michael Mitzen-
`macher $56,000.
`
`Google University Research Program. 12/11-12/12. $25,000.
`
`Yahoo! University Research Program. 7/11-6/12. $10,000.
`
`Google University Research Program. 12/09-12/10. $60,000.
`
`Yahoo! University Research Program. 9/09-8/10. $10,000.
`
`Google University Research Program. 8/08-7/09. $75,000.
`
`Yahoo! University Research Program. 9/07-8/08. $25,000.
`
`Yahoo! University Research Program. 9/06-8/07. $50,000.
`
`Cisco University Research Program. 8/08-7/09. $80,000.
`
`Cisco University Research Program. 8/07-7/08. $83,000.
`
`Cisco University Research Program. 8/06-7/07. $80,000.
`
`Cisco University Research Program. 8/05-7/06. $72,000.
`
`Alfred P. Sloan Research Fellowship. $40,000. Awarded in 2000.
`
`IBM Faculty Research Grant. $10,000 Awarded in 2005.
`
`IBM Faculty Research Grant. $10,000 Awarded in 2003.
`
`Mitsubishi Electronic Research Laboratory. $10,000 for undergraduate research projects.
`Awarded in 2002.
`
`0002
`
`

`

`Honors
`
`ACM Fellow (2014)
`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)
`ACM SIGCOMM Test of Time Paper Award (2009)
`IEEE Information Theory Society Best Paper Award (2002)
`Alfred P. Sloan Research Fellowship (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)
`
`Professional
`Activities
`
`Editorships:
`Editorial Board, Leibniz International Proceedings in Informatics (2009-present)
`Editorial Board, Communications of the ACM (2013-present)
`Science Board, Santa Fe Institute (2013-present)
`Guest Editor, SIAM Journal of Computing special issue for STOC 2009
`SIAM Journal on Computing, Editor (2006-2010)
`Internet Mathematics, Managing Editor
`Guest Editor, Theory of Computing System special issue for SPAA 2002
`Journal of Interconnection Networks, Editor
`
`Organizing Committees:
`SIGACT Chair (2015-2018)
`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:
`ANALCO 2018 Program Committee
`SIGCOMM 2017 Program Committee
`NSDI 2017 Program Committee
`ACM CoNEXT 2016 Program Committee
`
`0003
`
`

`

`SIGCOMM 2016 Program Committee
`ALENEX 2016 Program Committee (Co-Chair)
`ICALP 2016 Program Committee (Track C PC Chair)
`ACM CoNEXT 2015 Program Committee
`ICALP 2015 Program Committee
`ITCS 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
`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
`
`0004
`
`

`

`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.
`
`Books
`
`Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael
`Mitzenmacher and Eli Upfal. Published by Cambridge University Press in 2005.
`(2nd
`edition available in 2017.) This is a textbook meant for an advanced undergraduate or
`beginning graduate class. The textbook has been used in courses at Brown, Harvard, U.
`C. Berkeley, Univ. of Victoria, Tufts, Univ. of Mass. at Amherst, Purdue, U. Penn., and
`several other universities.
`
`Conference
`and Journal
`Publications
`
`“Adaptive Cuckoo Filters,” with S. Pontarelli and P. Reviriego. To appear in ALENEX
`2018.
`
`“An Empirical Comparison of the Maximal and Total Information Coefficients to Leading
`Measures of Dependendence,” with D. Reshef, Y. Reshef, and P. Sabeti. To appear in
`Annals of Applied Statistics.
`
`“Simple Multi-Party Set Reconciliation,” with R. Pagh. To appear in Distributed Com-
`puting.
`
`“Technical Perspective: Building a Better Hash Function.” Communications of the ACM,
`60(7), p. 93, 2017.
`
`“Compresso: Efficient Compression of Segmentation Data For Connectomics,” with D.
`Haehn, F. Lekschas, B. Matejek, and H. Pfister. In Proceedings of the 20th International
`Conference on Medical Image Computing and Computer Assisted Intervention, pp. 781-
`788, 2017.
`
`“Auditable Data Structures,” with M. Goodrich, E. Kornaropoulos, and R. Tamassia. In
`Proceedings of the European Symposium on Security and Privacy, pp. 285-300, 2017.
`
`“2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection,” with D. Eppstein, M.
`Goodrich, and M. Torres. In Proceedings of the 36th Symposium on Principles of Database
`Systems, pp. 247-260, 2017.
`
`“Scalable motif-aware graph clustering,” with C. Tsourakakis and J. Pachocki. In Pro-
`ceedings of the 26th International Conference on the World Wide Web, pp. 1451-1460,
`2017.
`
`“Measuring Dependence Powerfully and Equitably,” with Y. Reshef, D. Reshef, H. Finu-
`cane, and P. Sabeti. Journal of Machine Learning Research, 17(212):163, 2016.
`
`“Quantized Random Projections and Non-Linear Estimation of Cosine Similarity,” with
`P. Li and M. Slawski. To appear in Advances In Neural Information Processing Systems
`29, pp.2748-2756, 2016.
`
`“Analyzing Distributed Join-Idle-Queue: A Fluid Limit Approach.” In Proceedings of
`the 54th Annual Allerton Conference on Communication, Control, and Computing, pp.
`312-318, 2016.
`
`0005
`
`

`

`“Hardness of Peeling with Stashes,” with V. Nathan.
`116(11), pp. 682-688, 2016.
`
`Information Processing Letters,
`
`“More Practical and Secure History-Independent Hash Tables,” with M. Goodrich, E. Ko-
`rnaropoulos, and R. Tamassia. In European Symposium on Research in Computer Security,
`pp. 20-38, 2016.
`
`“Models and Algorithms for Graph Watermarking,” with D. Eppstein, M. Goodrich, J.
`Lam, N. Mamano, and M. Torres. In Proceedings of the Information Security Conference,
`pp. 283-301, 2016.
`
`“Better Bounds for Coalescing-Branching Random Walks on Graphs,” with R. Rajaraman
`and S. Roche. In Proceedings of the 28th ACM Symposium on Parallel Algorithms and
`Architectures (SPAA), pp. 313-323, 2016.
`
`“OMASS: One Memory Access Set Separation,” with S. Pontarelli and P. Reviriego. IEEE
`Transactions on Knowledge and Data Engineering, 28(7):1940-1943, 2016.
`
`In Proceedings
`“Voronoi Choice Games”, with M. Boppana, R. Hod, and T. Morgan.
`of 43rd International Colloquium on Automata, Languages, and Programming, 23:1-23:13,
`2016.
`
`“Space Lower Bounds for Itemset Frequency Sketches,” with E. Liberty, J. Thaler, and
`J. Ullman. In Proceedings of the 35th Symposium on Principles of Database Systems, pp.
`441-454, 2016.
`
`“Technical Perspective: Catching Lies (and Mistakes) in Offloaded Computation,” with J.
`Thaler. Communications of the ACM, 59(2), p. 102, 2016.
`
`“A New Approach to Analyzing Robin Hood Hashing.” In Proceedings of ANALCO, pp.
`10-24, 2016.
`
`“More Analysis of Double Hashing for Balanced Allocations.” In Proceedings of ANALCO,
`pp. 1-9, 2016.
`
`“Theory Without Experiments: Have We Gone Too Far?” Communications of the ACM,
`58(9), pp. 40-42, 2015.
`
`“Scaling Up Clustered Network Appliances with XBricks,” with D. Zhou, B. Fan, H. Lim,
`R. Wang, M. Kaminsky, D. Andersen, and A. Singh. In Proceedings of ACM SIGCOMM,
`2015.
`
`“Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling,” with J.
`Pachocki, R. Peng, C. Tsourakakis, and S. Chen Xu.
`In Proceedings of the 21st ACM
`SIGKDD Conference on Knowledge Discovery and Data Mining, 2015.
`
`“Repeated Deletion Channels,” with B. Haeupler. In Proceedings of the IEEE Information
`Theory Workshop, pp. 152-156, 2014.
`
`In
`“Multi-Party Set Reconciliation Using Characteristic Polynomials,” with A. Boral.
`Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and
`Computing, pp. 1182-1187, 2014.
`
`0006
`
`

`

`“Cleaning Up the Record on the Maximal Information Coefficent and Equitability,” with
`D. Reshef, Y. Reshef, and P. Sabeti. Proceedings of the National Academy of Sciences
`111(33):E3362-3, 2014.
`
`“Cuckoo Filter: Practically Better than Bloom,” with B. Fan, D.G. Andersen, and M.
`Kaminsky.
`In Proceedings of the 10th International Conference on Emerging Networks
`Experiments and Technologies (CoNEXT), pp. 75-88, 2014.
`
`“Coding for Random Projections,” with P. Li and A. Shrivastava. In Proceedings of the
`31st International Conference on Machine Learning (ICML), pp. 676684, 2014.
`
`“Balanced Allocations and Double Hashing.” In Proceedings of the 26th ACM Symposium
`on Parallel Algorithms and Architectures (SPAA), pp. 331-342, 2014.
`
`In Proceedings of the 26th
`“Parallel Peeling Algorithms,” with J. Jiang and J. Thaler.
`ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 319-330, 2014.
`Journal version: ACM Transactions on Parallel Computing, 3(1), 7, 2016.
`
`“Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One
`Basket”, with D. Eppstein, M. Goodrich, and P. Pszona. In Proceedings of the 13th Inter-
`national Symposium on Experimental Algorithms, pp. 162-173, 2014.
`
`“Efficient Estimation for High Similarities using Odd Sketches,” with R. Pagh and N.
`Pham. In Proceedings of the 23rd International Conference on the World Wide Web, pp.
`109-118, 2014.
`
`“Improving the Performance of Invertible Bloom Lookup Tables,” with S. Pontarelli and
`P. Reviriego. Information Processing Letters, 114(4), pp. 185-191, 2014.
`
`“Special Section on the Forty-First Annual ACM Symposium on Theory of Computing
`(STOC 2009),” with N. Immorlica, J. Katz, R. Servedio, and C. Umans. SIAM Journal
`on Computing, 41(6):1591-1592, 2012.
`
`“The Daily Deals Marketplace: Empirical Observations and Managerial Implications,”
`with J. Byers and G. Zervas. AC SIGecom Exchanges, 11(2):29-31, 2012.
`
`In Proceedings of the 50th
`“Peeling Arguments and Double Hashing,” with J. Thaler.
`Annual Allerton Conference on Communication, Control, and Computing, pp. 1118-1125,
`2012.
`
`“The Complexity of Object Reconciliation, and Open Problems Related to Set Difference
`and Coding,” with G. Varghese. In Proceedings of the 50th Annual Allerton Conference
`on Communication, Control, and Computing, pp. 1126-1132, 2012.
`
`“Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability,” with
`M. Goodrich, D. Hirschberg, and J. Thaler.
`In Proceedings of the First Mediterranean
`Conference on Algorithms, pp. 203-218, 2012.
`
`“An Economic Analysis of User-Privacy Options in Ad-Supported Services,” with J. Feigen-
`baum and G. Zervas. In Proceedings of the 8th Workshop on Internet and Network Eco-
`nomics, pp. 30-43, 2012.
`
`“Verifiable Computation with Massively Parallel Interactive Proofs,” with H. Pfister, M.
`Roberts, and J. Thaler. In Proceedings of the USENIX HotCloud Workshop, 2012.
`
`0007
`
`

`

`“Biff (Bloom Filter) Codes: Fast Error Correction for Large Data Sets,” with G. Varghese.
`In Proceedings of the International Symposium on Information Theory, pp. 483-487, 2012.
`
`“Continuous Time Channels with Interference,” with I. Ivan, J. Thaler, and H. Yuen. In
`Proceedings of the International Symposium on Information Theory, pp. 860-864, 2012.
`
`“The Groupon Effect on Yelp Ratings: a Root Cause Analysis,” with J. Byers and G.
`Zervas.
`In Proceedings of the ACM Conference on Electronic Commerce, pp. 248-265,
`2012.
`
`“Anonymous Card Shuffling and Its Applications to Parallel Mixnets,” with M. Goodrich.
`In Proceedings of 39th International Colloquium on Automata, Languages, and Program-
`ming, pp. 549-560, 2012.
`
`“Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified,” with K.
`Chung, H. Lam, and Z. Liu.
`In Proceedings of the 29th International Symposium on
`Theoretical Aspects of Computer Science, pp. 124-135, 2012.
`
`In
`“Practical oblivious storage,” with M. Goodrich, O. Ohrimenko and R. Tamassia.
`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,” T. Steinke and J. Thaler.
`In Proceedings of 2012 Meeting on Algorithm Engineering and Experiments, pp. 160-174.
`
`“Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications,” with J. Byers
`and G. Zervas. In Proceedings of the 5th International Conference on Web Search and Web
`Data Mining, pp. 543-552, 2012.
`
`“Practical Verified Computation with Streaming Interactive Proofs,” with G. Cormode
`and J. Thaler. In Proceedings of Innovations in Theoretical Computer Science, pp. 90-112,
`2012.
`
`“Information Dissemination via Random Walks in d-Dimensional Space,” with H. Lam, Z.
`Liu, X. Sun, and Y. Wang. In Proceedings of the 23rd Annual ACM-SIAM Symposium on
`Discrete Algorithms, pp. 1612-1622, 2012.
`
`“Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation,” with
`M.Goodrich, M. Mitzenmacher, and R. Tamassia. In Proceedings of the 23rd Annual ACM-
`SIAM Symposium on Discrete Algorithms, pp. 157-167, 2012.
`
`“An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Item-
`sets,” with A. Kirsch, A. Pietracaprina, G. Pucci, E. Upfal, and F. Vandin. Journal of the
`ACM, 59(3), 2012.
`
`“Detecting Novel Associations in Large Datasets,” with D. Reshef, Y. Reshef, H. Finucane,
`S. Grossman, G. McVean, P. Turnbaugh, E. Lander, and P. Sabeti. Science, Vol. 3004,
`No. 6602, pp. 1518-1524, December 2011.
`
`“External-Memory Multimaps,” with E. Angelino, M. Goodrich, and J. Thaler. In Proceed-
`ings of the 22nd International Symposium on Algorithms and Computation, pp. 384-394,
`2011. Journal version: Algorithmica, 67(1), pp. 23-48, 2013.
`
`0008
`
`

`

`large-scale multimaps,” with M. Goodrich. In Proceedings of the
`“Brief announcement:
`23rd ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 259-260,
`2011.
`
`“Oblivious RAM Simulation with Efficient Worst-Case Access Overhead,” with M. Goodrich,
`O. Ohrimenko, and R. Tamassia. In Proceedings of 3rd ACM Cloud Computing Workshop,
`pp. 95-100.
`
`“Invertible Bloom Lookup Tables,” with M. Goodrich. In Proceedings of the 49th Annual
`Allerton Conference on Communication, Control, and Computing, pp. 792-799, 2011.
`
`“Cuckoo Hashing with Pages,” with M. Dietzfelbinger and M. Rink. In Proceedings of the
`19th Annual Europeans Symposium on Algorithms, pp. 615-627, 2011.
`
`“Network Coding Meets TCP: Theory and Implementation,” with J.K. Sundararajan, D.
`Shah, M. Medard, S. Jakubczak, and J. Barros. Proceedings of the IEEE, 99(3), pp. 490-
`510, 2011.
`
`“Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation,” with M.
`Goodrich. In Proceedings of 38th International Colloquium on Automata, Languages, and
`Programming, pp. 576-587, 2011.
`
`“Graption: A Graph-based P2P Traffic Classification Framework for the Internet Back-
`bone,” with M. Iliofotou, H. Kim, M. Faloutsos, P. Pappu, and G. Varghese. Computer
`Networks, 55(8), pp. 1909-1920, 2011.
`
`“On the Zero-Error Capacity Threshold for Deletion Channels,” with I. Kash, J. Thaler,
`J. Ullman. In Proceedings of the Information Theory and Applications Workshop, pp. 1-5,
`2011.
`
`“Heapable Sequences and Subsequences,” with J. Byers, B. Heeringa, and G. Zervas. In
`Proceedings of ANALCO, pp. 33-44, 2011.
`
`“An Introduction to Human Guided Search.” ACM Crossroads, 17(2):34-35, 2010.
`
`“Popularity is Everything: A New Approach to Protecting Passwords from Statistical
`Guessing Attacks,” with S. Schechter and C. Herley.
`In Proceedings of the 5th Usenix
`Workshop on Hot Topics in Security, pp. 1-8, 2010.
`
`“Streaming Graph Computations with a Helpful Advisor,” with G. Cormode and J. Thaler.
`In Proceedings of the European Symposium on Algorithms, pp. 231-242, 2010. Journal
`version: Algorithmica, 65(2), pp. 409-442, 2013.
`
`“Tight Thresholds for Cuckoo Hashing via XORSAT,” with M. Dietzfelbinger, A. Goerdt,
`A. Montanari, R. Pagh, and M. Rink. In Proceedings of 37th International Colloquium on
`Automata, Languages, and Programming, pp. 213-225, 2010.
`
`“Local cluster aggregation models of explosive percolation,” with R.M. D’Souza. Physical
`Review Letters, 14(19), p. 104-107, 2010.
`
`“Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities,”
`with A. Kalai and M. Sudan. In Proceedings of the International Symposium on Informa-
`tion Theory, pp. 997-1001, 2010.
`
`0009
`
`

`

`“An Improved Analysis of the Lossy Difference Aggregator,” with H. Finucane. Computer
`Communication Review, 40(2), pp. 4-11, 2010.
`
`“Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank,” with J.
`Byers and G. Zervas. In Proceedings of the ACM Conference on Electronic Commerce, pp.
`1-12, 2010.
`
`“Carousel: Scalable Logging for Intrusion Prevention Systems”, with T. Lam and G. Vargh-
`ese. In Proceedings of NSDI 2010, pp. 361-376.
`
`“AMS Without 4-Wise Independence on Product Domains,” with V. Braverman, K. Chung,
`Z. Liu, and R. Ostrovsky. In Proceedings of the 27th International Symposium on Theo-
`retical Aspects of Computer Science, pp. 119-130, 2010.
`
`“Adaptive Weighing Designs for Keyword Value Computation,” with J. Byers and G.
`Zervas.
`In Proceedings of the Third International Conference on Web Search and Web
`Data Mining pp. 331-340, 2010.
`
`“Human-guided search,” with G. Klau, N. Lesh, and J. Marks. Journal of Heuristics,
`16(3), pp. 289-310, 2010.
`
`“Real-Time Parallel Hashing on the GPU,” with D. Alcantara, A. Sharf, F. Abbasinejad,
`S. Sengupta, J. Owens, and N. Amenta. ACM Transactions on Graphics, 28(5), p. 154,
`2009.
`
`“Exploiting Dynamicity in Graph-based Traffic Analysis: Techniques and Applications,”
`with M. Iliofotou and M. Faloutsos. In Proceedings of ACM Co-NEXT, pp. 241-252, 2009.
`
`In
`“An Analysis of Random-Walk Cuckoo Hashing,” with A. Frieze and P. Mellsted.
`Proceedings of 2009 APPROX-RANDOM, pp. 490-503, 2009. Journal version: SIAM
`Journal on Computing, 40(2), pp. 291-308, 2011.
`
`“Some Open Questions Related to Cuckoo Hashing.” In Proceedings of the 17th Annual
`European Symposium on Algorithms, pp. 1-10, 2009.
`
`“On Compressing Social Networks,”, with F. Chierichetti, R. Kumar, S. Lattanzi, A. Pan-
`conesi, and P. Raghavan. In Proceedings of the 15th ACM SIGKDD Int’l Conference on
`Knowledge Discovery and Data Mining, pp. 219-228, 2009.
`
`“An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Item-
`sets,” with A. Kirsch, A. Pietracaprina, G. Pucci, E. Upfal, and F. Vandin. In Proceedings
`of the 28th Symposium on Principles of Database Systems, pp. 117-126, 2009.
`
`“Using the Power of Two Choices to Improve Bloom Filters,” with Steven Lumetta. In-
`ternet Mathematics, vol. 4. no. 1, pp. 17-33, 2009.
`
`“Network coding meets TCP,” with J. Sundararajan, D. Shah, M. Medard, and J. Barros.
`In Proceedings of IEEE INFOCOM, pp. 280-288, 2009.
`
`“An Economically Principled Generative Model of AS Graph Connectivity,” with J. Corbo,
`S. Jain, and D. Parkes. In Proceedings of IEEE INFOCOM (Mini-conference), pp. 2941-
`2945, 2009.
`
`0010
`
`

`

`“Designing floating codes for expected performance,” with H. Finucane and Z. Liu. In Pro-
`ceedings of the 46th Annual Allerton Conference on Communication, Control, and Com-
`puting, 2008. Journal version (with F. Chierichetti, H. Finucane, and Z. Liu): IEEE
`Transactions on Information Theory, vol 56, Issue 3, pp. 968-978, 2010.
`
`“On the performance of multiple choice hash tables with moves on deletions and inserts,”
`with A. Kirsch. In Proceedings of the 46th Annual Allerton Conference on Communication,
`Control, and Computing, pp. 1284-1290, 2008.
`
`“More Robust Hashing: Cuckoo Hashing with a Stash,” with A. Kirsch and U. Wieder.
`In Proceedings of the 16th Annual European Symposium on Algorithms, pp. 611-622, 2008.
`Journal version: SIAM Journal on Computing, 39(4), pp. 1543-1561, 2009.
`
`“A survey of results for deletion channels and related synchronization channels.” In Pro-
`ceedings of the 2008 Scandinavian Workshop on Algorithm Theory, pp. 1-3, 2008. Journal
`version: “New Results and Open Problem for Channels with Synchronization.” Probability
`Surveys, 2009.
`
`“The Power of One Move: Hashing Schemes for Hardware,” with A. Kirsch. In Proceedings
`of IEEE INFOCOM, pp. 106-110, 2008. Journal version: IEEE/ACM Transactions on
`Networking, 18(6):1752-1765, 2010.
`
`“Distributed Beamforming with Binary Signaling,” with M. Johnson and K. Ramchandran.
`In Proceedings of the 2008 Int’l Symposium on Information Theory (ISIT), pp. 890-894,
`2008.
`
`“The Hiring Problem and Lake Wobegon Strategies,” with A. Broder, A. Kirsch, R. Kumar,
`E. Upfal, and S. Vassilvitskii. In Proceedings of the 14th Annual ACM-SIAM Symposium on
`Discrete Algorithms, pp. 1184-1193, 2008. Journal version: SIAM Journal on Computing,
`39(4), pp. 1233-1255, 2009.
`
`“Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream,” with S.
`Vadhan.
`In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algo-
`rithms, pp. 746-755, 2008. Journal version: with K. Chung and S. Vadhan. Theory of
`Computing, 9, pp. 897-945-1255, 2013.
`
`“Trace reconstruction with constant deletion probability and related results,” with T.
`Holenstein, R. Panigrahy, and U. Wieder. In Proceedings of the 14th Annual ACM-SIAM
`Symposium on Discrete Algorithms, pp. 389-398, 2008.
`
`“Capacity bounds for sticky channels.” IEEE Transactions on Information Theory, vol 54,
`Issue 1, pp. 72-77, 2008.
`
`“Network Monitoring Using Traffic Dispersion Graphs,” with M. Iliofotou, P. Pappu, G.
`Varghese, M. Faloutsos, and S. Singh. In Proceedings of the 7th ACM SIGCOMM Confer-
`ence on Internet Measurement, pp. 315-320, 2007.
`
`“HEXA: Compact Data Structures for Faster Packet Processing,” with S. Kumar, J.
`Turner, and P. Crowley.
`In Proceedings of the IEEE International Conference on Net-
`work Protocols, pp. 246-255, 2007.
`
`“Using a Queue to De-amortize Cuckoo Hashing in Hardware,” with A. Kirsch and M.
`Mitzenmacher. In Proceedings of the 45th Annual Allerton Conference on Communication,
`Control, and Computing, 2007.
`
`0011
`
`

`

`“Improved lower bounds for the capacity of i.i.d. deletion and duplication channels, with
`E. Drinea. IEEE Transactions on Information Theory, vol 53, Issue 8, pp. 2693-2714,
`2007.
`
`“Wired Geometric Routing,” with J. Ledlie, P. Pietzuch, and M. Seltzer. In Proceedings
`of the 6th International Workshop on Peer-to-Peer Systems (IPTPS), 2007.
`
`In
`“Capacity Upper Bounds for Deletion Channels,” with S. Diggavi and H. Pfister.
`Proceedings of the 2007 Int’l Symposium on Information Theory (ISIT), pp. 1716-1720,
`2007.
`
`In
`“Codes for Deletion and Insertion Channels with Segmented Errors,” with Z. Liu.
`Proceedings of the 2007 Int’l Symposium on Information Theory (ISIT), pp. 846-850,
`2007. Journal version: IEEE Transactions on Information Theory, vol 56, Issue 1, pp.
`224-232, 2010.
`
`“Towards a theory of networked computation : Executive Summary,” with J. Feigenbaum.
`ACM SIGACT News, (4):22-26, 2006.
`
`“Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment,” with F. Bonomi, R.
`Panigrahy, S. Singh, and G. Varghese.
`In Proceedings of the Allerton Conference, pp.
`877-883, 2006.
`
`“Beyond Bloom Filters: From Approximate Membership Checks to Approximate State
`Machines,” with F. Bonomi, R. Panigrahy, S. Singh, and G. Varghese. In Proceedings of
`ACM SIGCOMM, pp. 315-326, 2006.
`
`“An Improved Construction for Counting Bloom Filters,” with F. Bonomi, R. Panigrahy,
`S. Singh, and G. Varghese.
`In Proceedings of the European Symposium on Algorithms,
`2006.
`
`“Less Hashing, Same Performance: Building A Better Bloom Filter,” with A. Kirsch. In
`Proceedings of the European Symposium on Algorithms, pp. 456-467, 2006. Journal version:
`Random Structures and Algorithms, 33(2), pp. 187-218, 2008.
`
`“Stochastic Shortest Paths via Quasi-Convex Maximization,” with M. Brand, J. Kelner,
`and E. Nikolova. In Proceedings of the European Symposium on Algorithms, pp. 552-563,
`2006.
`
`“Polynomial Time Low-Density Parity-Check Codes with Rates Very Close to the Capacity
`of the q-ary Random Deletion Channel for Large q.” IEEE Transactions on Information
`Theory, vol 52, Issue 12, pp. 5496-5501, 2006.
`
`“A Simple Lower Bound for the Capacity of the Deletion Channel,” with E. Drinea. IEEE
`Transactions on Information Theory, vol 52, Issue 10, pp. 4657-4660, 2006.
`
`“On Lower Bounds for the Capacity of Deletion Channels,” with E. Drinea. IEEE Trans-
`actions on Information Theory, vol 52, Issue 10, pp. 4648-4657, 2006.
`
`“ On the Theory and Practice of Data Recovery with Multiple Versions.” In Proceedings
`of the International Symposium on Information Theory, pp. 982-986, 2006.
`
`“Fine-Grained Layered Multicast with STAIR,” with J. Byers, Gu-In Kwon, and M. Luby.
`IEEE/ACM Transactions on Networking, 14:1, pp. 81-93, 2006.
`
`0012
`
`

`

`“Distance-Sensitive Bloom Filters,” with A. Kirsch. In Proceedings of the ALENEX con-
`ference, pp. 41-50, 2006.
`
`“BubbleSearch: A Simple Heuristic for Improving Priority-Based Greedy Algorithms,”
`with N. Lesh. Information Processing Letters, 97(4), pp. 161-169, 2006.
`
`“Network-Aware Overlays with Network Coordinates,” with P. Pietzuch, J. Ledlie, and M.
`Seltzer. In Proceedings of the International Workshop on Dynamic Distributed Systems,
`2006.
`
`“Editorial: The Future of Power Law Research.” Internet Mathematics, vol. 2. no. 4, pp.
`525-534, 2006.
`
`“X-Tolerant Test Response Compaction,” with S. Mitra, S. Lumetta, and N. Patil. IEEE
`Design and Test of Computers, vol. 22, no. 6, pp. 566-574, Nov/Dec 2005.
`
`“Privacy preserving keyword searches on remote encrypted data,” with Y.-C. Chang. In
`Proceedings of the Third Intl. Conference on Applied Cryptography and Network Security,
`pp. 442-455, 2005.
`
`“Simple Summaries for Multiple Choice Hashing,” with A. Kirsch. In Proceedings of the
`43rd Annual Allerton Conference on Communication, Control, and Computing, 2005. Jour-
`nal version: IEEE/ACM Transactions on Networking: 16(1), pp. 218-231, 2008.
`
`“A case study in large-scale interactive optimization,” with M. Chimani, N. Lesh, and C.
`Sidner. In Proceedings of Artificial Intelligence and Applications 2005, pp. 24-29.
`
`“New heuristic and interactive approaches to 2D rectangular strip packing,” with N. Lesh,
`A. McMahon, and J. Marks. ACM Journal of Experimental Algorithms, 10, 2005.
`
`In Proceedings of the 11th
`“Multidimensional Balanced Allocations,” with A. Broder.
`Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 195-196, 2005.
`
`“Digital Fountains: A Survey and Look Forward.” 2004 Information Theory Workshop.
`
`“Improved Lower Bounds on the Capacity of I.I.D. Deletion Channels,” with E. Drinea.
`In Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and
`Computing, 2004.
`
`“Improved Lower Bounds on the Capacity of Deletion Channels,” with E. Drinea.
`Proceedings of the 2004 IEEE International Symposium on Information Theory.
`
`In
`
`“Geometric Generalizations of the Power of Two Choices,” with J. Byers and J. Consi-
`dine. In Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures
`(SPAA), pp. 54-63, 2004.
`
`“Interactive Data Summariza