Converse oF Clarke's famous quote

The following kind of act was popular (say) 40 years ago: Someone claims to be able to read minds. He says things like I sense there is someone here named Bill. Then someone named Bill says Yes, thats me! Then the mindreader talks to Bill and seems to know things about him. How did the mindreader do it? He studies styles of clothes (Mindreader thinks: The way Bill is dressed he must be a college professor.) He gets Bill to reveal stuff about himself and echoes it back. The mind reader may have people who mingle with the crowd ahead of time and try to overhear conversations. This took some real skill to pull off.

Fast forward to the year 2008.

1. The mindreader could get everyones name ahead of time since most paid by credit card, and google some of them to find out more about them.
2. But, the audience knows he can do this.
3. The more precise his statements are (e.g., I sense that Bill co-writes a Blog with someone named Lance) the more obvious it is that he used GOOGLE and hence the less impressed I would be.
4. Lets look at this another way: How could a real mindreader convince us that he wasn't using Google? Or some other high-tech device?
5. Recall Arthur Clark's famous quote

   Any sufficiently advanced technology is indistinguable from magic.

   What is happening here is the inverse or converse or something of that:

   In a sufficiently advanced technlogical society it will be hard for a magician to impress anyone.

International Spy Museum

I went to the International Spy Museum recently. I recommend it. However, there were two things I spotted that I know were incorrect. This makes their credibility as a source of information suspect. This is too bad--- as we'll see later.

1. The museum has the story of Nathan Hale. He was a spy for the Americans during the Revolutionary War. He was hanged and his last words were I regret that I have but one life to give for my country. In reality his last words were probably AAAAAAAAAAAHHHHHHHHHH. Actually they were never recorded, though some serious historians think he was the kind of guy who would say I regret ... . Not the same as saying it.
2. The museums had an exhibit of the Enigma machine. They were trying to make the (true) point that the story of cracking the Enigma was a secret for many years, and hence Turing didn't get credit until later. They phrased this as

   If the story of cracking the Enigma was known earlier then Turing would have won a Nobel Prize.

   A Nobel Prize? In what? Chemistry? Physics? Literature? Medicine? Peace? Economics? Peace (maybe its shortened the war)? The statement is clearly false. What they should have said was

   If the story of cracking the Enigma was known earlier, and if the Turing Award had been established, then Turing would have likely won a Turing Award.

Having gotten these two items wrong I now turn to a question for which I do not know the truth.

Did the Nuclear Secrets that Julius Rosenberg gave to the USSR speed up the building of the USSR's nuclear bomb?

I have read YES and NO for this question. The NO that I have read says that the biggest nuclear secret that the USSR ever got was the fact that the bomb could be built. Hence the person who leaked our biggest nuclear secret was... President Harry Truman. The YES that the Spy museum said was that the USSR bomb design was very close to the American one. What is the truth? That's just it- I don't know! If the spy museum had not made those other mistakes I would believe them on this. (My believe may still have been wrong.)

Wikipedia says the secrets were not valuable. Are they more credible?

Information Overload

Obama says many wonderful things for science. Scott has his take.

The Religion Chair at Columbia wants to end universities as we know it. Mitzenmacher does a good job pointing out the problems in his arguments, especially for CS.

Will the Swine Flu ruin the summer conference season? Probably not, so go register for the Complexity Conference in beautiful Paris and don't forget early registration ends today for STOC in not-quite-as-beautiful Bethesda.

AI in Jeopardy

John Markoff writes in the Times about IBM's plans to create a computer contestant for the Jeopardy TV game show. Jeopardy is a basic knowledge and trivia show with few gimmicks (beyond giving questions for answers instead of vice-versa) which is probably why the show has endured so long. The issue for the computer is not knowledge (one could download the entirety of Wikipedia on a USB drive) but of properly interpreting the question.

Back in my NEC days, some of the AI folks there wrote a similar program for the game show Who Wants to be a Millionaire, although the program was never considered for use on the real show. Unlike Jeopardy, Millionaire had multiple choice answers and their program basically did keyword matching on Google searches. Their program did quite well on the very specific high-dollar questions. But their program often stumbled on the low-dollar easy questions which relied on basic knowledge.

This Jeopardy computer experiment still seems to me comparing apples to oranges. Humans have little trouble interpreting the meaning of the "answers" in Jeopardy, they are being tested on their knowledge of that material. The computer has access to all that knowledge but doesn't know how to match it up to simple English sentences. I suspect the computer will win this fight for it has the ultimate Jeopardy advantage: it can buzz in faster.

Vardi: Are Conferences Worth Fixing?

Moshe Vardi uses his editor's letter in the May CACM to start up a debate on the future of conferences in CS. He mentions last year's Workshop on Organizing Workshops, Conferences, and Symposia for Computer Systems that focused on perceived problems in the paper selection process and then asks the big question.

But I fear these efforts have not addressed the most fundamental question: Is the conference-publication "system" serving us well today? Before we try to fix the conference publication system, we must determine whether it is worth fixing.

In 1999, the CRA published a best practices memo about tenure that legitimizes conferences as the primary place of publication.

The reason conference publication is preferred to journal publication, at least for experimentalists, is the shorter time to print (7 months vs 1-2 years), the opportunity to describe the work before one's peers at a public presentation, and the more complete level of review (4-5 evaluations per paper compared to 2-3 for an archival journal) [Academic Careers, 94]. Publication in the prestige conferences is inferior to the prestige journals only in having significant page limitations and little time to polish the paper. In those dimensions that count most, conferences are superior.

Vardi make several points.

• Fast dissemination is not an issue with on-line archives.
• The quality of reviewing is higher for journals than for conferences.
• Every other academic field uses journals as the primary focus of publication.

Moshe ends his letter asking for further discussion.

So, I want to raise the question whether "we are driving on the wrong side of the publication road." I believe that our community must have a broad and frank conversation on this topic. This discussion began in earnest in a workshop at the 2008 Snowbird Conference on Paper and Proposal Reviews: Is the Process Flawed?

I cannot think of a forum better than Communications in which to continue this conversation. I am looking forward to your opinions.

Complexity Theory songs (repost)

You probably read on Scott's blog that there is a WINNER for the Aaronson/Gasarch Complexity Theme Song Contest. It is Aaron Sterlings I just do theory You can get the lyrics and MP3 off of Scotts Blog. (MP3 is also pointed to below.)

Below is a list of five Songs about Complexity Theory that are available. Are there others? (Not counting The Klein Four or Tom Leher or Jonathan Coulton or Square One Television or others who have done math songs.) If you know of any email me pointer to the mp3, CD, LP, 45's 78's, or wax cylinder that contain them.

1. I just do theory. The new theory qualifying exam: Identify every reference in this song.
2. There so much Drama in the PhD. Complexity Theory song AND one of those Rap Songs that parents don't want their kids to listen to.
4. Longest path. The first complexity-theory song I ever heard and still one of the five best!
5. Theory Girl. Complexity Theory song AND Love song!
6. ALice and Bob By MC++. (I actually pointed to the MC++ website which has lots of stuff.) He has others, but this is his best and the one most relevant to Complexity Theory.

ALSO, not relevant to Complexity Theory, but worth noting for this blog--- A song about blogging!: I blog alone.

The Economy and Conferences

Aravind Srinivasin writes to us theory bloggers:

Especially given the current economic climate, ACM is concerned about getting enough registrants and booked hotel rooms for STOC. Could you please announce a reminder on your blogs that the STOC early registration deadline deadline is April 28th?

Consider yourselves reminded.

Will the economy affect the number of registrants at STOC and other theory conferences? Most attendees these days either have a paper in the conference, live close by or sit on some committee. NSF funding for theory is higher than in recent years but many departments have cut travel budgets and travel funding from outside the US may have dropped as well. If the economy is preventing you from attending STOC (and you would have attended otherwise) let us know in the comments, anonymously if you must. 

The economy might send people to cheaper hotels. This also hurts the STOC budget. From the hotel registration page.

Your support in staying at the Hyatt Regency Bethesda helps keep the conference costs down, which directly affects your registration fees. ACM guarantees the hotel that we will fill a certain number of “room nights” (rooms per night) during the conference. ACM incurs penalties if too many attendees opt to stay in other hotels in the area or neglect to indicate to the hotel that they are with the ACM conference.

I did a quick check on hotels.com and didn't see any significant savings at other hotels so go register at the STOC hotel, doubling up if you need to save money.

Who Gives the Talk?

In theoretical computer science we view all authors as having contributed equally, thus the listing of authors alphabetically. So when a paper gets accepted for presentation at a conference, who gives the talk?

In general the authors of the paper can choose among themselves who should give the talk, but having a few simple rules can help save an awkward discussion and hurt feelings.

By default I like to have the youngest author give the talk, youngest by academic age (years since Ph.D). Academic age is both negative and estimated for grad students but the rule still applies. Young people can use the talk practice and the exposure and giving the talk forces them to attend the conference where they can interact with a broader community.

If the youngest author cannot attend the conference (and it should be a very good reason) then move up the chain. If none of the authors can attend the conference, which should only happen in emergency situations, then the authors need to find someone else to give the talk. Authors should not submit to a conference unless one of them is willing to present the paper if it is accepted.

Some exceptions: An author looking for a job gets priority. If an author is already giving a different talk at the same conference then best to spread the wealth around. Sometimes it just makes sense for a specific author to give that talk based on the role they played in the paper.

Of course following these rules mean I haven't given a regular STOC/FOCS talk since 1992 but that's life.

NASA's Poll a Sham!!

Recall that NASA held a poll to determine the name of the third node of the international space station. I blogged about the fact that Stephen Colbert campaigned to win and did! The name Serenity came in second place.

NASA had three choices

1. Name it Colbert. Show the world democracy in action! (at least on unimportant things).
2. Name it Serenity. Reiterate that the poll was more to take the pulse of the public, but they really do want something more in line with the first two nodes: Harmony and Unity.
3. Use the 7th place winner Tranquility and offer some half-assed reason for it.

They chose option (3). However, they are going to name the treadmill that goes into the node:

Combined Operational Load Bearing External Resistance Treadmill

~

ACM Pubs

I am heading a committee to find a new Editor-in-Chief for JACM to replace Prabhakar Raghavan whose term is ending. Send me your nominations.

The ACM digital library has a new portal (currently in beta). They've also strengthened their search engine, added author profile pages and will start indexing best paper and other award winners. The digital library interfaces well with Google Scholar and other search engines and indexes many non-ACM publications (Tip: To get to a non-ACM publication page from the digital library listing click on the DOI). ACM continues to impress on its DL when I find so many of the others lacking in functionality or ease of use.

I'd also like to mention a little known service, the ACM International Conference Proceeding Series (AICPS). For conferences, mostly foreign, who don't want or need ACM sponsorship, this series gives them the opportunity to have their proceedings in the ACM digital library, a good alternative to the Springer LNCS series. In theory the CATS conference (Australia area theory) uses AICPS and I wouldn't mind seeing many other theory conferences heading that way.

Workshop on Theory and Many Cores

This is largely an announcement post, but it does raise the questions: (1) What has theory done for parallelism? (2) What can theory do for parallelism? (3) What has parallelism done for theory? (4) What can parallelism do for theory?

The current reality is that non-theory communities (architecture, compiler, applications) nearly ignore the role of the theory and algorithm communities when it come to ongoing reinvention of CS for parallelism. As you know, this reinvention is mandated by the transition to many-core computer driven by technology and market forces and will affect how CS is taught at all level, including freshmen programming, courses on algorithms and data structures, etc. It will be a pity for all if theory remains out of the discussion. For example, it can adversely affect the future of the theory and algorithms communities, as claims of relevance of theory to CS will become harder to support.

Here is one step to bridging the gap: Workshop on Theory and Many-Cores: What Does Theory Have to Say About Many-Core Computing?

WHEN: Friday, May 29, 2009

WHERE: Kim Engineering Building, Room 1110, University of Maryland, College Park, Maryland

The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.

The main objective of the workshop will be to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.

The workshop will feature five invited talks and several contributed presentations.=20

Deadline for submitting an abstract: April 27, 2009.

List of speakers:

1. Guy Blelloch, CMU
2. Phil Gibbons, Intel
3. Arch Robison, Intel (Architect of Intel's Threading Building Blocks (TBB))
4. Leslie Valiant, Harvard
5. Uzi Vishkin, University of Maryland

For those who attend STOC 2009, which starts May 30, in Bethesda, Maryland: The University of Maryland is a 12-mile ride from Bethesda, and both Bethesda and UMD are accessible by Metro.

Sponsors: The University of Maryland Institute for Advanced Computer Studies (UMIACS)its Electrical and Computer Engineering Department, and the Center for Computational Thinking, Carnegie-Mellon University

Conference Accepts

A number of summer conferences specifically had their submission deadlines soon after the STOC decision date in early February. Now these conferences have made their own decisions so go check out the accepted papers of Computational Complexity, ICALP, EC and COCOON.

Speaking of STOC, early registration deadline of April 28th is fast approaching. Bill and I will both be there.

Lots of great papers in the Complexity Conference headlined by Braverman but let me focus on the paper One-Way Functions and the Isomorphism Conjecture by Manindra Agrawal and Osamu Watanabe. That is the Agrawal of Primes in P fame. Kayal and Saxena each have Complexity papers as well.

Many complexity theorists don't believe the Berman-Hartmanis Isomorphism Conjecture, that all NP-complete sets are essentially the same, because the conjecture fails given sufficiently hard one-way functions. Agrawal and Watanabe argue that the one-way functions that we commonly see in cryptography have an easy to invert "cylinder" which allows one to achieve an isomorphism for NP-complete sets based on using these functions as reductions. Agrawal and Watanabe show roughly that under an assumption that all such functions have such cylinders one gets nonuniform isomorphisms. 

Given the Agrawal-Watanabe paper I started to believe that maybe the Berman-Hartmanis conjecture holds after all. On the other hand, Oded Goldreich has since given a candidate one-way function that may not have the cylinder property. Now I don't know what to believe.

Traveling to Conferences

COCOON is one of these conferences where I don't quite get the geography. Mostly in Asia the conference has also been held in Australia, Montana and Alberta. Someone once told me it was a "Pacific Rim" conference. But this summer the 15th COCOON will be held on the US side of Niagara Falls, near Buffalo, New York. I guess technically COCOON is being held in a country that borders the Pacific.

Because COCOON is usually in Asia they had problems with authors not coming to the conference which leads to an interesting paragraph in the author's instructions pointed out to me by a student author.

Each accepted paper must come with a full registration (i.e. not the student rate) for the paper to be included in the proceedings. [The full registration rate is 450USD, the student rate is 250USD.] For authors with multiple accepted papers, one full registration can "cover" up to 3 papers.

I understand what COCOON is trying to accomplish but why punish the students with an extra $200.

In general authors make a pledge to come to a conference if their paper gets accepted and COCOON is just reacting to authors who don't fulfill that basic commitment. So paying a registration fee (not to mention travel costs) is essentially a requirement if you want your paper to appear in any conference proceedings. In CS, a field that puts greater prestige on conferences than most journals, that puts a heavy burden on those who want to publish their papers but do not have grants or other travel funds available.

Accessing Ladner

Richard Ladner, current SIGACT chair and prover of many theorems including his namesake, won the 2008 CRA A. Nico Habermann Award not for theory but for his lifetime work on making computers accessible to the persons with disabilities. Ladner writes an article in CRA News on some of the challenges of persons with disabilities in education and computing, such as how do you allow a blind person to solve a CAPTCHA.

One of Ladner's projects builds an video messaging system designed so one can use it for communicating with sign language. Check out this video.

Tom Lehrer turns 9*9 today!

Today (April 9) Tom Lehrer turns 81=9². To celebrate I post some lesser known Tom L songs. I post all that did not appear on any of his CD's. Note that The remains of Tom Lehrer, his 3-CD boxed set, already had several songs that had not appeared on any of his prior available work. (I got it from Agnes, Thats Math (short version- long version is on Dr. Demento Basement tapes No. 4), Selling Out, I've spending Hannakuh in Santa Monica, L-Y, Silent E, O-U, S-N. L-Y and Silent E had appeared as extras on CD versions of his Vinyl records.) Hence to NOT even appear on the boxed-set makes it rather rare. Or is it? Its on You-Tube so how rare can it be? (I discussed this in an earlier blog here.)

Derivative Song. Likely did not appear on any CD because the audience for this is too small. Also might have been copyright problems as he used someone elses tune (See comment on THE PROFESSORS SONG later in this post.)

Decimal. GREAT song. Likely did not appear since its a bit dated and the context is now lost. The best of the rare songs. To the tune of his own New Math

The professor's song. GREAT song. Don't know why it's not in the boxed set--- no copyright problems since he used a Gilbert and Sullivan Tune which is public domain (Tom L always used his own tunes to avoid legal issues. The only exceptions are this song and The Elements which also used a Gilbert and Sullivan Tune.)



Subway Song. Not that good. However, note that 90% of Tom L's stuff is excellent. Weird Al has generated many more novelty songs, but only 50% are excellent. So who is better? It depends on how you measure. I, of course, like both of them. Incidentally, Weird Al did one math song for Square One TV: Polka Patterns. At one time that was a rare item in my collection. But now Its on you-tube so how rare can it be? @

The Lance Effect

"Lance" is a relatively rare name which has some advantages. I have what's usually a unique identifier, the only Lance at nearly every conference I've attended for example.

But Lance is far from unique. Googling "Lance" has me on the third page of lists, just above New Jersey Congressman Leonard Lance. The most famous Lance rides a bike.

Occasionally, though pretty rarely, I find myself in a room with another Lance and will always get confused when someone calls out "Lance" and it's not me.

But because of the rarity, most people think they know only one Lance even when they know more. So they send emails to "Lance" going to me by mistake. Usually harmless but once I got an obscenity-laced diatribe from a student. I did what I always do in this situation, reply with "Did you really mean to send that to me?"

During the last SoCG deadline day and again during last week's STOC deadline day, a certain professor (you know who you are) started sending me emails asking me to make various changes to a paper. But I wasn't writing a paper with him, turns out he has a student named Lance. But after I let him know, I continued to get emails for the student. First it was cute, then annoying, then fun as I made up answers ("no, you can't have the token"), then it got annoying again.

What's the lesson here? Be careful which Lance you send to, especially when the other Lance has a blog.

Baseball is Back

Ahh April. Taxes are due. Chicago's winter still hasn't ended. Spring quarter classes have started and while I have fun teaching Intro Theory it still means ten weeks to summer. But then I remember: Baseball is back and all is good in the world. Something to get excited about nearly every day for the next six months and hopefully longer.

In true Chicago fashion the first White Sox game yesterday was cancelled due to weather and will get played this afternoon. The Cubs won their first game in Houston yesterday on their likely 101st consecutive year of futility. I've also come to enjoy going to Brewers games in Milwaukee: I can drive to Miller Park in about an hour from my house, they have ample parking, a retractable dome so you don't have to worry about the weather and you can't beat the sausages: both the kind you buy in the stands and the ones who race on the field.

What does all this have to do with Complexity? Not much. But it is Opening Day and life is good.

The Jack Schwartz Memorial

(Guest Blog by Clyde Kruskal)

As I mentioned in my previous guest blog I attended Jack Schwartz's memorial, which was organized and MCed by Ed Schonberg. It took place at the Courant Institute on a Friday evening and was followed by food and drinks. The next day, his wife, Diana, graciously hosted an open house.

Colleagues, family, and friends spoke roughly in chronological order of knowing him, starting with his sister. The Computer Scientists who spoke most recognizable to this community were: Martin Davis, Greg Chaitin, and Michael Rabin. Other computer scientists who spoke were (his ex-wife) Fran Allen, Robert Dewar, Eugenio Omodeo (who came from Italy with Alfredo Ferro), Bud Mishra, and Ken Perlin.

Music was an important part of Jack's life. A number of people played and/or sang, including his wife, who composed and played a piano piece (Portrait of Jack).

What showed through was Jack's intellect and generousity. Louis Nirenberg noted that Jack read mathematics like other people read novels. This is not hyperbole. Similar comments were made by Robert Dewar and Peter Lax.

Michael Schwartman talked about how Jack helped him get out of the Soviet Union and make his way in the US, and how Jack was able to maintain their friendship despite their unequal relationship.

On a personal note, it was wonderful to see some of my former professors and fellow students at the Courant Institute. It has been a long time since I was back. Some things were the same, some things were different, and some things were the same but seemed very different than I remembered.

Guest Blog by Clyde Kruskal on Jack Schwartz

(Guest Blog by Clyde Kruskal.)
Last week I attended the memorial for one of my three advisors, Jacob T. Schwartz, who passed away in the beginning of March. He was a Mathematician and Computer Scientist with enormous intellect and accomplishments. I suspect he is not as well known in the Complexity Community as he deserves. Here I discuss only some of his work. Next week I will talk a little about the memorial itself.

Jack was a member of both the National Academy of Sciences and the National Academy of Engineering. He had a wide range of interests, and switched fields every few years. Whenever he worked in a field, it seems that his goal was to accomplish something large. One trick of being his student was to finish fast enough before he switched fields. For my thesis in Parallel Processing, I did not actually succeed in doing so, but Jack created a large project with plenty of researchers, so there was still a rich enviroment for me. His seminal paper on Ultracomputers was the basis for the project.

Jack is probably best known for his classic three volume set, co-authored with Dunford, on Linear Operators, which won the Leroy T. Steele Prize for Mathematical Exposition.

He developed the SETL programming language, which is based on the concept that, since set theory is a good way to describe mathematics, it should also be a good way to write programs. It never really caught on but was influential in the field of computer languages and compilers. Python has its roots partially in SETL. The first ADA compiler was written in SETL. Here is an example of a SETL program for topological sort taken from Schwartz's website:

proc top_sort1(G,nodes);  top sort proc, rec form
  return if exists n in nodes | n notin range(G) then
      [n] + top_sort1(G lessf n, nodes less n) else [] end if;
end top_sort1;

A powerful optimizer is needed for such a high level language, and much effort went into this. GNU SETL is available. If you spend enough time in New York, eventually you will see four strong moving men twisting and turning a baby grand piano up four flights of narrow staircases. Figuring how to do this so that the piano fits is a computationally difficult task (The Piano Movers Problem). Jack co-authored a series of papers with Micha Shirir on this topic. This seems to be his most cited body of work in Computer Science.

Jack also worked outside of Math and Computer Science: He wrote a two volume set in Economics, and at the end of his life he was actively working in Biology.

Schwartz's [Wikipedia page] lists his interests to include: theory of linear operators, von Neumann algebras, quantum field theory, time-sharing, parallel computing, programming language design and implementation, robotics, set-theoretic approaches in computational logic, proof and program verification systems; multimedia authoring tools; experimental studies of visual perception; multimedia and other high-level software techniques for analysis and visualization of bioinformatic data.

ToCT Launches

The ACM Transactions on Computation Theory has published its first issue with three exciting papers:

• Algebrization: A New Barrier in Complexity Theory by Aaronson and Wigderson.
• Scott and Avi's new take on relativization.
• A Simple Proof of Bazzi's Theorem by Razborov.
• A short proof that polylog independence fools DNFs. Precursor to Braverman's new result.
• Directed Planar Reachability Is in Unambiguous Log-Space by Bourke, Tewari and Vinodchandran.
• Roughly, given a map with one-way streets, you can nondeterministically find a unique route from point A to point B if one exists.

This is just the start of what is becoming a strong journal. Submit your papers and join the fun.

The Letter

Richard Lipton posts about the naming of the P=NP problem, the only Millennium Prize problem not named after people. But Lipton skipped an important part of the story.

As I started graduate school in 1985, there was a movement to use the term the Cook-Levin Conjecture instead of P≠NP. There were some who thought this disregarded the important work of Karp, leading to a rather nasty incident at FOCS '86 in Toronto.

But when the Gödel letter to von Neumann came to light in 1988 no one knew exactly who to credit the conjecture. Since then people just talk about the P vs. NP problem.

But was the Gödel letter actually written by Gödel? The letter mentions von Neumann's illness. von Neumann kept secret the fact that he had what was then highly experimental chemotherapy treatment even from his closest friends. It's extremely unlikely that Gödel would have known about this treatment at the time he supposedly wrote the letter.

And then there is a curious discussion from a dinner I went to during a STACS conference in the late 90's. I was having dinner with a small group including Thomas Hampson, then at Karlsruhe, and his wife Suzanne. Hampson had done a postdoc with Karp at Berkeley and they wrote several papers together. Hampson also was an expert on Gödel, having given a well-received survey of Gödel's work at a previous STACS. 

Suzanne was a museum curator who also occasionally worked with the German version of the FBI on forgeries. I asked her, jokingly, whether she had tried to forge anything herself. She smiled and said "Well there was the letter by G..." At this point Thomas said something short to her in German and Suzanne quickly changed the topic.

So is the Gödel letter a complete fabrication? Or is it this post?