Monday, November 10, 2008

STOC reminder- TODAY!/ NYU Theory Day


I) Reminder: STOC submission abstracts due today.


                       New York Area Theory Day
                    Organized by:  NYU/IBM/Columbia
                    External sponsorship by: Google
                       Friday, December 5, 2008

The Theory Day will be held at
Courant Institute of Mathematical Sciences,
New York University, 251 Mercer Street,
Auditorium 109, New York.


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
                 Approx Algs 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

For directions, please see
(building 46)

To subscribe to our mailing list,
follow instructions at

Yevgeniy Dodis
Tal Rabin
Baruch Schieber
Rocco Servedio


Prof. Assaf Naor
(New York University)

Approximate Kernel Clustering

In the kernel clustering problem we are
given a large n times n positive semi-definite
matrix A=(a_{ij}) with \sum_{i,j=1}^n a_{ij}=0
and a small k times k positive semi-definite
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)*(1-1/k) for every k >= 3.

Joint work with Subhash Khot.


Prof. Joe Mitchell
(Stony Brook University)

Approx Algs for some Geometric
Coverage and Connectivity Problems
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.


Dr. Jonathan Feldman

A Truthful Mechanism for
Offline Ad Slot Scheduling

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 real-time
auction among advertisers who have
placed standing bids for clicks.
These "position auctions" have been
studied from a game-theoretic
point of view and are now well
understood as a single-shot 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 per-click 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
revenue-maximizing schedule is not
truthful, but has a Nash
equilibrium whose outcome is identical
to our mechanism.  Our
mechanism employs a descending-price
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.


Prof. Yishay Mansour
(Google and Tel Aviv University)



No comments:

Post a Comment