Capital Area Theory Seminar: Spring 2006

Schedule

CATS will usually meet on Friday 1:00pm-2:00pm AVW 3258 but some talks may be at a different place and time.

For additional information send email to Samir Khuller.

If you want to receive announcements of upcoming talks join the theory-local mailing list.

Talks from previous semesters

• 2005 : Fall | Spring
• 2004 : Fall | Spring
• 2003 : Fall | Spring
• 2002 : Fall | Spring
• 2001 : Fall
• 2000 : Fall | Spring
• 1999 : Fall | Spring
• 1998 : Fall | Spring
• 1997 : Fall | Spring
• 1996 : Summer and Fall | Spring
• 1995 : Fall

Other cats

Combinatorial Algorithms Test Sets Collaborative Agent Technology System Computing: The Australasian Theory Symposium

Abstracts

Quadratic Lower Bounds on Matrix Rigidity

ABSTRACT

The rigidity of a matrix $A$ with respect to the rank bound $r$ is the minimum number of entries of $A$ that must be changed to reduce the rank of $A$ to or below $r$. It is a major unsolved problem (Valiant, 1977) to construct ``explicit" families of $n \times n$ matrices of rigidity $n^{1+\delta}$ for $r=\epsilon n$, where $\epsilon$ and $\delta$ are positive constants. In fact, no superlinear lower bounds are known for explicit families of matrices for rank bound $r=\Omega(n)$. In this talk, we present the first optimal, $\Omega(n^2)$, lower bound on the rigidity of two ``algebraically explicit'' families of complex matrices with respect to the rank bound $r=c n$, where $c$ is an absolute positive constant. The entries of these matrix families are (i) square roots of $n^2$ distinct primes and (ii) primitive roots of unity of prime orders for the first $n^2$ primes. Our proofs use an algebraic dimension concept introduced by Shoup and Smolensky (1997) and a generalization of that concept.

Combinatorial Algorithms for the Data Migration Problem

ABSTRACT

Given a graph G=(V,E) we are to schedule the edges such that no two adjacent edges are scheduled at the same time. We consider two variants of this problem where our objective is to minimize the average completion time of either the edges or the vertices.

I will describe combinatorial algorithms for these problems:

• Edge variant: improved \sqrt{2}-approximation for bipartite graphs.
• Vertex variant: fast 3-approximation algorithm for general graphs.

To Fill or not to Fill: the Gas Station Problem

ABSTRACT

In this paper, we study several routing problems that generalize shortest paths and the traveling salesman problem. We consider a more general model that incorporates the actual costs in terms of gas prices.

We have a vehicle with a given tank capacity of U. In fact, we will assume that U is the distance the vehicle may travel on a full tank of gas. We assume that at each vertex v gas may be purchased at a price of c(v). The objective is to find the cheapest route to go from s to t ,or the cheapest tour visiting a given set of locations.

(Joint work with Samir Khuller and Julian Mestre)

Theoretical challenges in the design of advertisement auctions

ABSTRACT

The Internet is probably the most important technological creation of our times. It provides many immensely useful services to the masses for free, including such essentials as web search, web mail, and web portals. These services are expensive to maintain, and depend upon advertisement revenue to remain free. One of the most effective ways to allocate advertisement space on the web is through auctions. In this talk, I will discuss some of the theoretical challenges in the design of online advertisement auctions, and will present some of our recent results addressing these issues. In particular, I will focus on mechanism design for budget-constrained bidders, multi-unit auctions for perishable goods with unknown supply, and dynamics of bid optimization.

How many colors are needed to randomly color a graph? A Markov chain approach.

ABSTRACT

A (proper) graph coloring is a function which assigns a color to each vertex of a graph, so that no two adjacent vertices receive the same color. A simple greedy strategy can produce such a coloring in linear time, using at most D+1 colors where D is the maximum degree of the graph. If we want to produce not just any coloring, but a uniformly random coloring, in polynomial time, how many colors are needed?

To address this question, we will use the Markov chain Monte Carlo approach (MCMC). This is a general and powerful technique for sampling random elements from combinatorially-defined sets. Other well-known applications of MCMC include Google's PageRank, many dynamical models in statistical physics (e.g. for gas dynamics, ferromagnetism, etc), and approximating the permanent.

I will describe a simple Markov chain whose state space is proper graph colorings, and whose distribution converges to uniform as the number of steps tends to infinity. Simulating this chain for a finite number of steps is the best known algorithm for sampling graph colorings approximately uniformly at random. I will tell you about a sequence of results for this chain, each of which introduced a new general technique for the analysis of MCMC algorithms.

Randomized Online Matching

ABSTRACT

Consider the problem of assigning consultants to projects. Each consultant should be assigned a project, in such a way that the cost of these assignments is minimized. Cost could represent the travel time of the consultant to the project site, or the ability of the consultant to complete the task. This problem is an instance of the minimum-cost matching problem: one of the most important problems in computer science. Substantial previous work has lead to efficient algorithms to compute these matchings.

However, the consultant-assignment problem is naturally online, in that we do not know what the list of projects will be in advance. Projects arrive one-by-one, and as each project appears we must assign a consultant. The requirement that we make assignments as we go, without prior knowledge of the list of projects, makes the problem substantially more difficult. Prior work (by Khuller, Mitchell, and Vazirani) has demonstrated that this problem is intractable if the costs are arbitrary. If the costs form a metric (satisfying symmetry and triangle inequality, for example distances along a sphere) then the best possible deterministic guarantee is that the cost of our matching is at most 2K-1 times the optimum, where K is the number of assignments.

In this talk, I will describe the first randomized algorithm for the online matching problem. By using a simple randomized greedy technique combined with prior work in metric embeddings (in particular the result of Fakcharoenphol, Rao, and Talwar), I will guarantee that the cost of our matching is at most O(log^3 K) times the optimum. This talk is based on the paper "Randomized Online Algorithms for Minimum Metric Bipartite Matching" which appeared at SODA 2006, and represents joint work with Akash Nanavati and Laura Poplawski.

Approximate Range Searching

ABSTRACT

The range searching problem consists of preprocessing a set of data points in d-dimensional space in order to efficiently compute the sum of the weights of the data points lying inside a query range. For our approximate version, we assume that all data points lie in the unit box and we can allow a point within distance epsilon from the range boundary to be either inside or outside the range. Assuming d is constant, we show that if the ranges are halfspaces, we can answer queries in constant time using O(1/epsilon^d) space (notice that there is no dependency on the number of points). We present data structures for different range shapes, including spherical, simplex, orthogonal and convex ranges.

(joint work with David Mount)

Irit Dinur's Breakthrough

ABSTRACT

Irit Dinur has achieved a major breakthrough by presenting a substantially simplified proof of the PCP Theorem ("The PCP Theorem by Gap Amplification", to appear in STOC 2006). In this first talk, I will review the background including the PCP Theorem, the paper's approach, and preliminaries on graph powering, expanders, random walks etc. The second talk, on April 28, will mostly cover the main technical result, the Soundness Amplification Lemma.

A tight bound on approximating arbitrary metrics by tree metrics

ABSTRACT

In this paper, we show that any n-point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Omega(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.

Reference: A tight bound on approximating arbitrary metrics by tree metrics, STOC '03, Jittat Fakcharoenphol, Satish Rao, Kunal Talwar.