I) Reminder: STOC submission abstracts due today.
II)
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.
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
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
TBA
For directions, please see
here
and
here
(building 46)
To subscribe to our mailing list,
follow instructions at
here
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Servedio rocco@cs.columbia.edu
=======================================================================
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
(Google)
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)
TBA
-------------------------------------------------------------------------
No comments:
Post a Comment