Abraham Flaxman, CMU

The central observation of this talk is that if \epsilon n random edges are added to any n node connected graph or digraph then the resulting graph has diameter O(log n) with high probability. We apply this to smoothed analysis of algorithms and property testing.

Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for graphs with bounded out-degree, it is NL-complete. By XORing an arbitrary bounded out-degree digraph with a sparse random digraph R = G(n,\epsilon n) we obtain a ``smoothed'' instance. We show that, with high probability, a log-space algorithm will correctly determine if a smoothed instance is strongly connected. The algorithm consists of, for every pair (s,t), checking if a series of random walks starting at s ever reaches t (and can be derandomized by carefully exploring vertices within a certain distance). We also show that if NL is not contained in L then no heuristic can recognize similarly perturbed instances of (s,t)-connectivity.

Property Testing: A digraph is called k-linked if for every choice of 2k distinct vertices s_1, ... ,s_k,t_1,... ,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r=1,... ,k. Recognizing k-linked digraphs is NP-complete for k >= 2. We describe a polynomial time algorithm for bounded degree digraphs which accepts k-linked graphs with high probability, and rejects all graphs which are at least \epsilon n edges away from being k-linked. The algorithm consists of perturbing the graph by adding \epsilon n/2 random edges, and then for every choice of terminal pairs, checking if a series of vertex disjoint random walks starting from s_1, ... ,s_k ever reach t_1,....,t_k.

This is joint work with Alan Frieze.

Jorge Vittes

Change propagation is a technique for automatically adjusting the output of an algorithm to changes in the input. The idea behind change propagation is to track the dependences between data and function calls, so that, when the input changes, functions affected by that change can be re-executed to update the computation and the output. Change propagation makes it possible for a compiler to dynamize static algorithms. The practical effectiveness of change propagation, however, is not known. In particular, the cost of dependence tracking and change propagation may seem significant.

The presentation presents some experimental evidence that change propagation performs well when compared to direct implementations of dynamic algorithms. We implement change propagation on tree-contraction as a solution to the dynamic trees problem and present an experimental evaluation of the approach. The applications considered include path queries, subtree queries, least-common-ancestor queries, maintenance of centers and medians of trees, nearest-marked-vertex queries, semi-dynamic minimum spanning trees, and the max-flow algorithm of Sleator and Tarjan.

This is joint work with Umut Acar, and Guy Blelloch.

Tim Roughgarden

Presenting the latest most celebrated result in complexity theory (see paper by Omer Reingold)

Paper abstract: We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and Zhou. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that SL=L (where L is the class of problems solvable by deterministic log-space computations).

Jason Hartline, Microsoft Research

This talk will present a subset of results recently given in a SODA 2005 paper on {\em online auctions}. The online auction problem was originally considered by Bar-Yossef, Hildrum, and Wu in 2002. Blum et al. showed how to use techniques for {\em learning from expert advice} to give an auction that is approximately optimal but with an additive loss term of $O(h \log \log h)$ when the bidders' valuations are on the interval $[1,h]$ which is known in advance. We improve on this result using a new expert learning algorithm (and analysis) due to Kalai. Using this new algorithm we obtain near optimal additive loss of $O(h)$ and do not need to know the range of bidder valuations in advance. We also apply these results to a new auction problem, the {\em attribute auction}.

In this talk I will derive Kalai's expert learning algorithm from first principles and show how it gives improved results for the online auction problem. I will also briefly talk about the attribute auction problem.

Joint work with Avrim Blum. The paper is available at

Hovav Shacham

Consider a modulus N of unknown factorization. How do we go about finding roots of a polynomial f(x) modulo N? (Or, more generally, modulo some factor of N?)

In this talk, we give Coppersmith's method for computing, in polynomial time, roots of the equation

f(x) = 0 mod b where b divides N, and b > N^\beta

that are small: less than (roughly) N^{\beta^2 / deg(f)}.

We begin by presenting the Lenstra-Lenstra-Lovasz approximation algorithm for the shortest-vector problem on lattices.

We then present Coppersmith's method. This method uses the LLL algorithm to obtain from the modular polynomial f(x) a polynomial g(x) that has the same small root x0 _over_the_integers_; we discuss of Howgrave-Graham's sufficient condition for a polynomial to have this property.

Finally, we consider some applications of Coppersmith's method to cryptanalyzing certain classes of RSA keys.

Our exposition is a simplified version of that given in Alexander May's thesis.

Sriram Sankaranarayanan

A polyhedron has two descriptions. It may be described as the intersection of a set of half-spaces (constraint representation) or the set generated by a set of vertices, rays and lines (generator representation). Converting from one representation to another (also known as the vertex enumeration problem) is an inherently hard problem since each representation can be exponentially larger than the other representation.

High dimensional polyhedra are frequently used in the analysis of linear systems. The greatest bottleneck for the analysis is the repeated conversion from one representation to another. In this talk, I will briefly describe some algorithms for this conversion. I will then discuss techniques for efficiently implementing polyhedral analysis of linear hybrid systems by avoiding these conversions.

Joint work with Michael Colon.

Man-Cho Anthony So

Recently, Alon and Naor (Approximating the Cut-Norm via Grothendieck's Inequality, STOC04) have shown how to use (proofs of) the Grothendieck inequality in functional analysis to analyze certain semidefinite programming (SDP) relaxations. In this talk we shall apply their idea and consider SDP models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, it includes MAX-3-CUT where some of the edges can have negative weights. Our analysis is based on Rietz's proof of Grothendieck's inequality, and it yields an $(k\sin(\pi/k))^2/(4\pi)$ approximation algorithm for the discrete problem where the decision variables are $k$-ary and the objective matrix is positive semidefinite. This technique also provides a simpler analysis for an $\pi/4$ approximation algorithm for the continuous problem where the objective function is positive semidefinite.

This is joint work with Jiawei Zhang and Yinyu Ye.

Bob McGrew

We investigate the class of single-round, sealed-bid auctions for a set of identical items to bidders who each desire one unit. We adopt the worst-case competitive framework defined by Goldberg et al. that compares the profit of an auction to that of an optimal single-price sale that sells at least two items. In this paper, we first derive an optimal auction for three items, closing an open question. Second, we show that the form of this auction is independent of the competitive framework used. Third, we propose a schema for converting a given limited-supply auction into an unlimited supply auction. Applying this technique to our optimal auction for three items, we achieve an auction with a competitive ratio of 3.25, which improves upon the previously best-known competitive ratio of 3.39.

Finally, we generalize a result characterizing optimal auctions and extend our understanding of the nature of the optimal competitive auction by showing that the optimal competitive auction occasionally offers prices that are higher than all bid values.

Aaron Bradley

The universal halting problem for a program loop asks whether the loop terminates on all input. Traditionally, such a question is answered by showing that a function over the program state is a ranking function for the loop. In this talk, we formally define ranking functions and show several examples of their use. We then introduce the flavor of current research on termination. A research result usually takes the form ``it is decidable/semi-decidable whether a loop in class X has a ranking function of form Y.''

Yet Floyd and others showed decades ago that every terminating loop has a ranking function. Why, then, do we care about class X of loops and form Y of ranking functions? In fact, constructing a ranking function may require using an incomplete logical language -- in general, first order logic with fixpoints. We show that this theoretical limitation is harsh in practice: termination for a simple class of linear loops is not semi-decidable.