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 NP-hard 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.

Tim Roughgarden

I will briefly survey some of my recent research on the complexity of computing equilibria---particularly correlated equilibria---in games with a large number of players. Such games, in order to be computationally meaningful, must be presented in some succinct, game-specific way. I will discuss a general framework for obtaining polynomial-time 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.

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.

Sriram Sankaranarayanan

We present a technique for performing data-flow analysis over imperative programs. Specifically, our analysis seeks to discover numerical properties over program variables like variable bounds, variable-difference 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 context-insensitive analysis for linear systems. Time permitting, we shall describe various extensions including extensions to non-linear programs using semi-definite programming, handling function calls with context information, and handling data structures like arrays.

This is work done jointly with Zohar Manna and Henny Sipma.

Satish Kumar Thittamaranahalli

We will provide a simple polynomial-time 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 NP-hard to solve, we will identify the following tractable subclass of DTPs---referred 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.

Mingjie Lin

We consider a class of k-server optimal task scheduling problems --- partitioning and scheduling N tasks with various real-time 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 real-time 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 k-server optimal task scheduling problem.

This is an ongoing joint work with Yashar Ganjali, Huan Liu, and Man-Cho Anthony So.

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, Ben-Gurion University.