[Lowerbounds, Upperbounds]

SPEAKER: Vijay V. Vazirani
TIME: Wednesday 12-1pm, November 29, 2006
PLACE: NSH 1507
TITLE: New Market Models and Algorithms

ABSTRACT:

The notion of a “market'’ has undergone a paradigm shift with the Internet — totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner.

In view of these new realities, the study of market equilibria, an important, though essentially non-algorithmic, theory within Mathematical Economics, needs to be revived and rejuvenated with new models, ideas, and an inherently algorithmic approach.

In this talk, I will give a feel for the exciting work going on on this front and present new results on resource allocation markets. Interestingly enough, this work has also contributed handsomely to the theory of algorithms itself. In particular, the highly successful primal-dual schema from exact and approximation algorithms, which was so far used for combinatorially solving special classes of linear programs, has been extended to solving nonlinear convex programs.

This talk is meant for a general audience.

It is based on the following three papers:
http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/adwords.pdf
http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG.pdf
http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG2.pdf

SPEAKER: Prasad Chebolu
TIME: Thursday 4:30-5:30 pm, November 16th, 2006
PLACE: PPB 300
TITLE: Thesis Proposal: Topics in Random Graphs

Thesis Committee: Alan Frieze(chair), Anupam Gupta, R Ravi

Abstract: We study the hamiltonicity property of a new class of random graphs- random lifts in both undirected and directed graphs. In the undirected case, we show that for sufficiently large h>0 random lifts of K_h and K_{h,h} are Hamiltonian. In the case of directed graphs, we obtain a similar result for the complete directed graph.

We also study the average performance of the greedy matching algorithm in sparse random hypergraphs. We are currently working on developing a matching algorithm for sparse random graphs which runs in time O(n) with high probability.

As future work, we would like to obtain conditions under which strong connectivity holds in random lifts of digraphs.

This proposal includes joint work with Kelley Burgin, Colin Cooper, Alan Frieze and Pall Melsted.

Friday, November 17th, 2006, 3:30 pm
Wean Hall 7220

Broadcasting on trees: Beliefs, Evolution and Reconstruction

Elchanan Mossel
UC Berkeley

Broadcasting processes on trees play a fundamental role in various algorithmic inference problems including: The reconstruction of evolutionary trees in biology, the reconstruction of language evolution in linguistics, network tomography and in the analysis of message passing algorithms such as Belief Propagation and Warning Propagation.

In the talk I will survey several theoretical and applied developments in this area obtained using and extending techniques from discrete probability and statistical physics.

SPEAKER: Don Sheehy
TIME: Wednesday 12-1pm, November 15, 2006
PLACE: NSH 1507
TITLE: Flips in Computational Geometry

ABSTRACT:
In this talk, we will be looking at a basic primitive in computational geometry, the flip. Also known as bistellar flips, edge-flips, rotations, and Pachner moves, this local change operation has been discovered and rediscovered in a variety of fields (thus the many names) and has proven useful both as an algorithmic tool as well as a proof technology. For algorithm designers working outside of computational geometry, one can consider the flip move as a higher dimensional analog of the tree rotations used in binary trees. I will survey some of the most important results about flips with an emphasis on developing a general geometric intuition that has led to many advances.

When I was a kid, I was told that a book could gain immortality when people referred to it without even mentioning its title. At that time I wasn’t sure what that meant.

As I grew up, I started to hear about legends of the Green Dragon and the Red Dragon that soar over the great land of Computer Science…

After some twenty years, this semester, the Purple Dragon has finally made its debut to take over the reign of the Red Dragon.

But somehow, deep inside, I felt something looks “wrong” ever since I laid my sight on its cover. I couldn’t identify the subtle cause.

And this morning, ah ha! I finally realized—the computer has disappeared! Indeed, everything else like the Sword of LALR Generator are still there. The computer, however, has disappeared.

I can only imagine that the Knight has an UMPC mounted behind the Shield on his/her forearm. Or perhaps, with the advancement of technology in the last twenty years, the battlefield is now the Matrix.

P.S. Seriously, parsing has definitely advanced in the last twenty years. For a great theory-meets-practice story, you can read about ANTLR. It’s fascinating.

Friday, November 10th, 2006, 3:30 pm
Wean Hall 7220

Eden Chlamtac
Princeton University

Abstract

We describe an algorithm which colors any 3-colorable graph using O(n^0.2074) colors, thus improving the algorithms of Karger, Motwani and Sudan, and Blum and Karger from almost a decade ago. The previous best known algorithm used O(n^{3/14}) colors. We build on these results, which combined semidefinite
programming (SDP) relaxations (specifically, vector chromatic number) with some combinatorial techniques.

We demonstrate a better relation between vector chromatic number and true chromatic number. While this already gives some improvement, we obtain our best result by working with stronger SDP relaxations (e.g. by adding “odd-cycle constraints”). Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao and Vazirani.

This is joint work with Sanjeev Arora and Moses Charikar.

Recently I have finally switched to a ThinkPad X41 Tablet for my everyday computing need. I said “finally” because I actually had the machine since more than a year ago (Sept 2005), but it had more than a couple issues that kept me from relying on it solely. I remember being asked on a trip why I brought two laptops along.

The good news is that Microsoft has fixed two of my issues over the summer. If you are using a X41 tablet as well (already there are five in my group), here they are:

• Insufficient System Resources Exist to Complete the API during hibernation: hot fix 909095
• The mouse pointer or pen pointer behavior is irregular in Windows XP Tablet PC Edition 2005: hot fix 920295

The latter is particularly important since it makes the tablet a lot more responsive when the CPU is under load. I can’t imagine how I could have lived with a “jumpy” cursor for over a year…

Now if only someone makes a fast and reliable 1.8″ harddrive…

SPEAKER: Virginia Vassilevska
TIME: Wednesday 12-1pm, November 8, 2006
PLACE: NSH 1507

TITLE: A dominance approach to weighted graph problems

ABSTRACT:

Fast matrix multiplication allows us to obtain faster algorithms for many graph problems. A notable example is that of detecting a triangle in a graph - the naiive algorithm runs in O(n^3), while cubing the adjacency matrix gives an O(n^2.38) algorithm. Other problems that have benefitted from fast matrix multiplication include graph perfect matching, unweighted APSP, linear programming.

Most of these problems are unweighted, and it is unclear how to apply the matrix multiplication techniques to their weighted counterparts. We show how to use a different kind of matrix product, the dominance product, to solve some weighted problems such as finding a maximum weighted triangle in a graph, computing bits of the distance product and finding the bottleneck distances between all pairs of vertices.

Title: New Results and Open Problems for Deletion Channels and Related Synchronization Problems
Michael Mitzenmacher, Harvard University

Place: NSH 3305
Time: Monday Nov 6, noon

Abatract:

At this point, it seems that most everything is known about the basic channels studied in information theory. For the i.i.d. (independent and identically distributed) binary erasure channel and the i.i.d. binary symmetric error channel, the capacity has long been known, and there are very efficient encoding and decoding schemes that are near capacity.

The situation is very different for the i.i.d. binary deletion channel. With this channel, the sender sends n bits, and each bit is deleted with some fixed probability p. So, for example, the sender might send 10110010, and the receiver obtains 1100. The i.i.d. binary deletion channel is perhaps the most basic channel that incorporates the challenge of synchronization. Surprisingly, even the capacity of the deletion channel remains unknown!

In this talk, I will survey what is known about the deletion channel, focusing on our recent work on bounds on the capacity. The main result is that the for any probability p, the deletion channel has capacity at least (1-p)/9. Hence, the capacity of the deletion channel is always within a constant factor of the erasure channel (which has capacity (1-p)). We also discuss the many remaining open problems in the area of synchronization channels.

Joint work with Eleni Drinea.

Friday November 3, 2006
Wean 7220, 3:30PM

L1 Embedding for Low Bandwidth Graphs

Adam Meyerson
UCLA

We introduce the first embedding of graphs of low bandwidth into L1, with distortion depending only upon the bandwidth. We extend this result to a new graph parameter called tree-bandwidth, which is very similar to (but more restrictive than) treewidth. This represents the first constant distortion embedding of a non-planar class of graphs into L1. Our results make use of a new technique that we call iterative embedding in which we define coordinates for a small number of points at a time.

Joint work with Douglas E. Carroll and Ashish Goel.