- Manhattan Distance. How are foreigners supposed to know about the structure of streets in New York? What's wrong with grid distance?
- Las Vegas Algorithms. I found this one a little unfair, after all Monte Carlo algorithms came first. Still today might not Macau algorithms make sense?
- Arthur-Merlin Games. A British reference by a Hungarian living in the US (László Babai who also coined Las Vegas algorithms). Still the Chinese might not know the fables. Glad the Europeans don't remember the Pat and Vanna terminology I used in my first STOC talk.
- Alice and Bob. The famous pair of cryptographers but how generically American can you get. Why not Amare and Bhati?
I have two minds here. We shouldn't alienate or confuse those who didn't grow up in an Anglo-American culture. On the other hand, I hate to have to try and make all terminology culturally neutral, you'd just end up with technical and ugly names, like P and NP.
Interesting point. I think keeping the original names is probably justified here. As the scientific communities around the world become more prominent the names will (probably) become more reflective of the demographics of the world as a whole. Indeed, there may well be Macau algorithms in the future. It seems rather pointless to rename MA/AM because it would be confusing to non-Anglo-Americans in favour of what would most likely be an equally confusing but less memorable technical name. Besides, the point seems rather moot given essentially all (computer) science is done in English. This seems far more of a barrier to non-Anglo-Americans than potentially confusing names.
ReplyDeleteA potentially interesting comparison is the medical literature. Much of medicine around the world (parts of continental Europe*/India/Africa) is taught in English, using English textbooks and terminology. There are a huge number of concepts/diseases/body parts which derive their name from Greek/Latin (why not Sanskrit/high Arabic/Hebrew?) or after European/American doctors that discovered them. We could potentially rename them in a more culturally neutral way. However, ultimately, they need to be named something, in some language, and this choice will inevitably be culturally bias in some way. I don't think that the case for "cultural neutrality" is sufficient to rewrite a huge amount of literature and simultaneously partially erase the people who discovered so much. That's just my opinion though. No doubt this comparison is flawed in many ways!
*typically places with a small population such as Finland/Norway. I'm not sure how widespread this is more generally.
I'm all for 'grid' distance. Or sender/receiver for Alice/Bob. Call a thing what it is, not some arbitrary name. We've all moved on from Abelian to commutative.
ReplyDeleteI have fond memories of studying for theory quals trying to map the distinction between Las Vegas and Monte Carlo (very arbitrary), and somewhat differently Arthur and Merlin (How does the myth work? Is Arthur the verifier? A king would seem too dumb to do such dirty work). Note that 'fond' = 'exhilarated at something awful because I didn't die'. Full disclosure: native speaker, only seen Las Vegas and Monte Carlo on TV, all knowledge of King Arthur is from Monty Python and the Holy Grail.
There is some benefit for attaching a story as a mnemonic to meaning. But an academic's name is both meaningless and vain.There's a certain amount of arbitrariness in mathematical language (-any- language), but call things what they are instead of some opaque vanity plate or inside joke.
Just for the other side, in defense of opaque labels, for those who are second language/2nd culture learners, it's -all- an arbitrary learning experience. In some sense they have it easier because they are always having to struggle to learn the new vocabulary because it's all new and opaque at the beginning. So they actually have it easier not having to worry about how to intuitively map some ephemeral cultural artifact, the labels are just another thing to learn whether evocative to a native speaker or not. Also, what a great way to learn the local culture by arbitrarily inserting complicated childhood myths.
I think a lot of hard to remember names die out. There's absolutely no logic in which is Las Vegas and Monte Carlo, I find it much easier to remember ZPP and BPP, which I do not find technical and ugly, once you know what they stand for. Instead of Manhattan distance most people say l1 (L1) distance. Arthur-Merlin perfectly captures what happens and would be hard to explain otherwise, so I guess this name will live on (but of course you have IP for the unbounded rounds version).
ReplyDeleteI worry that the ham sandwich theorem is not kosher.
ReplyDeleteDon't worry, the spicy chicken theorem almost definitely is.
DeleteThanks for the pointer! I like the footnote on p.1: "Vegetarian readers are welcome to substitute the chicken filet with a peeled potato."
DeleteSpicy latke theorem ;)
DeleteAlice and Bob are not technical, you can easily use other names (including names not starting with the letters 'A' and 'B'), and I have in fact done so. I think most people don't really care so they just stick with Alice and Bob.
ReplyDeleteManhattan distance of course is just l_1, and I don't think I've seen anyone talk about Manhattan distance in years.
I agree that names like P, NP, ZPP, BPP, and so on are nicer than names like Las Vegas and Monte Carlo and Manhattan. To be frank, I find the latter to be kind of childish, though I can see why some might find the charm in them.
interesting points. I want to add Post machine and Hintikka set.
ReplyDeleteWe should rename NC. Sure, we still rememer who Nick Pippenger is, but for how much longer?
ReplyDeleteLas Vegas and Monte Carlo are awful. Not to mention Atlantic City algorithms, though maybe that one's easier to remember as "Not LV or MC so it must be the one that means probably correct and probably polynomial".
For the Alice/Bob nonsense I propose we use Ahmad and Bo-Wan, with third wheel Carena and eavesdropper Ivanka.
Ok, scrap "Turing machine"...
ReplyDeleteThere are more serious issues with theoretical computer science than the origin of its technical names names:
ReplyDelete1. STOC/FOCS are seen as the top venues of the field but in reality they are not bona-fide worldwide conferences but mostly U.S. based events.
Notice what happens with some top venues in other areas of computer science:
IJCAI (Seattle->Acapulco->Hyderabad->Pasadena->Barcelona->Beijing->Buenos Aires->NYC->Melbourne->Stockholm->Macau)
Conference such as LICS, AAMAS, COLT, INFOCOM could produce similar (fairly geographically diverse) lists. STOC/FOCS/ITCS/SODA: mostly not.
2. Many computer science conferences are using double blind reviewing. If there is one measure that could promote more diversity, this is it. Another one would be, of course, to make the PC's more diverse, not biased towards top 10 schools in the U.S.
Lack of geographic (and program committee) diversity are more serious issues than naming our algorithms Monte Carlo/Las Vegas, or using Pat and Vanna in our proofs.
3. The whole conference-based system is biased against those without resources, shy, or who cannot/does not want to participate for some other reason to conferences (see Glencora Boradaille's recent post). Couple that with lack of anonymity in submissions and you get a status quo with significant prestige-related biases, of the sort uncovered (for other areas of science) by Aaron Clauset.
The Chicken McNugget Theorem:
ReplyDeletehttps://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem