Finding a maximum likelihood tree is hard.
Online algorithms for market clearing.
Combining expert advice in reactive environments.
Using expander graphs to find vertex connectivity.
New hardness results for congestion minimization and machine scheduling.
Logarithmic hardness of the undirected edge-disjoint paths problem.