kline center with outliers
Sergei Vassilvitskii
Given a set $X$ of $n$ points in $R^d$, a width $w$,
and an integer $k > 0$, consider the problem of finding
$k$ $d$dimensional cylinders of width $w$ that cover $X$.
By a result of Megiddo and Tamir, the problem
is both NPhard and hard to approximate.
The current best known algorithm
is due to Agarwal and Procopiuc~\cite{AP} which identifies $O(dk \log k)$
$d$cylinders of diameter at most $8w$ in time $O(dnk^3 \log^4 n)$.
We consider the problem of finding a collection of $k$ cylinders
that cover all but an $\epsilon$fraction of the points. The solution
to this problem is interesting in its own right since in many
applications finding clusters that cover most of the data
is often sufficient. We give two simple algorithms for solving this
problem, both covering at least $(1\epsilon)n$ points using O(dk \log
k/eps) and O(k log kd/eps) cylinders respectively.
In this talk I will present the problem in further detail, give the
algorithms and time permitting state some open problems.
This is joint work with Nina Mishra and
Rajeev Motwani.

Computing (Correlated) Equilibria in MultiPlayer
Games
Tim Roughgarden
I will briefly survey some of my recent research on the complexity of computing
equilibriaparticularly correlated equilibriain games with a
large number of players. Such games, in order to be computationally
meaningful, must be presented in some succinct, gamespecific way. I
will discuss a general framework for obtaining polynomialtime
algorithms for optimizing over correlated equilibria in such settings,
with applications including symmetric games, graphical games, and
congestion games. Time permitting, I will also mention complexity
results implying that such algorithms are not possible in certain
other such games.
This is joint work with Christos Papadimitriou.

Knapsack Auctions
Gagan Aggarwal
Motivated by settings such as ad pricing on websites and pricing
satellite
bandwidth, we formulate the knapsack auction problem as follows: a seller
has a certain amount, say K, of a good. Each bidder i has a demand d_i for
the good, and bids b_i for it (the bidder will pay atmost b_i for d_i
amount of good). The goal is design a truthful auction that maximizes
revenue. We use competitive analysis to measure the performance of an
auction. We compare the auction revenue to the optimal "monotone" pricing
revenue  a pricing scheme is called monotone if it offers a higher (or
equal) price to a bidder with higher demand. We design an auction that
achieves C.OPT  h log log log n, where OPT is the revenue of the optimal
monotone pricing scheme, "C" is a constant, "h" is the highest bid and "n"
is the number of winners under the optimal monotone pricing scheme (a
bidder is a winner if it is able to afford the good).
We first design an auction for the unlimited supply case, where the
amount
of available good, K, is infinite. Then, we reduce the limited supply case
to the unlimited supply case with a factor 3 loss in competitive ratio
(and a small additive loss).
This is joint work with Jason Hartline and Andrew Goldberg.

Scalable Program Analysis using Mathematical Programming
Sriram Sankaranarayanan
We present a technique for performing dataflow analysis
over imperative programs. Specifically, our analysis seeks to discover
numerical properties over program variables like variable bounds,
variabledifference bounds, and so on. These properties are extremely
useful in statically checking for common programming bugs
like buffer overflows.
In general, numerical properties can be discovered by analysis using
polyhedra. But such algorithms do not scale because of the inherently
exponential space complexity of the polyhedral manipulations
involved. Our analysis, on the other hand, works by posing repeated
linear optimization queries to a LP solver. The number and
dimensionality of each such query is shown to be polynomial in program
size. The practical performance of our algorithm on a few benchmark
systems is also quite promising. We shall first present our basic
ideas through a simple contextinsensitive analysis for linear
systems. Time permitting, we shall describe various extensions
including extensions to nonlinear programs using semidefinite
programming, handling function calls with context information, and
handling data structures like arrays.
This is work done jointly with Zohar Manna and Henny Sipma.

On the Tractability of Restricted
Disjunctive Temporal Problems
Satish Kumar Thittamaranahalli
We will provide a simple polynomialtime randomized algorithm for
solving
certain restricted (but very useful) kinds of "disjunctions of linear
inequalities" that arise in temporal reasoning and scheduling problems.
The general form of a "disjunctive temporal problem" (DTP) is as
follows.
We are given a set of events {X_0, X_1 ... X_N}, and a set of constraints
{C_1, C_2 ... C_M}. A constraint c_i is a disjunction of the form s_(i,1)
V s_(i,2) ... s_(i,K), where s_(i,j) is a simple temporal constraint of
the form L <= X_b  X_a <= U. Although general DTPs are NPhard to solve,
we will identify the following tractable subclass of DTPsreferred to as
restricted DTPs (RDTPs)that are amenable to simple randomized
algorithms: ``Any c_i is of one of the following types: (Type 1) L <= X_b
 X_a <= U, (Type 2) (L_1 <= X_a <= U_1) V (L_2 <= X_a <= U_2) ... (L_K
<= X_a <= U_K), (Type 3) (L_1 <= X_a <= U_1) V (L_2 <= X_b <= U_2)''. We
will show that RDTPs are also useful in the context of solving general
DTPs.

kserver Optimal Task Scheduling
Problem with Convex Cost Function
Mingjie Lin
We consider a class of kserver optimal task scheduling problems 
partitioning and scheduling N tasks with various realtime constrains
and work loads on k servers with convex task processing cost function
so as to minimize the total task processing cost while still guarantee
satisfaction of all time constrains. This class has broad expressing
power for practical scheduling problems in several areas such as
realtime multimedia wireless transmission
\cite{gamal02,prabhakar02,keslassy03}, CPU energy conservation
\cite{yao95, alenawy04,swaminathan04}, and warehouse order processing
management, et. al.. Our formulation is quite general such that most
previous works can be readily reduced to a special case of the
presented kserver optimal task scheduling problem.
This is an ongoing joint work with Yashar Ganjali, Huan Liu, and
ManCho Anthony So.

Lines in Finite Fields as
Computational Devices
Ilya Mironov, Microsoft Research, SVC
One of the central assumptions in cryptography is the hardness of the
discrete logarithm problem: given g^x find x, where g is an element of a
prime order p. In the adversary can only access the group via an oracle,
which can multiply or divide group elements, the complexity of the
problem is about p^1/2.
Define the complexity of the set S as the number of queries that the
adversary has to ask when x is known to belong to S. We show that the
adversary can be modeled as a set of lines, such that projections of
their intersection points cover S. An open problem is to construct small
sets of high complexity. We show several constructions that get us there
based on ideas from combinatorics and additive number theory.
This is a joint work Anton Mityagin, UCSD, and Kobbi Nissim,
BenGurion
University.

