Computer Science Colloquium
The IBM Research NYU/Columbia Theory Day
Friday, December 5, 2008
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 10012
Program
9:30  10:00 Coffee and bagels
10:00  10:55 Prof. Assaf Naor
Approximate Kernel Clustering
10:55  11:05 Short break
11:05  12:00 Prof. Joe Mitchell
Approximation Algorithms for some Geometric Coverage and Connectivity Problems
12:00  2:00 Lunch break
2:00  2:55 Dr. Jonathan Feldman
A Truthful Mechanism for Offline Ad Slot Scheduling
2:55  3:15 Coffee break
3:15  4:10 Prof. Yishay Mansour
Regret Minimization for Global Cost Functions with Applications to Job Scheduling
For directions, please see: http://cs.nyu.edu/csweb/Location/directions.html
For additional directions, please see: http://cs.nyu.edu/csweb/Location/directions.html
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
TalRabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Serverdio rocco@cs.columbia.edu
Abstracts
Approximate Kernel Clustering
Prof. Assaf Naor
New York University
In the kernel clustering problem we are given a large n times n
positive semidefinite matrix A=(a_{ij}) with \sum_{i,j=1}^n a_{ij}=0
and a small k times k positive semidefinite matrix B=(b_{ij}). The
goal is to find a partition S_1,...,S_k of {1,...n} which
maximizes the quantity
\sum_{i,j=1}^k (\sum_{(p,q)\in S_i\times S_j} a_{pq}) b_{ij}.
We study the computational complexity of this generic clustering
problem which originates in the theory of machine learning. We design
a constant factor polynomial time approximation algorithm for this
problem, answering a question posed by Song, Smola, Gretton and
Borgwardt. In some cases we manage to compute the sharp approximation
threshold for this problem assuming the Unique Games Conjecture
(UGC). In particular, when B is the 3 times 3 identity matrix the UGC
hardness threshold of this problem is exactly 16*pi/27. We present and
study a geometric conjecture of independent interest which we show
would imply that the UGC threshold when B is the k times k identity
matrix is (8*pi/9)*(11/k) for every k >= 3.
Joint work with Subhash Khot.
Approximation Algorithms for some Geometric Coverage and Connectivity Problems
Prof. Joe Mitchell
Stony Brook University
We examine a variety of geometric optimization problems. We describe
some recent progress in improved approximations algorithms for several
of these problems, including the TSP with neighborhoods, relay
placement in sensor networks, and visibility/sensor coverage. We
highlight many open problems.
A Truthful Mechanism for Offline Ad Slot Scheduling
Dr. Jonathan Feldman
Google
Targeted advertising on web pages is an increasingly important
advertising medium, attracting large numbers of advertisers and users.
One popular method for assigning ads to various slots on a page (for
example the slots along side web search results) is via a realtime
auction among advertisers who have placed standing bids for clicks.
These "position auctions" have been studied from a gametheoretic
point of view and are now well understood as a singleshot game.
However, since web pages are visited repeatedly over time, there are
global phenomena at play such as supply estimates and budget
constraints that are not modeled by this analysis.
We formulate the "Offline Ad Slot Scheduling" problem, where
advertisers are scheduled beforehand to slots on a web page for
portions of the day. Advertisers specify a daily budget constraint,
as well as a perclick bid, and may not be assigned to more than one
slot on the page during any given time period. We give a scheduling
algorithm and a pricing method that amount to a truthful mechanism
under the utility model where bidders try to maximize their clicks,
subject to their personal constraints. In addition, we show that the
revenuemaximizing schedule is not truthful, but has a Nash
equilibrium whose outcome is identical to our mechanism. Our
mechanism employs a descendingprice auction that maintains a solution
to a machine scheduling problem whose job lengths depend on the price.
Joint work with Muthu Muthukrishnan, Eddie Nikolova and Martin Pal.
Regret Minimization for Global Cost Functions with Applications to Job Scheduling
Prof. Yishay Mansour
Google and Tel Aviv University
We consider standard regret minimization setting where at each time
step the decision maker has to choose a distribution over $k$
alternatives, and then observes the loss of each alternative. The
setting is very similar to the classical online job scheduling setting
with three major differences:
(1) Information model: in the regret minimization setting losses are
only observed after the actions (assigning the job to a machine) is
performed and not observed before the action selection, as assumed in
the classical online job scheduling setting,
(2) The comparison class: in regret minimization the comparison class
is the best static algorithm (i.e., distribution over alternatives)
and not the optimal offline solution.
(3) Performance measure: In regret minimization we measure the
additive difference to the optimal solution in the comparison class,
in contrast to the ratio used in online job scheduling setting.
Motivated by load balancing and job scheduling, we consider a global
cost function (over the losses incur by each alternative/machine),
rather than simply a summation of the instantaneous losses as done
traditionally in regret minimization. Such global cost functions
include the makespan (the maximum over the alternatives/machines) and
the $L_d$ norm (over the alternatives/machines).
The major contribution of this work is to design a novel regret
minimization algorithm based on calibration that guarantees a
vanishing average regret, where the regret is measured with respect to
the best static decision maker, who selects the same distribution over
alternatives at every time step. Our results hold for a wide class of
global cost functions. which include the makespan and the $L_d$ norms,
for $d>1$. In contrast, we show that for concave global cost
functions, such as $L_d$ norms for $d<1$, the worstcase average
regret does not vanish.
In addition to the general calibration based algorithm, we provide
simple and efficient algorithms for special interesting cases.
This is a joint work with Eyal EvenDar and Shie Mannor.
Computer Science Colloquium
Looking Glass: Supporting Learning from Peer Programs
Caitlin Kelleher, Washington University in St. Louis
Friday, December 5, 2008 11:30 p.m.
WWH Room 1302
New York, NY 10012
Host
Ken Perlin
Synopsis
Computer programming has become a fundamental tool that enables progress across a broad range of disciplines including basic science, communications, and medicine. Yet, Computer Science is failing to attract the number of students necessary to sustain progress both within the discipline and in those disciplines supported by computer science. Some recent research has focused on creating programming environments that introduce young students to computer programming in a motivating context. One of these systems, Storytelling Alice motivates middle school children, particularly girls, to learn programming in order to build animated stories. In a formal study, we found that 51% of Storytelling Alice users versus 17% of Generic Alice users snuck extra time to keep programming. While a motivating context for learning computer programming is necessary to increase the number of young students who learn to program, it is not sufficient. For many prehigh school students, formal opportunities to learn computer science simply do not exist. We are currently working on a new system called Looking Glass which maintains storytelling as a motivating context and focuses on developing user interface support that enables middle school aged children to easily and effectively teach themselves using programs created by peers. Looking Glass will incorporate tools that enable users to identify sections of peer written programs that interest them and then follow automatically generated tutorials to learn how to create the selected sections of those programs in their own context. In this talk, I will describe our proposed framework for supporting users in learning from peercreated programs and present early results from an exploratory study of novice programmers searching for code in unfamiliar programs.
Bio
Caitlin Kelleher is currently an Assistant Professor of Computer Science at Washington University in St. Louis. She received her bachelor’s degree in Computer Science from Virginia Tech and her Ph.D. in Computer Science from Carnegie Mellon University with Professor Randy Pausch. Caitlin was a National Science Foundation Graduate Fellow.
Joint CS & ITP Event
Computer Graphics as a Telecommunication Medium
Vladlen Koltun, Stanford University
Friday, December 5, 2008 6:30 p.m.
721 Broadway (ITP/Tisch), Room 447
New York, NY 10012
Host
Chris Bregler
Synopsis
I will argue that the primary contribution of computer graphics in the next decade will be to enable richer social interaction at a distance. The integration of realtime computer graphics and largescale distributed systems will give rise to a rich telecommunication medium, currently referred to as virtual worlds. The medium provides openended facetoface communication among adhoc groups of people in custom environments and decouples shared spatial experiences from geographic constraints.
I will outline a research agenda for enabling and advancing the medium. The three driving themes are system architectures, content creation, and interaction. System architectures aim to support the medium at planetary scale. Content creation aims to enable untrained participants to create highquality threedimensional content. Interaction aims to make virtual world communication seamless and natural. I will demonstrate preliminary results in each area.
Bio
Vladlen Koltun is an Assistant Professor of Computer Science at Stanford University. He directs the Virtual Worlds Group, which explores how scalable virtual world systems can be built, populated, and used. His prior work in computational geometry and theoretical computer science was recognized with the NSF CAREER Award, the Alfred P. Sloan Fellowship, and the Machtey Award.
top  contact webmaster@cs.nyu.edu
