The diameter of randomly perturbed digraphs
and some applications
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
outdegree, it is NLcomplete. By XORing an arbitrary bounded outdegree
digraph with a sparse random digraph R = G(n,\epsilon n) we obtain a
``smoothed'' instance. We show that, with high probability, a logspace
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 klinked 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 klinked
digraphs is NPcomplete for k >= 2. We describe a polynomial time
algorithm for bounded degree digraphs which accepts klinked graphs with
high probability, and rejects all graphs which are at least \epsilon n
edges away from being klinked. 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.

An Experimental Analysis of Change Propagation
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 reexecuted 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 treecontraction as a solution to the
dynamic trees problem and present an experimental evaluation of the
approach. The applications considered include path
queries, subtree queries, leastcommonancestor queries, maintenance
of centers and medians of trees, nearestmarkedvertex queries,
semidynamic minimum spanning trees, and the maxflow algorithm of
Sleator and Tarjan.
This is joint work with Umut Acar, and Guy Blelloch.

Undirected STConnectivity in LogSpace
Tim Roughgarden
Presenting the latest most celebrated result in complexity theory (see paper by
Omer
Reingold)
Paper abstract: We present a deterministic, logspace algorithm that solves
stconnectivity in
undirected graphs. The previous bound on the space complexity of undirected stconnectivity
was log^{4/3}() obtained by Armoni, TaShma, Wigderson and Zhou. As undirected
stconnectivity is complete for the class of problems solvable by symmetric,
nondeterministic, logspace computations (the class SL), this algorithm implies that SL=L
(where L is the class of problems solvable by deterministic logspace computations).

Near Optimal Online Auctions
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 BarYossef, 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

Finding small roots of modular polynomials
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 LenstraLenstraLovasz approximation
algorithm for the shortestvector 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
HowgraveGraham'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.

Enumerating vertices of polyhedra:
Application to Linear Systems Analysis.
Sriram Sankaranarayanan
A polyhedron has two descriptions. It may be described as the
intersection of a set of halfspaces (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.

Approximating the CutNorm via
Grothendieck's
Inequality
ManCho Anthony So
Recently, Alon and Naor (Approximating the CutNorm 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 wellknown combinatorial optimization problems, as well as
problems in control theory. For instance, it includes MAX3CUT 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.

From Optimal Limited Supply To Unlimited
Supply Auctions
Bob McGrew
We investigate the class of singleround, sealedbid auctions for a set
of
identical items to bidders who each desire one unit. We adopt the
worstcase competitive framework defined by Goldberg et al. that compares
the profit of an auction to that of an optimal singleprice 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 limitedsupply 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 bestknown 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.

Will This Talk Ever End?
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/semidecidable 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 semidecidable.

