Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] STOC reminder- TODAY!/ NYU Theory Day

Expand Messages
  • GASARCH
    TWO ITEMS: I) Reminder: STOC submission abstracts due today. II) New York Area Theory Day Organized by: NYU/IBM/Columbia External sponsorship by: Google
    Message 1 of 1 , Nov 10, 2008
    • 0 Attachment
      TWO ITEMS:

      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@...
      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)
      
      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
      
      -------------------------------------------------------------------------
      
      
      
      
      


      --
      Posted By GASARCH to Computational Complexity at 11/10/2008 12:33:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.