Joan Feigenbaum
Grace Murray Hopper Professor of Computer Science

B.A., Mathematics, Harvard, 1981
Ph.D., Computer Science, Stanford, 1986
Joined Yale Faculty 2000
Personal Homepage

Office Location: AKW 512
Telephone: 203.432.6432

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.

Representative Publications:
	"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.