|
|
Milestone Year
2002
Explicit Lossless Expanders
Imagine you would like to design a computer network with many terminals,
each linked to a few other terminals such that information can spread quickly.
Such a network is formalized by the notion of a graph,
which is a combinatorial notion central to mathematics and computer science.
Especially useful graphs in this setting are known
as Expander Graphs which are sparse (the overall number of links is small)
but still highly connected. In particular, each two terminals
in an expander are connected by a short sequence of links
(and in fact, by many such paths).
Expander graphs have many applications in computer science
(and mathematics) beyond robust network designs, some very surprising.
For example, expanders yield error correcting codes
(which are a major ingredient in all modern communication protocols),
and ways of extracting "pure" randomness
(an important resource of computation) from the imperfect sources
that are available.
How can we design expander graphs? One method is using randomization:
We can connect each terminal to a few other random terminals.
But there are many advantages to a deterministic construction
such that the graphs have concise description and it is easy to
determine for each terminal who are its neighbors.
A celebrated sequence of works gave beautiful and mathematically
deep constructions. However, all of these constructions had
an inherent limitation that restricts their applicability.
The algebraic techniques at the basis of all these constructions
could not imply a stronger type of expanders known as lossless expanders:
In a lossless expander most of these links going out from any
(not too large) set of terminals will connect to new terminals;
in other words, only few links will be "lost" by connecting to
the same set of terminals.
In 2002, a WIS scientist and his collaborators solved
the long standing open problem by giving the first
explicit construction of very sparse lossless expanders.