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]

9 thoughts on “Terminology

  1. how about just “almost unbiased”, in analogy with “almost k-wise independent”? the latter is well-known to be a consequence of the former, and “almost k-wise independence” is somewhat commonly used — even in the title of Alon-Goldreich-Hastad-Peralta. (and i am really glad you brought up the Naor-Naor paper, which is among my personal favorites.)


  2. “\epsilon-biased” = “biased by at most \epsilon”

    Seems like perfectly good terminology to me…

  3. There’s an old joke – um… two elderly women are at a Catskill mountain resort, and one of ’em says, “Boy, the food at this place is really terrible.” The other one says, “Yeah, I know; and such small portions.” Well, that’s essentially how I feel about your post. 🙂

    And to address the point: the problem with the term epsilon-biased generators is much more severe than what you point out. It’s missing some vital information. We should instead refer to them as “epsilon-biased against parities”, or “epsilon-biased against linear functions”, so that one can also speak about being “epsilon-biased against branching programs”, “epsilon-biased against polynomials”, “epsilon-biased against k-juntas”, and so on.

    (by the way, isn’t epsilon-biased against k-juntas exactly the same concept as epsilon-almost k-wise independent?)

    And I actually like to call them epsilon-fooling polynomials, epsilon-fooling branching programs, etc.

    P.S. it’s completely okay that the uniform distribution is 1/10-biased . 1/10 stands for an upper-bound on the biasedness. It is the same as saying that sorting integers is in EXP.

  4. My point (addressing Anonymi #2 and #3) is that it is more natural to say $\epsilon$-goodproperty, to mean that one has the goodproperty except for an error parameter $\epsilon$, rather than to say $\epsilon$-badproperty, to mean that there is at most an $\epsilon$ amount of badproperty. (Or rather than to say $(1-\epsilon)$-goodproperty, to mean that there is at least a $(1-\epsilon)$ amount of goodproperty.)

    This is consistent for example with the use of $\epsilon$-regular in Szemeredi’s theorem, or of $\epsilon$-quasirandomness in various combinatorial applications.

    Note also #4’s use of “$\epsilon$-fooling,” which I like, and that follows the same convention.

    [I hope nobody is taking this discussion seriously, or any more seriously than a proposal to let Esperanto be the national language of France, on the basis that it does not have irregular verbs.]

  5. [I hope nobody is taking this discussion seriously, or any more seriously than a proposal to let Esperanto be the national language of France, on the basis that it does not have irregular verbs.]

    and i hope nobody took my comment seriously — after all, we do need some mathematical notation to define the concept precisely at some point. 🙂


  6. Why do you say we will never change the names of PP or PCP? Maybe there should be a formal group of zookeepers who do more than maintain a website, but who actually try to come up with a good and (at least more) standardized naming scheme for complexity classes.

    Okay, okay, maybe that’s a little too far. But it’s not too much to hope that some names might change for the better. After all, “recursion theory” changed to “computability theory” in the last 20 years, a good many decades after it was entrenched in the hearts, minds, and funding requests of recursion theorists everywhere. (Of course, there are still some who call it recursion theory, but the term has clearly gone out of fashion.)

  7. Yes, why can’t we change the names ever? I think it would be good for the field to fix the worst few. In the long run (100 years from now), if these complexity classes are still being studied, I hope that some group will have fixed the names up.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s