Theory Discussion Group, Fall 2003

Tentative time and place: Wednesday 5-6pm, Upson 5126

(Here are the webpages from previous semesters: Fall 02 Spring 03.)

I've assembled a list of possible discussion topics.

Sep 3 Ara Hayrapetyan
Paper: A tight bound on approximating arbitrary metrics by tree metrics.
I'll be presenting a recent result published in STOC'03 by Jittat Fakcharoenphol, Satish Rao and Kunal Talwar, in which the authors show that any n point metric space can be embedded into a distribution of tree metrics with expected distortion of O(log n). This result is tight as there exist metric spaces where every tree embedding must have a distortion of at least Omega(log n).
Sep 10 No TDG (no speaker)
Sep 17 Anirban Dasgupta
I will talk about some recent results on spectral analysis : finding out hidden structures in a random graph model using eigenvector properties . After giving an intro to the random graph models used, and the eigenvector techniques, I will talk about the problem faced by these algorithms on graph models with arbitrary degree distributions e.g. power law . Finally I will present a way to get around this problem of degree distributions . This is joint work with Frank Mcsherry and John Hopcroft . Also, this is in progress, so comments are solicited.
Sep 24 Hubie Chen
Title: Periodic Constraint Satisfaction
I'll give a gentle introduction to the constraint satisfaction problem (CSP) and the associated theory that has been used to study CSP complexity. Then, I'll discuss a generalization of CSPs -- periodic constraint satisfaction problems. In the periodic CSP, a large (possibly infinite) network of constraints is specified implicitly by a finite set of "generating" constraints, and the question is to decide whether or not the implicit large constraint network is satisfiable. Interestingly, there appears to be a wide dichotomy in the complexity of such problems (polynomial time versus undecidable). The presentation will be based on the paper
Oct 1 Martin Pl
Title: Cake Cutting
My talk will be based on the ESA 2003 paper "A lower bound for cake cutting" by Ji Sgall and Gerhard Woeginger. They discuss a model with n players, in which every player has her own evaluation of different parts of the cake. Their goal is to devise a protocol to cut the cake into n pieces, so that each player gets a "fair" (at least 1/n) share according to that player's evaluation. Under some simplifying assumptions they prove that each fair protocol has complexity Omega(n log n).
Regardless of complexity considerations, an interesting open question seems to be whether cake cutting has a fair protocol for which truthtelling is the dominant strategy.
Oct 8 Alex Slivkins
TITLE: Min-Quotient Cuts in Planar Graphs

Sort of a follow-up to the last Yuval's lecture.
Suppose a cut C divides the graph into two pieces S1, S2 where S1 has smaller weight. Then the quotient of C is defined as cost(C)/weight(S1). Accordingly, the quotient is a (decreasing) measure of the quality of a cut. Finding the min-quotient in general graphs is strongly NP-hard; the best known approx ratio is O(log n). In planar graphs the problem becomes more tractable. I will talk about the following results:

  • a nice and simple pseudo-polynomial algorithm for edge cuts (STOC'93)
  • [maybe] fully polynomial 3.5-approx for edge-cuts (STOC'92)
  • a much harder pseudo-polynomial (3.5+eps)-approx for node-cuts (STOC'03)
The plan is to show some nice graph theory :).
Eyal Amir, Robert Krauthgamer, Satish Rao. Constant factor approximation of vertex-cuts in planar graphs. STOC'03
J.K. Park and C.A. Phillips. Finding minimum-quotient cuts in planar graphs. STOC'93
Satish Rao. Faster algorithms for finding small edge cuts in planar graphs. STOC'92
Oct 15 No TDG due to FOCS (11-14 Oct.)
Oct 22 No speaker -- no TDG
Oct 29 Zoya Svitkina
I will present the paper A sublinear algorithm for weakly approximating edit distance by Tugkan Batu and Funda Ergun and Joe Kilian and Avner Magen and Sofya Raskhodnikova and Ronitt Rubinfeld and Rahul Sami from STOC 2003.
The authors propose a randomized algorithm that runs in sublinear time and determines, with high probability, whether the two input strings are "close" or "far" from each other in terms of their edit distance. For a parameter alpha<1, the algorithm outputs "close" if the edit distance is O(n^alpha), and "far" if the edit distance is Omega(n), where n is the length of the strings. The idea of the algorithm is to recursively compare shorter and shorter substrings of one string to another, which works because if the two strings are close, then there will be good matches for most of their substrings.
Nov 5 Chaitanya Swamy
I'll talk about algorithms for getting a spanning tree with low maximum degree. Specifically we are given a connected graph G and want to return a spanning tree whose maximum degree is as small as possible. This problem is NP-Hard. Amazingly however, there exists a polynoimal-time algorithm that returns a spanning tree whose maximum degree is at most (an additive) 1 off the optimal - the best that one could hope for unless P=NP. I'll talk about this algorithm and a simpler algorithm which gives an additive O(log n) approximation, both of which are based on local-search. An interesting open question is whether one can get similar results when we have an edge weighted graph and want a minimum spanning tree of as small maximum degree as possible. For this problem we only know of an additive O(log n) approximation algorithm, generalizing the O(log n) additive approximation result for the unweighted (or 0-weighted) case.
Nov 12 Tom Wexler
I'm going talk about "Simpler and Better Approximation Algorithms for Network Design", a paper from STOC '03 by Anupam Gupta, Amit Kumar, and Tim Roughgarden. The authors show how to use some (relatively) simple randomized algorithms to get good approximation guarantees for a number of related problems; Connected Facility Location (CFL), Virtual Private Network Design (VPND), and Single Sink Buy-at-Bulk Network Design (SSBB). I'll talk about their CFL result and possibly one of the other two problems. Its a nice example of the power/simplicity of randomization.
Nov 19 Elliot Anshelevich
The problem of Second Hamiltonian Cycle is as follows. Suppose we are given as input a graph and a Hamiltonian cycle in this graph. Does a second distinct (not necessarily disjoint) Hamiltonian cycle exist in this graph? A classic result by Cedric Smith says this is always true when the graph is 3-regular. This was later extended by Thomason to include all graphs of only odd degree, and later by Thomassen to include all r-regular graphs, except for a finite set of r's. All of these are existence results, however, and we cannot use them to actually find a Hamiltonian cycle. In 1999, Bazgan et al showed that in 3-regular graphs, there exists an EPTAS for Second Hamiltonian Cycle. I plan to discuss all the results stated above.
Nov 26 No TDG -- Thanksgiving
Dec 3 Ara Hayrapetyan

Last updated Sep 3, 2003