Terminology

Different communities have different traditions for terminology. Mathematicians appropriate common words, like ring, field, scheme, ideal,... and the modern usage of the term bears no connection with the everyday meaning of the word. Physicists have a lot of fun with their sparticles and their strangeness and charm and so on. Theoretical computer scientists, like the military, and NASA, prefer acronyms.

We have some isolated examples of felicitous naming. Expander, for example, is great: it sounds right and it is suggestive of the technical meaning. Extractor is my favorite, combining a suggestion of the meaning with a vaguely threatening sound. I think it's too bad that seedless extractor has come to pass, because it evokes some kind of device to get grape juice. (I was on the losing side that supported deterministic extractor.)

Unfortunate namings are of course more common. Not only is the complexity class PP embarrassing to pronounce, but its name, derived from Probabilistic Polynomial time, is a poor description of it. By analogy with #P and $\oplus$P, it should be called MajP.

I heard the story of a famous (and famously argumentative) computer scientist complaining to one of the authors of the PCP theorem about the term PCP, which stands for Probabilistically Checkable Proof. "I too can define a probabilistic checker for SAT certificates," he supposedly said, "with probability half check the certificate, with probability half accept without looking at it." The point being that the terminology emphasizes a shortcoming of the construction (the probabilistic verification) instead of the revolutionary feature (the constant query complexity). Personally, I would prefer Locally Testable Proof.

Of course we will never change the name of PP or PCP, and the seedless extractors are here to stay, but there is one terminology change for which I'd like to start a campaign.

Naor and Naor constructed in 1990 a pseudorandom generator whose output is secure against linear tests. They called such a generator $\epsilon$-biased if the distinguishing probability of every linear test is at most $\epsilon$. Such generators have proved to be extremely useful in a variety of applications, most recently in the Bogdanov-Viola construction of pseudorandom generators again degree-2 polynomials.

Shall we start calling such generators $\epsilon$-unbiased? Seeing as it is the near lack of bias, rather than its presence, which is the defining feature of such generators?

(I know the reason for the Naor-Naor terminology: zero-bias generator makes perfect sense, while zero-unbiased makes no sense. But how about the fact that it is technically correct to say that the uniform distribution is $\frac {1}{10}$-biased?)

[Update: earlier posts on the same topic here and here]