Interesting comments by Aram Harrow (March 5, 2011)

I generally agree with your latest Opinion, but in fact computer scientists care very much about explicitness of expanders. If you want to use them for an error-correcting code on n bits, then there are exp(n) vertices in the expander, and an explicit expander (like the L-P-S construction) is crucial. These codes allow for very high rates and linear or near-linear time encoding and decoding. Googling for "expander codes" gives many hits too. Here's a random recent paper

Expanders are also used in CS for data structures, derandomization, and probably other things too, almost always relying on the explicitness property to be useful.

A longer list of applications is here. Most, but not all, require the "explicit" property (which in other settings might be called "implicit").

aram


Back to Opinion 113 of Doron Zeilberger