Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 1 of 39 PageID #: 42940
`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 1 of 39 PagelD #: 42940
`
`APPENDIX A
`APPENDIX A
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 2 of 39 PageID #: 42941
`
`DAVID R. KARGER
`
`Work Address
`MIT Computer Science and Artificial Intelligence Laboratory
`32 Vassar St.
`Cambridge, MA 02139
`(617)-258-6167
`
`Home Address
`21 Craigie St.
`Cambridge, MA 02138
`(617)-491-9592
`email: karger@@mit.edu
`
`Interests
`
`Information management: personal information management, human computer
`interaction, databases, machine learning, social computing, semantic web
`
`Data Structures and Algorithms; Graph Algorithms; Approximation Algorithms;
`Probabilistic Analysis. Applications in communication, networking, biology, natu-
`ral language processing.
`
`Experience MASS. INSTITUTE OF TECHNOLOGY
`January 1995–present
`Professor.
`
`AKAMAI TECHNOLOGIES
`October 1998–April 2001
`Research Scientist.
`
`AT&T BELL LABORATORIES
`September 1994–January 1995
`Postdoctoral Fellow.
`
`XEROX PALO ALTO RESEARCH CENTER
`1991–1995
`Consultant in Information Retrieval.
`
`Cambridge, MA
`
`Cambridge, MA
`
`Murray Hill, NJ
`
`Palo Alto, CA
`
`STANFORD UNIVERSITY
`1991–1994
`Teaching assistant in theory of computation, data structures and algorithms, and
`graduate theory courses. Lectured, prepared assignments and exams, led sections.
`
`Stanford, CA
`
`Education
`
`STANFORD UNIVERSITY
`1991–1995
`Ph.D. in Computer Science. Advisor: Professor Rajeev Motwani
`
`Stanford, CA
`
`CAMBRIDGE UNIVERSITY
`1990
`Certificate of Advanced Study in Mathematics.
`
`Cambridge, England
`
`HARVARD UNIVERSITY
`1985–89
`B.A. summa cum laude in Computer Science and Physics.
`
`Cambridge, MA
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 3 of 39 PageID #: 42942
`
`Dissertation Randomized Algorithms for Graph Optimization Problems. Presents new algo-
`rithms for several graph problems. Gives presently best sequential and parallel
`algorithm for finding minimum cuts in undirected graphs. Presents random sam-
`pling approaches to speeding up graph problems such as minimum spanning tree
`and maximum flow. Gives approximation algorithms for network design problems.
`
`Honors
`
`NAS award for Initiatives in Research, 2003
`
`David and Lucille Packard Foundation Fellowship, 1997–2002
`
`Alfred P. Sloane Foundation Fellowship, 1997–1999
`
`Mathematical Programming Society Tucker Prize, 1997
`
`National Science Foundation CAREER award, 1996-1999
`
`ACM Doctoral Dissertation Award, 1994
`
`Hertz Foundation Graduate Fellowship, 1993-94
`
`National Science Foundation Graduate Fellowship, 1990-93
`
`Churchill Foundation Fellowship for study at Cambridge University, 1989-90
`
`Phi Beta Kappa, 1989
`
`Professional
`Activities
`
`Referee for Journal of the ACM, ACM Transactions on Information Systems,
`Mathematical Programming, Journal of Algorithms, SIAM Journal on Computing,
`Information Processing Letters, Journal of Computer and System Sciences,
`
`Program Committees: 1996 ACM-SIAM Symposium on Discrete Algorithms, 1996
`and 1998 IEEE Symposium on Foundations of Computer Science, 2002 Interna-
`tional Peer to Peer Systems conference (IPTPS), 2005 ACM Symposium on Theory
`of Computing, 2007 and 2009 Conference on Innovative Database Systems Research
`(CIDR), 2008 International Semantic Web Conference (ISWC) , 2010 Conference
`on Intelligent User Interfaces (IUI), 2008 and 2010 Conference on Information
`Retrieval (SIGIR), 2009 Visual Interface to the Social and Semantic Web, Confer-
`ence on Human-Computer Interaction (CHI) 2010, World Wide Web conference
`(WWW) 2003, 2009, 2010
`
`Chair: 2009 International Semantic Web Conference (ISWC) 2009
`
`Member SIAM, ACM, AMS
`
`ACM Fellow
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 4 of 39 PageID #: 42943
`Faculty Personnel Record
`Name: David R. Karger
`
`MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`School of Engineering Faculty Personnel Record
`
`Date: January 25, 2012
`
`1. Date of Birth: 1 May 1967
`
`2. Citizenship: U.S.
`
`3. Education:
`School
`Harvard University
`Cambridge University
`Stanford University
`
`Full Name: David Ron Karger
`
`Department: Electrical Engineering
`and Computer Science
`
`Degree
`A.B.
`Math Certificate
`Ph.D.
`
`Date
`1989
`1990
`1994
`
`4. Title of Ph.D. Thesis:
`Random Sampling in Graph Optimization Problems
`
`5. Principal Fields of Interest:
`Analysis of Algorithms (graph algorithms, combinatorial optimization, randomization).
`Applications of Algorithms in Systems, Networking, and Artificial Intelligence
`Information Retrieval (text databases, digital libraries, filtering and routing).
`
`6. Name and Rank of Other Department Faculty in the Same Field:
`Erik Demaine, Assistant Professor
`Shafi Goldwasser, Professor
`Charles Leiserson, Professor
`Silvio Micali, Professor
`Ron Rivest, Professor
`Madhu Sudan, Associate Professor
`Piotr Indyk, Assistant Professor
`
`7. Name and Rank of Faculty in Other Departments in the Same Field:
`Bonnie Berger, Associate Professor (Mathematics)
`Michel Goemans, Associate Professor (Mathematics)
`F. Thomson Leighton, Professor (Mathematics)
`James Orlin, Professor (Sloane)
`Dan Spielman, Assistant Professor (Mathematics)
`Andreas Schulz, Associate Professor
`Santosh Vempala, Assistant Professor (Mathematics)
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 5 of 39 PageID #: 42944
`Faculty Personnel Record
`Name: David R. Karger
`
`8. Non-M.I.T. Experience:
`Employer
`MIT Lincoln Laboratory
`Harvard University
`Microsoft Corporation
`Xerox PARC
`AT&T
`Akamai Technologies
`
`Position
`Summer Technical Staff
`Teaching Fellow
`Intern
`Intern
`Postdoctoral Fellow
`Research Scientist
`
`Beginning
`1985
`Sep. 1987
`Jun. 1990
`Jun. 1991
`Sep. 1995
`Jun. 1998
`
`Ending
`1989
`May. 1989
`Sep. 1990
`Jun. 1993
`Jan. 1995
`April 2001
`
`9. History of M.I.T. Appointments:
`Rank
`Assistant Professor
`Esther & Harold E. Edgerton Career Development
`Associate Professor
`Associate with Tenure
`Professor
`
`10. Consulting Record:
`Firm
`Xerox PARC
`NEC
`IBM
`Google
`Vanu
`
`Beginning
`Jan. 1995
`
`Ending
`Jul. 1998
`
`1998
`2001
`Jul. 2004
`
`2001
`Jun. 2004
`present
`
`Beginning
`Jun. 1991
`1995
`1996
`1999
`2002
`
`Ending
`1999
`1998
`2000
`2001
`present
`
`11. Department and Institute Committees, Other Assigned Duties:
`Activity
`Beginning
`Undergraduate Counselor (Dept.)
`Sep 1995
`Doctoral Clean Slate
`Dec 1995
`6-A Faculty Advisor for AIG
`1996
`ACM and Sprowls thesis awards
`June 1996/1998/2000
`Graduate Admissions
`1997, 1998, 2001
`Graduate Recruitment
`Jan 1997
`Education
`Jan 2003
`
`Ending
`present
`Dec 1996
`1999
`
`present
`present
`
`12. Professional Service:
`Activity
`Program Committee Member,
`1995 DAGS Summer Institute on Electronic Publishing
`Program Committee Member,
`1996 ACM-SIAM Symposium on Discrete Algorithms
`Program Committee Member,
`1996 IEEE Symposium on Foundations of Computer Science
`
`Beginning Ending
`1995
`
`1995
`
`1996
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 6 of 39 PageID #: 42945
`Faculty Personnel Record
`Name: David R. Karger
`
`Activity
`Program Committee Member,
`Workshop on Survey Methodology and Web Demographics
`Program Committee Member,
`1998 IEEE Symposium on Foundations of Computer Science
`Program Committee Member,
`1999 Workshop on Algorithm Engineering
`and Experimentation
`Program Committee Member,
`1999 Workshop on Randomization and Approximation
`Techniques in Computer Science
`Program Committee Reviewer,
`1999 SIGIR Conference on Information Retrieval
`Judge, Tucker Prize
`Mathematical Programming Society
`Member at Large,
`ACM SIGACT Executive Committee
`Chair,
`ACM SIGACT Electronic Publications Committee
`Editorial Board
`Journal of Information Retrieval (Kluwer Publishers)
`Technical Advisor
`MIT/HP DSpace digital library project
`Program Committee Member,
`1st International Workshop on Peer
`to Peer Systems
`Program Committee Member,
`12th World Wide Web Conference (WWW 2003)
`Program Committee Member,
`ALENEX Workshop on Algorithm Engineering and Experimentation Program Committee Memb
`Conference on Principles of Distributed Computing (PODC 2004)
`Program Committee Member,
`Second Workshop on Semantics in Peer-to-Peer and Grid Computing (SemPGRID04)
`Program Committee Member,
`Symposium on Theory of Computing (STOC 05)
`Member,
`DARPA Information Science and Technology Advisory Panel (ISAT)
`Program Committee Member,
`International Semantic Web Conference (ISWC06)
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 7 of 39 PageID #: 42946
`Faculty Personnel Record
`Name: David R. Karger
`
`Activity
`Program Committee Member,
`Workshop on Semantic Web in Use at ISWC2006
`Program Committee Member,
`Semwiki2006 - From Wiki to Semantics. First workshop on semantic wikis, at 3rd Annual Europe
`Program Committee Member,
`Conference on Innovative Database Research (CIDR07)
`
`13. Awards Received:
`
`Award
`Harvard College Scholarship
`A.B. summa cum laude, Harvard University
`Churchill Foundation Fellowship
`NSF Graduate Fellowship
`Hertz Foundation Graduate Fellowship
`ACM Doctoral Dissertation Award
`NSF CAREER faculty development award
`Alfred P. Sloane Foundation Fellowship
`Mathematical Programming Society Tucker Prize
`David and Lucille Packard Foundation Fellowship
`SIAM Outstanding Paper Prize
`Usenix Security Best Student Paper Award
`National Academy of Sciences Young Innovator Award
`
`Received
`1988, 1989
`1989
`1989
`1990
`1993
`1994
`1996
`1997
`1997
`1998
`2000
`2002
`2003
`
`14. Current Organization Membership:
`Organization
`ΦBK
`ACM:
`
`Special Interest Group on Algorithms and Computation Theory
`Special Interest Group on Information Retrieval
`
`SIAM
`AMS
`
`15. Patents and Patent Applications Pending:
`
`1. Douglas Cutting, David Karger, Jan Pedersen, and John Tukey, “Scatter-Gather: A
`Cluster-based Method and Apparatus for Browsing Large Document Collections,” Patent
`No. 5,442,778, August 15, 1995
`2. Douglas Cutting, David Karger, Jan Pedersen, “Method of Constant Interaction-Time
`Clustering Applied to Document Browsing,: Patent No. 5,483,650, January 9 1996.
`3. David Karger, Eric Lehman, Matt Levine, Daniel Lewin, Tom Leighton, Rina Panigrahy.
`“Method and Aparatus for Distributing Requests Among a Plurality of Resources.”
`Patent No. 6,30,618, August 6, 2002.
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 8 of 39 PageID #: 42947
`Faculty Personnel Record
`Name: David R. Karger
`
`4. David Karger, Eric Lehman, Matt Levine, Daniel Lewin, Tom Leighton, Rina Panigrahy.
`“Method for Caching Files in Networks.” TLO case 7874S.
`5. Andrew D. Berkheimer, William Bogstad, Rizwan Danidina, Ken Iwamoto, David R.
`Karger, Brian A. Kim, William Koffel, F. Thompson Leighton, Daniel Lewin, Lucas
`J. Matkins, Alexander Sherman, Adrian M. Soviani, David Wang, Zhi-Hui Xu, Yoav
`Yerushalmi. “Internet Content-Distribution Software.” TLO Case 8197S.
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 9 of 39 PageID #: 42948
`Faculty Personnel Record
`Name: David R. Karger
`
`Teaching Experience of David Ron Karger
`
`1. Teaching Experience
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 10 of 39 PageID #: 42949
`Faculty Personnel Record
`Name: David R. Karger
`
`Term Subject
`Number
`
`Title
`
`Role
`
`Course
`Type
`
`Course
`evaluation
`survey
`given
`
`ST95
`
`6.001
`
`FT95
`
`6.042
`
`ST96
`
`FT96
`
`6.891
`
`ST97
`
`6.042
`
`FT97
`
`6.854
`
`ST98
`
`6.033
`
`FT98
`
`6.856
`
`ST99
`
`FT99
`
`6.854
`
`ST00
`
`6.042
`
`FT00
`
`6.856
`
`ST01
`
`6.042
`
`6.856
`
`01-02
`FT02
`
`ST02
`
`FT03
`
`6.854
`
`Structure and
`Interpretation
`of Computer
`Programs
`Mathematics
`for Computer
`Science
`parental
`release
`Randomized
`Algorithms
`
`Mathematics
`for Computer
`Science
`Advanced
`Algorithms
`Computer
`Systems
`Randomized
`Algorithms
`parental
`release
`Advanced
`Algorithms
`
`Mathematics
`for Computer
`Science
`Randomized
`Algorithms
`Mathematics
`for Computer
`Science
`sabbatical
`Randomized
`Algorithms
`parental
`release
`Advanced
`Algorithms
`
`Recitation (2
`sections)
`
`Lecture
`
`Yes
`
`Lecture
`
`Yes
`
`Lecture
`
`Lecture
`
`Lecture
`
`Design
`
`Lecture
`
`Lecture
`
`Lecture
`
`Lecture
`
`Lecture
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Yes
`
`Lecture
`
`Yes
`
`Lecture
`
`Yes
`
`Co-in charge,
`lectures
`development
`
`In charge,
`lectures
`development
`In charge,
`lectures
`
`In charge,
`lectures
`Recitations (2
`sections)
`In charge,
`lectures
`
`In charge,
`lectures,
`development
`Co-in charge,
`lectures,
`development
`In charge,
`lectures
`Co-in charge,
`lectures
`development
`
`In charge,
`lectures
`
`co-in charge,
`lectures,
`development
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 11 of 39 PageID #: 42950
`Faculty Personnel Record
`Name: David R. Karger
`
`2. Teaching Evaluation Data
`
`Term Subject
`Number
`
`Total
`students
`registered
`
`Survey form
`used
`
`Instructor
`Teaching
`Quality
`
`Overall
`Course
`Quality
`
`ST95
`FT95
`ST96
`FT96
`ST97
`FT97
`ST98
`FT98
`ST99
`FT99
`ST00
`FT00
`01-02
`FT02
`
`6.001
`6.042
`
`6.891
`6.042
`6.854
`6.033
`6.856
`
`6.854
`6.042
`6.856
`
`6.856
`
`364
`120
`parent release
`15
`136
`22
`355
`40
`parent release
`50
`110
`50
`sabbatical
`37
`
`HKN
`HKN
`
`HKN
`HKN
`HKN
`HKN
`HKN
`
`HKN
`HKN
`HKN
`
`HKN
`
`NA
`NA
`
`6.0
`5.2
`4.8
`NA
`5.7
`
`5.2
`5.2
`6.0
`
`6.2
`
`5.6
`NA
`
`5.9
`4.5
`5.4
`5.6
`5.6
`
`5.8
`4.9
`6.0
`
`6.0
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 12 of 39 PageID #: 42951
`Publications of David Ron Karger
`
`1. Book Chapters
`
`In
`“Randomized Algorithms”.
`1. M. X. Goemans, D. R. Karger, and J. Kleinberg.
`M. Dell’Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliographies in Com-
`binatorial Optimization. John Wiley & Sons, August 1997.
`2. D. R. Karger, C. Stein, and J. Wein. “Scheduling Algorithms”. In M. J. Atallah, editor,
`Algorithms and Theory of Computation Handbook. CRC Press, 1998.
`3. D. R. Karger. “Random Sampling in Graph Optimization Problems: A Survey”. In
`S. Rajasekaran, P. Pardalos, J. Reif, , and J. Rolim, editors, Handbook on Randomization.
`Kluwer Academic Press, 2001.
`
`2. Papers in Refereed Journals
`
`1. D. R. Karger, D. Koller, and S. J. Phillips. “Finding the Hidden Path: Time Bounds for
`All-Pairs Shortest Paths”. SIAM Journal on Computing, 22(6):1199–1217, December
`1993. A preliminary version appeared in Proceedings of the 32nd Annual Symposium on
`the Foundations of Computer Science.
`2. D. R. Karger, P. N. Klein, and R. E. Tarjan. “A Randomized Linear-Time Algorithm
`to Find Minimum Spanning Trees”. Journal of the ACM, 42(2):321–328, March 1995.
`3. C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. “Prim-Dijkstra
`Tradeoffs for Improved Performance-Driven Routing Tree Design”. IEEE Transactions
`on Computer Aided Design, 14(7):890–895, July 1995.
`4. D. R. Karger, S. Phillips, and E. Torng. “A Better Algorithm for an Ancient Schedul-
`ing Problem”. Journal of Algorithms, 20:400–430, March 1996. A preliminary version
`appeared in Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algo-
`rithms.
`5. D. R. Karger and C. Stein. “A New Approach to the Minimum Cut Problem”. Journal
`of the ACM, 43(4):601–640, July 1996. Preliminary portions appeared in SODA 1992
`and STOC 1993.
`6. A. Blum and D. R. Karger. “Improved approximation for graph coloring”. Information
`Processing Letters, 61(1):49–53, January 1997.
`7. D. R. Karger and R. Motwani. “Derandomization Through Approximation: An NC
`Algorithm for Minimum Cuts”. SIAM Journal on Computing, 26(1):255–272, January
`1997. A preliminary version appeared in Proceedings of the 25th ACM Symposium on
`Theory of Computing.
`8. D. R. Karger, N. Nisan, and M. Parnas. “Fast Connected Components Algorithms for the
`EREW PRAM”. SIAM Journal on Computing, 28(3):1021–1034, 1999. A preliminary
`version appeared in Proceedings of the 4th Annual ACM-SIAM Symposium on Parallel
`Algorithms and Architectures.
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 13 of 39 PageID #: 42952
`Publications of David Ron Karger
`
`9. D. R. Karger, G. D. S. Ramkumar, and R. Motwani. “On Approximating the Longest
`Path in a Graph”. Algorithmica, 18(1):82–98, May 1997. A preliminary version appeared
`in the 1993 Workshop on Algorithms and Data Structures.
`10. P. Fizzano, D. R. Karger, C. Stein, and J. Wein. “Job Scheduling in Rings”. Journal
`of Parallel and Distributed Computing, 45(2):122–133, September 1997. A preliminary
`version appeared in Proceedings of the 6th Annual ACM-SIAM Symposium on Parallel
`Algorithms and Architectures.
`11. D. R. Karger and D. Koller. “(De)randomized Construction of Small Sample Spaces
`in NC”. Journal of Computer and System Sciences, 55(3):402–413, December 1997.
`Special issue of selected papers from Proceedings of the 35th Annual Symposium on the
`Foundations of Computer Science.
`12. D. R. Karger. “Random Sampling and Greedy Sparsification in Matroid Optimization
`Problems”. Mathematical Programming B, 82(1–2):41–81, June 1998. A preliminary
`version appeared in Proceedings of the 34th Annual Symposium on the Foundations of
`Computer Science.
`13. D. R. Karger, R. Motwani, and M. Sudan. “Approximate Graph Coloring by Semidef-
`inite Programming”. Journal of the ACM, 45(2):246–265, March 1998. A preliminary
`version appeared in Proceedings of the 35th Annual Symposium on the Foundations of
`Computer Science.
`14. D. R. Karger. “Random Sampling in Graph Optimization Problems: A Survey”. Op-
`tima, 58:1–11, 1998.
`D. Karger, A. Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim,
`L. Matkins, and Y. Yerushalmi. “Web caching with consistent hashing”. Computer
`Networks, 31(11–16):1203–1213, May 1999.
`16. D. R. Karger. “A Randomized Fully Polynomial Approximation Scheme for the All
`Terminal Network Reliability Problem”. SIAM Journal on Computing, 29(2):492–514,
`1999. A preliminary version appeared in Proceedings of the 27th ACM Symposium on
`Theory of Computing. A corrected version was published in SIAM Review. Winner,
`SIAM Outstanding Paper Prize, 2000.
`17. D. R. Karger. “A Randomized Fully Polynomial Approximation Scheme for the All Ter-
`minal Network Reliability Problem”. SIAM Review, 43(3):499–522, 2001. A preliminary
`version appeared in Proceedings of the 27th ACM Symposium on Theory of Computing.
`This corrects a version published in SICOMP. Winner, SIAM Outstanding Paper Prize,
`2000.
`18. S. Arora, D. R. Karger, and M. Karpinski. “Polynomial Time Approximation Schemes
`for Dense Instances of NP-Hard Problems”. Journal of Computer and System Sciences,
`58:193–210, 1999. Special issue of selected papers from Proceedings of the 27th ACM
`Symposium on Theory of Computing.
`
`15.
`
`*
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 14 of 39 PageID #: 42953
`Publications of David Ron Karger
`
`19. D. R. Karger. “Random Sampling in Cut, Flow, and Network Design Problems”. Math-
`ematics of Operations Research, 24(2):383–413, May 1999. A preliminary version ap-
`peared in Proceedings of the 26th ACM Symposium on Theory of Computing.
`20. D. R. Karger. “Minimum Cuts in Near-Linear Time”. Journal of the ACM, 47(1):46–
`76, January 2000. A preliminary version appeared in Proceedings of the 28th ACM
`Symposium on Theory of Computing.
`A. A. Bencz´ur and D. R. Karger. “Augmenting Undirected Edge Connectivity in ˜O(n2)
`Time”. Journal of Algorithms, 37:2–36, 2000. Special issue of selected papers from
`Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms.
`
`21.
`
`*
`
`3. Papers to Appear in Refereed Journals
`
`*
`
`1.
`
`I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and
`H. Balakrishnan. “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Appli-
`cations”. Transactions on Networking, 2003. To appear.
`
`4. Proceedings of Refereed Conferences
`
`1. D. R. Karger, D. Koller, and S. J. Phillips. “Finding the Hidden Path: Time Bounds
`In Proceedings of the 32nd Annual Symposium on the
`for All-Pairs Shortest Paths”.
`Foundations of Computer Science, pages 560–568. IEEE, IEEE Computer Society Press,
`October 1991. Journal version appears in SIAM Journal on Computing 22(6).
`2. D. Cutting, D. R. Karger, J. Pedersen, and J. W. Tukey. “Scatter/Gather: A Cluster-
`based Approach to Browsing Large Document Collections”. In Proceedings of the 15th
`Annual International ACM SIGIR Conference on Research and Development in Infor-
`mation Retrieval, pages 318–329, Copenhagen, Denmark, 1992.
`3. D. R. Karger, N. Nisan, and M. Parnas. “Fast Connected Components Algorithms
`for the EREW PRAM”. In Proceedings of the 4th Annual ACM-SIAM Symposium on
`Parallel Algorithms and Architectures, pages 562–572. ACM, June 1992. Journal version
`appears in SIAM Journal on Computing 28(3).
`4. D. R. Karger. “Global Min-cuts in RNC and Other Ramifications of a Simple Mincut
`Algorithm”. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Al-
`gorithms, pages 21–30. ACM-SIAM, January 1993. Journal version appears in Journal
`of the ACM43(4).
`5. D. R. Karger, G. D. S. Ramkumar, and R. Motwani. “On Approximating the Longest
`Path in a Graph”. In F. Dehne, editor, WADS93: Algorithms and Data Structures :
`Third Workshop, number 709 in Lecture Notes in Computer Science, pages 421–430.
`Springer-Verlag, 1993. Journal version appears in Algorithmica 18(1).
`6. D. R. Karger and C. Stein. “An ˜O(n2) Algorithm for Minimum Cuts”. In A. Aggarwal,
`editor, Proceedings of the 25th ACM Symposium on Theory of Computing, pages 757–
`765. ACM, ACM Press, May 1993. Journal version appears in Journal of the ACM
`43(4).
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 15 of 39 PageID #: 42954
`Publications of David Ron Karger
`
`7. D. R. Karger and R. Motwani. “Derandomization Through Approximation: An NC
`Algorithm for Minimum Cuts”. In A. Aggarwal, editor, Proceedings of the 25th ACM
`Symposium on Theory of Computing, pages 497–506. ACM, ACM Press, May 1993.
`Journal version appears in SIAM Journal on Computing 26(1).
`8. D. Cutting, D. R. Karger, and J. Pedersen. “Constant Interaction-Time Scatter/Gather
`In Proceedings of the 16th Annual
`Browsing of Very Large Document Collections”.
`International ACM SIGIR Conference on Research and Development in Information
`Retrieval, pages 126–134, July 1993. Pittsburgh, PA.
`9. D. R. Karger. “Random Sampling in Matroids, with Applications to Graph Connec-
`In L. Guibas, editor, Proceedings of the 34th
`tivity and Minimum Spanning Trees”.
`Annual Symposium on the Foundations of Computer Science, pages 84–93. IEEE, IEEE
`Computer Society Press, November 1993. Journal version appears in Mathematical
`Programming B 82(1–2).
`10. D. R. Karger, S. Phillips, and E. Torng. “A Better Algorithm for an Ancient Scheduling
`Problem”. In D. D. Sleator, editor, Proceedings of the 5th Annual ACM-SIAM Sym-
`posium on Discrete Algorithms, pages 132–140. ACM-SIAM, January 1994. Journal
`version appears in Journal of Algorithms 20.
`11. D. R. Karger. “Using Randomized Sparsification to Approximate Minimum Cuts”. In
`D. D. Sleator, editor, Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete
`Algorithms, pages 424–432. ACM-SIAM, January 1994.
`12. D. R. Karger. “Random Sampling in Cut, Flow, and Network Design Problems”. In
`Proceedings of the 26th ACM Symposium on Theory of Computing, pages 648–657. ACM,
`ACM Press, May 1994. Journal version appears in Mathematics of Operation Research
`24(2), 1999.
`13. P. Fizzano, D. R. Karger, C. Stein, and J. Wein. “Job Scheduling in Rings”. In Proceed-
`ings of the 6th Annual ACM-SIAM Symposium on Parallel Algorithms and Architectures,
`pages 210–219. ACM, June 1994. Journal version appears in Journal of Parallel and
`Distributed Computing 45(2).
`14. D. R. Karger and D. Koller. “(De)Randomized Construction of Small Sample Spaces
`in NC”. In S. Goldwasser, editor, Proceedings of the 35th Annual Symposium on the
`Foundations of Computer Science, pages 252–263. IEEE, IEEE Computer Society Press,
`November 1994. Journal version appears in Journal of Computer and System Sciences
`55.
`15. D. R. Karger, R. Motwani, and M. Sudan. “Approximate Graph Coloring by Semidefi-
`nite Programming”. In S. Goldwasser, editor, Proceedings of the 35th Annual Symposium
`on the Foundations of Computer Science, pages 2–13. IEEE, IEEE Computer Society
`Press, November 1994. Journal version appears in Journal of the ACM 45(2).
`16. D. R. Karger and S. Plotkin. “Adding Multiple Cost Constraints to Combinatorial
`Optimization Problems, with Applications to Multicommodity Flows”. In Proceedings
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 16 of 39 PageID #: 42955
`Publications of David Ron Karger
`
`20.
`
`22.
`
`23.
`
`of the 27th ACM Symposium on Theory of Computing, pages 18–25. ACM, ACM Press,
`May 1995.
`17. M. A. Hearst, D. R. Karger, and J. O. Pedersen. “Scatter/Gather as a Tool for Nav-
`igating Search Results”.
`In Proceedings of the AAAI Fall Symposium on Knowledge
`Navigation, 1995.
`18. S. Arora, D. R. Karger, and M. Karpinski. “Polynomial Time Approximation Schemes
`for Dense Instances of NP-Hard Problems”. In Proceedings of the 27th ACM Symposium
`on Theory of Computing, pages 284–293. ACM, ACM Press, May 1995. Journal version
`appears in Journal of Computer and System Sciences.
`19. D. R. Karger. “A Randomized Fully Polynomial Approximation Scheme for the All
`Terminal Network Reliability Problem”. In Proceedings of the 27th ACM Symposium
`on Theory of Computing, pages 11–17. ACM, ACM Press, May 1995. Journal version
`appears in SIAM Journal on Computing 29(2).
`A. A. Bencz´ur and D. R. Karger. “Approximate s–t Min-Cuts in ˜O(n2) Time”.
`In
`G. Miller, editor, Proceedings of the 28th ACM Symposium on Theory of Computing,
`pages 47–55. ACM, ACM Press, May 1996.
`21. D. R. Karger. “Minimum Cuts in Near-Linear Time”. In G. Miller, editor, Proceedings
`of the 28th ACM Symposium on Theory of Computing, pages 56–63. ACM, ACM Press,
`May 1996. Journal version appears in Journal of the ACM 47(1).
`C. C. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. “Experimental
`Study of Minimum Cut Algorithms”. In M. Saks, editor, Proceedings of the 8th Annual
`ACM-SIAM Symposium on Discrete Algorithms, pages 324–333. ACM-SIAM, January
`1997.
`D. R. Karger and R. P. Tai. “Implementing a Fully Polynomial Time Approximation
`Scheme for All Terminal Network Reliability”. In M. Saks, editor, Proceedings of the 8th
`Annual ACM-SIAM Symposium on Discrete Algorithms, pages 334–343. ACM-SIAM,
`January 1997.
`D. R. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. “Con-
`sistent Hashing and Random Trees: Distributed Caching protocols for Relieving Hot
`Spots on the World Wide Web”. In Proceedings of the 29th ACM Symposium on Theory
`of Computing, pages 654–663. ACM, ACM Press, May 1997.
`25. D. R. Karger. “Using Random Sampling to Find Maximum Flows in Uncapacitated
`Undirected Graphs”. In Proceedings of the 29th ACM Symposium on Theory of Com-
`puting, pages 240–249. ACM, ACM Press, May 1997.
`26. C. Young, D. S. Johnson, D. R. Karger, and M. D. Smith. “Near-Optimal Interproce-
`dural Branch Alignment”. In ACM SIGPLAN Conference on Programming Language
`Design and Implementation, pages 183–193, Las Vegas, NV, June 1997. ACM.
`D. Karger, A. Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim,
`L. Matkins, and Y. Yerushalmi. “Web Caching with Consistent Hashing”. In Proceedings
`of the Eighth World-Wide Web Conference, 1999.
`
`24.
`
`27.
`
`*
`
`*
`
`*
`
`*
`
`*
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 17 of 39 PageID #: 42956
`Publications of David Ron Karger
`
`30.
`
`31.
`
`32.
`
`28. S. Arora, M. Grigni, D. Karger, P. Klein, and A. Woloszyn. “A Polynomial-Time Ap-
`proximation Scheme for Weighted Planar Graph TSP”. In H. Karloff, editor, Proceedings
`of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33–41. ACM-
`SIAM, January 1998.
`29. D. R. Karger. “Better Random Sampling Algorithms for Flows in Undirected Graphs”.
`In H. Karloff, editor, Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete
`Algorithms, pages 490–499. ACM-SIAM, January 1998.
`A. A. Bencz´ur and D. R. Karger. “Augmenting Undirected Edge Connectivity in ˜O(n2)
`In H. Karloff, editor, Proceedings of the 9th Annual ACM-SIAM Symposium
`Time”.
`on Discrete Algorithms, pages 500–509. ACM-SIAM, January 1998. Journal version
`appears in Journal of Algorithms 37.
`D. R. Karger and M. Levine. “Finding Maximum Flows in Simple Undirected Graphs
`Seems Faster than Bipartite Matching”. In Proceedings of the 29th ACM Symposium on
`Theory of Computing, pages 69–78, New York, May 23–26 1998. ACM, ACM Press.
`D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, and J. Wein.
`“Techniques for Scheduling with Rejection”.
`In European Symposium on Algorithms
`(Lecture Notes in Computer Science), volume 1461, page 490, 1998.
`33. D. R. Karger, P. N. Klein, C. Stein, M. Thorup, and N. Young. “Optimal Rounding
`Algorithms for a Geometric Embedding of the Multiway Cut Problem”. In Proceedings
`of the 30th ACM Symposium on Theory of Computing, pages 668–677. ACM, ACM
`Press, May 1999.
`34. F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne,
`M. Skutella, C. Stein, and M. Sviridenko. “Approximation Schemes for Minimizing
`Average Weighted Completion Time with Release Dates”. In Proceedings of the 32nd
`Annual Symposium on the Foundations of Computer Science, pages 32–43. IEEE, IEEE
`Computer Society Press, October 1999.
`R. D. Iyer, D. R. Karger, H. Rahul, and M. Thorup. “An Experimental Study of Poly-
`logarithmic Fully-Dynamic Connectivity Algorithms”.
`In Proceedings of ALENEX00:
`Workshop on Algorithm Engineering and Experimentation, January 2000. ALENEX00
`special issue of the Journal of Experimental Algorithmics.
`E. Adar, D. R. Karger, and L. A. Stein. “Haystack: Per-User Information Environ-
`ments”. In Proceedings of the 8th International Conference on Information and Knowl-
`edge Management, pages 413–422, 1999.
`37. M. Thorup and D. R. Karger. “Dynamic Graph Algorithms with Applications”.
`Seventh Scandinavian Workshop on Algorithm Theory, 2000.
`J. Li, J. Janotti, D. S. J. De Couto, D. R. Karger, and R. Morris. “A Scalable Lo-
`In Proceedings of the 6th ACM In-
`cation Service for Geographic Ad-Hoc Routing”.
`ternational Conference on Mobile Computing and Networking (MobiCom 2000), pages
`120–130, Boston, MA, August 2000.
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`35.
`
`36.
`
`38.
`
`In
`
`Redacted
`
`

`

`Case 1:16-cv-00453-RGA Document 495-1 Filed 03/08/18 Page 18 of 39 PageID #: 42957
`Publications of David Ron Karger
`
`39.
`
`40.
`
`41.
`
`42.
`
`D. R. Karger and M. Minkoff. “Building Routing Trees with Incomplete Global Knowl-
`edge”. In Proceedings of the 33rd Annual Symposium on the Foundations of Computer
`Science, pages 613–623. IEEE, IEEE Computer Society Press, November 2000.
`D. W. Engels, J. Feldman, D. R. Karger, and M. Ruhl. “Scheduling Trees with Com-
`munication and Precedence Delays”. In S. R. Kosaraju, editor, Proceedings of the 12th
`Annual ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, January 2001.
`D. R. Karger and N. Srebro. “Learning Markov Networks: Maximum Bounded Tree-
`width Graphs”. In S. R. Kosaraju, editor, Proceedings of the 12th Annual ACM-SIAM
`Symposium on Discrete Algorithms, pages 392–401. ACM-SIAM, January 2001.
`F. Dabek, E. Brunskill, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, and H. Bal-
`akrishnan. “Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service”.
`In Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII),
`Schloss Elmau, Germany, May 2001. IEEE Computer Society.
`I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. “Chord: A
`Scalable Peer-to-peer Lookup Service for Internet Applications”. In Proceedings of the
`ACM SIGCOMM ’01 Conference, pages 149–160, San Diego, California, August 2001.
`F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. “Wide-area cooperative
`storage with CFS”. In Proceedings of the ACM 2001 Symposium on Operating System
`Principles, October 2001.
`D. R. Karger and M. Ruhl. “Finding Nearest Neighbors in Growth Restricted Metrics”.
`In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 741–750.
`ACM, ACM Press, May 2002.
`D. R. Karger and M. S. Levine. “Random Sampling from Residual Graphs”. In Pro-
`ceedings of the 33rd ACM Symposium on Theory of Computing, pages 63–66. ACM,
`ACM Press, May 2002.
`47. E. W. Boyer, K. Shih, D. R. Karger, L. Quang, and P. Case. “Internet Surveillance
`of Pro-drug Websites. I. Incidence of Club Drug Reporting Over a One-Year Period.”.
`Journal of Toxicology: Clinical Toxicology, 39:536, 2001. (abstract).
`48. E. W. Boyer, K. Shih, D. R. Karger, L. Quang, and P. Case. “Internet Surveillance
`of Pro-drug Websites.
`II. Identification of Emerging Drug Use Trends.”. Journal of
`Toxicology: Clinical Toxicology, 39:537, 2001. (abstract).
`49. E. W. Boyer, K. Shih, D. R. Karger, L. Quang, and P. Case. “Internet Surveillance
`of Pro-drug Websites.
`III. Identification of Emerging Drugs of Abuse.”. Journal of
`Toxicology: Clinical Toxicology, 39:537, 2001. (abstract).
`J. Feldman and D. R. Karger. “Decoding