Joan Feigenbaum

Joan Feigenbaum


Grace Murray Hopper Professor of Computer Science & Economics
Room / Office: Watson 512
Office Address:
51 Prospect Street
New Haven, CT 06511
Mailing Address:
P.O. Box 208285
New Haven, CT 06520
Phone: (203) 432-6432
  • Ph.D., Stanford University
  • B.A., Harvard University


Joan Feigenbaum is the Grace Murray Hopper Professor of Computer Science at Yale University. She received a B.A. in Mathematics from Harvard and a Ph.D. in Computer Science from Stanford. Between finishing her Ph.D. in 1986 and starting at Yale in 2000, she was with AT&T, most recently in the Information Sciences Research Center of the AT&T Shannon Laboratory in Florham Park, NJ. There she established a research group in the emerging area of algorithmics for massive data sets and served as manager of the group for two years.

Professor Feigenbaum's research interests include Internet algorithms, computational complexity, security and privacy, and digital copyright. She has a long-standing interest in fundamental problems in complexity theory that are motivated by cryptology and is co-inventor (with former colleagues Matt Blaze and Jack Lacy) of the security-research area of "trust management." More recently, she has worked on basic algorithms for massive data sets, particularly those generated in network operations and business-to-consumer e-commerce. With collaborators Sampath Kannan, Martin Strauss, and Mahesh Viswanathan, Professor Feigenbaum has devised several highly influential algorithms for network-generated massive data, including a randomized algorithm for deciding whether two streams of router measurements are approximately equivalent and another for deciding whether a stream is close to having the "groupedness" property (a natural relaxation of the sortedness property). Within the area of e-commerce foundations, she has also worked on the interplay of incentives and computation. Using tools from microeconomics and game theory, computer scientists are now developing a theory of "incentive-compatible" distributed computation. In joint work with Arvind Krishnamurthy, Christos Papadimitriou, Rahul Sami, and Scott Shenker, Professor Feigenbaum has studied incentive-compatible protocols for multicast cost/sharing and interdomain routing.

Professor Feigenbaum has an extensive record of distinguished service to the Computer Science community. From 1997 to 2002, she served as Editor-in-Chief of the Journal of Cryptology. She has also been an editorial-board member for the SIAM Journal on Computing, Program Chair for the Crypto 1991 and Complexity 1998 conferences, and Program Committee member for numerous conferences and workshops. Well known for her ability to establish and explicate research priorities, Professor Feigenbaum has given many high-profile, direction-setting, invited talks, including "Security and Privacy in the Information Economy" at the 1997 Grace Hopper Celebration of Women in Computing, "Games, Complexity, and Approximation Algorithms" at the 1998 International Congress of Mathematicians, and "Massive Graphs: Algorithms, Applications, and Open Problems" at the 1999 annual meetings of the American Mathematical Society and the Society for Industrial and Applied Mathematics.

Selected Awards & Honors:

  • Member, Connecticut Academy of Science and Engineering, 2013 – Present
  • Fellow, American Association for the Advancement of Science, 2012 – Present
  • Connecticut Technology Council "Women of Innovation," 2012
  • Fellow, Association for Computing Machinery, 2001 – Present

Selected Publications:

  • J. Feigenbaum and B. Ford, "Multiple Objectives of Lawful-Surveillance Protocols," in Proceedings of the 25th International Workshop on Security Protocols, Lecture Notes in Computer Science, volume 10476, Springer, 2017, pp. 1–8.
  • J. Feigenbaum and B. Ford, "Seeking Anonymity in an Internet Panopticon," Communications of the ACM  58:10 (October 2015), pp. 58–69.
  • J. Feigenbaum, A. D. Jaggard, and R. Wright, "Towards a Formal Model of Accountability," in Proceedings of the 14th ACM New Security Paradigms Workshop, 2011, pp. 45–56.
  • J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, "A BGP-based Mechanism for Lowest-Cost Routing," Distributed Computing 18 (2005), pp. 61–72.
  • "Testing and Spot Checking of Data Streams," with S. Kannan, M. Strauss, and M. Viswanathan, Algorithmica 34:67-80, 2002.
  • "Sharing the Cost of Multicast Transmissions," with C. Papadimitriou and S. Shenker, Journal of Computer and System Sciences, 63:21-41, 2001 (special issue on Internet Algorithms).
  • "Compliance Checking in the PolicyMaker Trust-Management System," with M. Blaze and M. Strauss, Proceedings of the 2nd Financial Crypto Conference, Lecture Notes in Computer Science, v. 1465, Springer, Berlin, 1998, pp. 254-274.
  • "Random Debaters and the Hardness of Approximating Stochastic Functions," with A. Condon, C. Lund, and P. Shor, SIAM Journal on Computing 26:369-400, 1997.