The law of small numbers is that there are not enough small numbers for all of the tasks that are assigned to them. That makes some math cranks find patterns which are really only caused by not enough small numbers around. One such crank kept finding the number 57 in events related to the American Revolutionary war. The fallacy is that if you look hard enough ANY number would work.

At the LLL workshop it was noted that LLL stands for both Local Lovasz Lemma (my wife asked ``an entire workshop about a lemma?'') or the Lensta-Lenstra-Lovasz algorithm. Here we see that there aren't quite enough sequences of letters, hence some get used twice. Of course in this case it helps that Lovasz is brilliant.

The only other example I now of two well known theorems with the same initials of authors is AKS:

AKS primality testing: Agrawal-Kayal-Sazena test of primality in poly time

and

AKS sorting network: Ajtai-Komlos-Szemeredi O(log n) sorting network.

AKS primality gets 13,500 hits

AKS sorting network gets 39,100 hits

Are there other pairs of well known results where the initials are the same?

(This may depend on what you call ``well known'')

When someone says AKS do you think primality or sorting network?

It may depend on your age and your field. I think of the Ajtai-Komlos-Szemeredi upper bound R(3,k) \le O(k^2/log(k)). I tend to NOT count that as another collision of initials since its the exact same authors as the other paper.

PCP: Post Correspondence Problem or Probabilistically Checkable Proofs?

ReplyDeleteA collision that I discovered when I checked what talks were up:

ReplyDeletePCP=Probabilistically Checkable Proof

PCP=Post Correspondence Problem

There is also a recent paper by An-Kleinberg-Shmoys on the TSP path problem.

ReplyDeletePCP seems like a good example of an acronym that can mean two very different things, both widely known in computer science (and without any common author).

ReplyDeleteAlso AKS = Ajtai-Kumar-Sivakumar, the first singly exponential (2^n) algorithm for the Shortest Vector Problem in n-dimensional lattices.

ReplyDeleteBottom line: if you review a paper/proposal by AKS, accept it.

For AKS, I don't think about either of your two choices, because it's "Komlos", not "Kolmos". More precisely, it's "Komlós".

ReplyDeleteFixed to Komlos.. Thanks.

DeleteAKS primes = 122000 hits.

ReplyDeleteI thought AKS is used for referring to extremely difficult to understand algorithms and is abbreviating a German expression like "algorithmus klieg schwierig" (not sure about K).

ReplyDeleteAnother example, when an acronym is used in quite a few unrelated fields:

ReplyDeleteATM = Alternating Turing Machine

ATM = Asynchronous Transfer Mode

ATM = Automated Teller Machine

ATM = Adobe Type Manager

ATM = Air Traffic Management

ATM = Anti-Tank Missile

ATM = Area Training Manager

ATM = Automatic Timing Mechanism

ATM = Atmospheric Transport Model

ATM = Air Turbine Motor

ATM = Association of Texas Midwives

ATM = Acoustic Telemetry Modem

ATM = Automated Theorem Prover

and probably a number of others...

If you're going to go there then there's the obvious one that makes certain complexity theorists sound like drug dealers (which also happens to collide with an idea in computability as pointed out by two Anons above)

DeleteDefinitely AKS makes me think primes, not sorting network. Similarly PCP = probabilistically checkable proof.

ReplyDeleteActually, TSP is a good example.

ReplyDeleteTravelling Salesman Problem

Time Stamp Protocol

Telecommunications Service Provider