As a sequel to that I note the following: The theorem is not in EITHER Goldreich's Complexity book or Arora-Barak's Complexity book. One of the following is true:
- Gasarch is right and Goldreich and Arora-Barak are wrong. It should have been in their books.
- Gasarch is wrong and Goldreich and Arora-Barak are right. Its okay that its not in their books.
- It is in the book but Gasarch couldn't find it.
When I taught Graduate Algorithms (I really did!) I taught Yao's MST algorithm that ran in time O(|E|log log |V|). The students asked me WHY this was important (there were better algorithms available). Then I realized that I taught it only because Samir Khuller taught it when he taught the class, so I asked him why it was important. He said it very much impressed him when he was a graduate student.
The contents of the Goldreich book and Arora-Barak book are influenced by a deep understanding of the field, and not by things that impressed them in their youth.
Is Mahaney's theorem important? The real question might be compared to what?. As the number of things that you absolutely have to have in a course grows, at some point, something has to be tossed out.