tag:blogger.com,1999:blog-3722233.post7206224659206310774..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Law of small numbers and lettersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-68828444395193955612014-06-09T03:54:18.211-05:002014-06-09T03:54:18.211-05:00Actually, TSP is a good example.
Travelling Sales...Actually, TSP is a good example.<br /><br />Travelling Salesman Problem<br />Time Stamp Protocol<br />Telecommunications Service ProviderPseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43412146731154012112014-06-04T23:23:02.941-05:002014-06-04T23:23:02.941-05:00Definitely AKS makes me think primes, not sorting ...Definitely AKS makes me think primes, not sorting network. Similarly PCP = probabilistically checkable proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17505848279273790312014-06-03T22:08:16.071-05:002014-06-03T22:08:16.071-05:00If you're going to go there then there's t...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)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8959285010059702092014-06-03T18:12:51.327-05:002014-06-03T18:12:51.327-05:00Another example, when an acronym is used in quite ...Another example, when an acronym is used in quite a few unrelated fields:<br /><br />ATM = Alternating Turing Machine<br />ATM = Asynchronous Transfer Mode<br />ATM = Automated Teller Machine<br />ATM = Adobe Type Manager<br />ATM = Air Traffic Management<br />ATM = Anti-Tank Missile<br />ATM = Area Training Manager<br />ATM = Automatic Timing Mechanism<br />ATM = Atmospheric Transport Model<br />ATM = Air Turbine Motor<br />ATM = Association of Texas Midwives<br />ATM = Acoustic Telemetry Modem<br />ATM = Automated Theorem Prover<br /><br />and probably a number of others...Andras Faragohttp://www.utdallas.edu/~faragonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60334011213989355812014-06-03T15:38:52.015-05:002014-06-03T15:38:52.015-05:00I thought AKS is used for referring to extremely d...I 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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50074839514403371042014-06-03T02:49:38.381-05:002014-06-03T02:49:38.381-05:00AKS primes = 122000 hits. AKS primes = 122000 hits. Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39219436178042656942014-06-02T15:50:18.832-05:002014-06-02T15:50:18.832-05:00Fixed to Komlos.. Thanks.Fixed to Komlos.. Thanks.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18182981467282931712014-06-02T15:01:40.059-05:002014-06-02T15:01:40.059-05:00For AKS, I don't think about either of your tw...For AKS, I don't think about either of your two choices, because it's "Komlos", not "Kolmos". More precisely, it's "Komlós".Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29710481257990417062014-06-02T08:39:41.183-05:002014-06-02T08:39:41.183-05:00Also AKS = Ajtai-Kumar-Sivakumar, the first singly...Also AKS = Ajtai-Kumar-Sivakumar, the first singly exponential (2^n) algorithm for the Shortest Vector Problem in n-dimensional lattices.<br /><br />Bottom line: if you review a paper/proposal by AKS, accept it.Chrishttps://www.blogger.com/profile/03327470068256472110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50471886488677278772014-06-02T04:29:11.467-05:002014-06-02T04:29:11.467-05:00PCP seems like a good example of an acronym that c...PCP 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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39763661055078444822014-06-02T03:09:06.648-05:002014-06-02T03:09:06.648-05:00There is also a recent paper by An-Kleinberg-Shmoy...There is also a recent paper by An-Kleinberg-Shmoys on the TSP path problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79872886493408018572014-06-02T02:32:47.321-05:002014-06-02T02:32:47.321-05:00A collision that I discovered when I checked what ...A collision that I discovered when I checked what talks were up:<br /><br />PCP=Probabilistically Checkable Proof<br />PCP=Post Correspondence Problem<br />Gunnarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9233137870752410092014-06-02T01:21:36.199-05:002014-06-02T01:21:36.199-05:00PCP: Post Correspondence Problem or Probabilistica...PCP: Post Correspondence Problem or Probabilistically Checkable Proofs?Anonymousnoreply@blogger.com