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 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 TBA For directions, please see http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46) To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny Organizers: Yevgeniy Dodis dodis@... Tal Rabin talr@... Baruch Schieber sbar@... Rocco Servedio rocco@... ======================================================================= 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) Approximation Algorithms 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 -------------------------------------------------------------------------

--

Posted By GASARCH to Computational Complexity at 11/10/2008 12:22:00 PM