A Request That We Passed On

Alistair Sinclair is a “British computer scientist and computational theorist”—to quote our friends at Wikipedia. I know him more as Berkeleyan than British, but Ken knew him long ago in Britain itself, so what do I know. Wherever he is, he is one of the leaders in the world on anything concerning randomized algorithms of all kinds. He has won the prestigious Gödel and Fulkerson Prizes. The latter was for his brilliant work on the permanent, in a long project that culminated in his famous breakthrough paper with Mark Jerrum and my Georgia Tech colleague Eric Vigoda.

Today I want to talk about a request we just got from Alistair that Ken and I decided to take a pass on, and give a reason why we did so.

Alistair just asked us if we would make an announcement about the exciting programs planned for the next academic year at the Simons Institute for the Theory of Computing at Berkeley. He kindly pointed out that:

If you see an opportunity, I wonder if you could post this in some form on your blog? You should definitely feel free to ignore this request: I fully realize that your blog is not primarily a bulletin board. But if you are able to welcome this it would be much appreciated.

Below is an official announcement; of course, you are welcome to abbreviate and/or modify this in any way you wish. The key pieces of information are the link and the deadline of Decemeber 15.

Ken and I discussed it at length and finally decided that even though we have both known Alistair for over thirty years, we couldn’t exactly do what he asked. The Simons Institute is a wonderful new resource, generously supported by Jim Simons, and is running some terrific programs. But announcements are not really what we do.

His Request

Just FYI, here is what we were to announce for him, but we declined politely to do so, since we are usually not a “bulletin board,” as he put it.

Simons-Berkeley Research Fellowships are an opportunity for outstanding junior scientists (up to 6 years from PhD by Fall 2014) to spend one or two semesters at the Institute in connection with one or more of its programs. The programs for 2014-15 are as follows:

• Algorithmic Spectral Graph Theory (Fall 2014)

• Algorithms and Complexity in Algebraic Geometry (Fall 2014)

• Information Theory (Spring 2015)

• Hedge Fund Logistics and Obamacare (Winter 2014)

The last is by special invitation only. It will cover secrets of testing computer systems for hedge fund operations and high-speed trading, and apply the lessons learned to develop recommendations for fixing the beleaguered website healthcare.gov. Jim Simons himself will be leading the discussions. Since December 15th is Zamenhof Day, the birthday of the Esperanto creator Ludwik Zamenhof, applications written in Esperanto will be given special consideration.

Okay we are joking about the last topic on hedge funds but wanted to be sure you were reading. Alistair did after all say we could “abbreviate and/or modify this in any way you wish.” But we do have a serious point, and it’s not what you think.

A Little Quote Logic

We—especially Ken and new Buffalo student Michael Wehar, whose work while a CMU undergrad we covered a year ago—have been thinking about provability predicates in logic and paradoxes arising from interpreting them as ways of quoting something. A proof predicate has the form and says that is a valid proof (in a given formal system) of the formula . This is the logical analogue of checking the validity of a computation by a particular machine. A provability predicate then has the form .

The weird fact, which applies to the same natural strong formal systems that Kurt Gödel’s famous incompleteness theorems hold for, is that there are statements such that proves . but does not prove itself. Call such a statement an “ambivalence” of . Our analogy is that in this post, Alaistair’s request on which we were ambivalent is .

Indeed the English phrase “to pass on” has ambivalent meanings: it can mean to transmit or to decline. To “take a pass on” something can mean to decline it or to give it a go. “Special consideration” might be more positive or might be otherwise.

Are there helpful general properties known about such statements ? One can try to avoid them by adding suitable logical reflection principles to , but we wish to know what happens in the original systems. We are also interested in even more paradoxical cases where does not prove , but , that is assuming the negation of , does prove . Note that the consistency of is expressed by the statement . We are wondering especially about cases where itself might be or . Knowing some general properties might also help us with cases like proving where is a slight modification of , such as but or maybe .

Well, we try to be consistent on this blog, but we can’t prove it.

Open Problems

Ooops, we were not supposed to actually put this out—this was just one of our brainstorming drafts. Oh well. I guess I clicked the publish button on the WordPress.com site. But for a possible future post or paper, can you help us with understanding ambivalent statements?