## Three exciting algorithmic talks at STOC'12

- Routing in Undirected Graphs with Constant Congestion
by Julia Chuzhoy
- Improving Chrisofides' Algorithm for the s-t Path TSP
by Hyung-Chan An, Robert Kleinberg, David B. Shmoys
- Multiplying Matrices Faster Than Coppersmith-Winograd
by Virginia Vassilevska Williams

#### Oded's comments

It was the PC's idea [not mine :-)] to lump-up these three talks
is a plenary session, and it was indeed an excellent idea.
In fact, this session illustrates how STOC should look like:
A focus on few results that are believed to deserve the attention
of the entire community, and bringing the entire community together.
Keeping with this spirit I have included also the third work in
this choice, although it has appeared already
as choice Nr 83.

The first work presents an efficient algorithm for finding
``edge disjoint'' paths with congestion $c=14$ for a given
set of source-sink pairs.
The solution found is within a polylog factor from the optimal,
and (up to the degree of the polynomial) this is the best one can hope for.
(Previously such an approximation level was only achievable
for polyloglog congestion.)
The algorithm is based on a new notion of relaxed embedding,
and on efficiently so embedding an expander in the graph.
Julia, who gave an excellent talk, concluded by announcing
a recent improvement that sets $c$ to 2.

The second work refers to st-TSP which amounts to finding a path TSP
between two given endpoints, as opposed to standard (circuit) TSP.
For twenty years, the best known approximation, for general metric,
was $5/3$ (as opposed to $3/2$ for circuit TSP),
and the current work improves it to 1.6181 (the Golden ratio).
The begging challenge now is to break the 3/2 barrier for circuit TSP.

The improvement in the third work is in the third digit after
the decimal point but it is for (the exponent of) matrix multiplication.
(See choice Nr 83.)
Virginia's slides, delivered by Satish Rao,
ended with ``Let's prove omega=2''...

Back to
list of Oded's choices.