A beautiful journey to the Theory of Computation
8:15 AM to 5:30 PM
Davis Auditorium 530 W 120th Street New York, NY 10027 USA
Various
We are happy to invite you to Columbia University to celebrate Christos Papadimitriou’s contributions to science on the occasion of his 70th birthday, through a mix of talks, panels, and fun activities. One of world’s leading computer scientists, Christos is best known for his work in computational complexity, helping to expand its foundations, methodology and reach. Using computation as a scientific lens, he has also made seminal contributions to biology and the theory of evolution, economics and game theory—where he helped found the field of algorithmic game theory, artificial intelligence, robotics, databases, networks and the Internet, and more recently the study of the brain. In this 3 day celebration, we will celebrate the wealth of areas that Christos’s work has influenced directly, as well as areas that have been influenced, are being influenced, or might be influenced by the “algorithmic lens.”
Day one:
09:00am Scott Shenker
09:45am Michael I. Jordan
11:00am Anna Karlin
11:45am Michael Collins
02:00pm AI panel moderated by Jitendra Malik
04:00pm Elias Koutsoupias
04:45pm Rump session
http://papafest.cs.columbia.edu/
Add to GMail
A beautiful journey to the Theory of Computation
8:15 AM to 5:30 PM
Davis Auditorium 530 W 120th Street New York, NY 10027 USA
Various
We are happy to invite you to Columbia University to celebrate Christos Papadimitriou’s contributions to science on the occasion of his 70th birthday, through a mix of talks, panels, and fun activities. One of world’s leading computer scientists, Christos is best known for his work in computational complexity, helping to expand its foundations, methodology and reach. Using computation as a scientific lens, he has also made seminal contributions to biology and the theory of evolution, economics and game theory—where he helped found the field of algorithmic game theory, artificial intelligence, robotics, databases, networks and the Internet, and more recently the study of the brain. In this 3 day celebration, we will celebrate the wealth of areas that Christos’s work has influenced directly, as well as areas that have been influenced, are being influenced, or might be influenced by the “algorithmic lens.”
Day two:
09:00am Noam Nisan
09:45am Santosh Vempala
11:00am Eva Tardos
11:45am Sanjeev Arora
02:00pm Adi Livnat
02:45pm John Tsitsiklis
04:00pm Leslie Valiant
04:45pm Prabhakar Raghavan
06:30pm Reception and rock concert at Prohibition
http://papafest.cs.columbia.edu/
A beautiful journey to the Theory of Computation
8:15 AM to 12:40 PM
Davis Auditorium 530 W 120th Street New York, NY 10027 USA
Various
We are happy to invite you to Columbia University to celebrate Christos Papadimitriou’s contributions to science on the occasion of his 70th birthday, through a mix of talks, panels, and fun activities. One of world’s leading computer scientists, Christos is best known for his work in computational complexity, helping to expand its foundations, methodology and reach. Using computation as a scientific lens, he has also made seminal contributions to biology and the theory of evolution, economics and game theory—where he helped found the field of algorithmic game theory, artificial intelligence, robotics, databases, networks and the Internet, and more recently the study of the brain. In this 3 day celebration, we will celebrate the wealth of areas that Christos’s work has influenced directly, as well as areas that have been influenced, are being influenced, or might be influenced by the “algorithmic lens.”
Day three:
09:00am Theory panel moderated by Richard Karp
11:00am Jon Kleinberg
11:45am Umesh Vazirani
12:30 Closing remarks
http://papafest.cs.columbia.edu/
Towards an improved approximation algorithm for the Travelling Saleswoman Problem
11:40 AM to 12:40 PM
CS Department 451
Anna Karlin, University of Washington
The traveling saleswoman problem (TSP) is one of the most celebrated and well-studied NP-complete problems we know. A classic result from Christofides in the 70s tells us that a fast algorithm exists which returns a solution at most 3/2 times worse than the optimal. Since then, however, no better approximation algorithm has been found. Finding a polynomial time algorithm which breaks this 3/2 barrier is a famous open problem in theoretical computer science. In this talk, we will give an overview of research towards this goal and describe a new sub-3/2 approximation algorithm for an interesting special case, so-called "half integral" TSP instances.
This is joint work with Nathan Klein and Shayan Oveis Gharan.
From Ethical Challenges of Intelligent Systems to Embedding Ethics in Computer Science Education
11:40 AM to 12:40 PM
CSB 451
Barbara Grosz, Harvard University
Computing technologies have become pervasive in daily life, sometimes bringing unintended but harmful consequences. For students to learn to think not only about what technology they could create, but also whether they should create that technology and to recognize the ethical considerations that should constrain their design, computer science curricula must expand to include ethical reasoning about the societal value and impact of these technologies. This talk will describe Harvard's Embedded EthiCS initiative, a novel approach to integrating ethics into computer science education that incorporates ethical reasoning throughout courses in the standard computer science curriculum. It changes existing courses rather than requiring wholly new courses. The talk will begin with a short description of my experiences teaching the course "Intelligent Systems: Design and Ethical Challenges" that inspired the design of Embedded EthiCS. It will then describe the goals behind the design, the way the program works, lessons learned and challenges to sustainable implementations of such a program across different types of academic institutions.
Add to GMail