The 17x17 challenge. Worth $289.00. This is not a joke.

The 17x17 challenge: worth $289.00. I am not kidding.

Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)

The 17x17 challenge: The first person to email me a 4-coloring of 17x17 in LaTeX will win $289.00. (I have a LaTeX template below.)

UPDATE: THE RESULTS ABOUT OBS₄ HAVE CHANGED SINCE THE ORIGINAL POST SINCE BRAD LARSON EMAILED ME A 4-COL OF 21x10 and 21x11. UPDATE: BRAD LARSON EMAILED ME A 4-COL OF 22x10.

UPDATE- PROBLEM WAS SOLVED. See my arXiv paper on grid colorings OR
my Feb 8, 2012 post.

Why 17x17? Are there other grids I care about? We (We=Stephen Fenner and Charles Glover and Semmy Purewal) will soon be submitting a PAPER (see TALK for a superset of the slide-talk I've given on this paper) on coloring grids. Here are the results and comments:

1. For all c there is a finite set of grids a₁xb₁, ..., a_kxb_k such that a grid is c-colorable iff it does not contain any of the a_ixb_i (n x m contains a x b if a &le n and b &le m). We call this set of grids OBS_c (OBS for Obstruction Set).
2. OBS₂ = {3x7, 5x5, 7x3}
3. OBS₃ = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
4. OBS₄ contains 41x5, 31x6, 29x7, 25x9, 23x10, 10x23, 9x25, 7x29, 6x31, 5x41
5. Exactly one of the following sets is in OBS₄: 21x13, 21x12.
6. Exactly one of the following sets is in OBS₄: 19x17, 18x17, 17x17.
7. If 19x17 is in OBS₄ then 18x18 might be in OBS₄ . If 19x17 is not in OBS₄ then 18x18 is not in OBS₄ .
8. A chart of what we do and do not know about 4-colorings of grids is here.
9. A Rectangle Free Subset of a x b is a subset of a x b that has no rectangles. Note that if a x b is 4-colorable then there must be a rectangle free subset of a x b of size Ceil(ab/4). We actually have a rectangle free subset of 17x17 of size Ceil(289/4)+1. Hence we think it is 4-colorable. For the rectangle-free subset see here. For the original LaTeX (which you can use for a template when you submit yours) see here. THIS IS WHY I AM FOCUSING ON 17x17--- BECAUSE I REALLY REALLY THINK THAT IT IS 4-COLORABLE. I could still be wrong.

What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.

Can I get a paper out of this? FACT: If you get me the coloring and want to use it in a publication then that is fine. OPINION: It would not be worth publishing unless you get all of OBS₄. See next question.

What do you hope to get out of this? My most optimistic scenario is that someone solves the 17x17 problem and that the math or software that they use can be used to crack the entire OBS₄ problem. If this happens and my paper has not been accepted yet then we could talk about a merge, though this is tentative on both ends.

Has there been any work done on this problem that is not in your paper?

1. A Rutgers grad student named Beth Kupkin has worked on the problem: here.
2. A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
3. SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
4. Here are some thoughts I have had on the problem lately: here.
5. There is a paper on the 3-d version of this problem: here.

Is Lance involved with this at all? When I gave a talk on grid colorings at Northwestern, Lance fell asleep.

Birthday Paradox Variance

First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US.

Here's an interesting approach to the birthday paradox using variances.

Suppose we have m people who have birthdays spread uniformly over n days. We want to bound m such that the probability that there are are at least two people with the same birthay is about one-half.

For 1 ≤ i < j ≤ m, let A_i,j be a random variable taking value 1 if the ith and jth person share the same birthday and zero otherwise. Let A be the sum of the A_i,j. At least two people have the same birthday if A ≥ 1.

E(A_i,j) = 1/n so by linearity of expectations, E(A) = m(m-1)/2n. By Markov's inequality, Prob(A ≥ 1) ≤ E(A) so if m(m-1)/2n ≤ 1/2 (approximately m ≤ n^1/2), the probability that two people have the same birthday is less than 1/2.

How about the other direction? For that we need to compute the variance. Var(A_i,j) = E(A_i,j²)-E²(A_i,j) = 1/n-1/n² = (n-1)/n².

A_i,j and A_u,v are independent random variables, obvious if {i,j}∩{u,v} = ∅ but still true even if they share an index: Prob(A_i,jA_i,v = 1) = Prob(The ith, jith and vth person all share the same birthday) = 1/n² = Prob(A_i,j=1)Prob(A_i,v=1).

The variance of a sum of pairwise independent random variables is the sum of the variances so we have Var(A) = m(m-1)(n-1)/2n².

Since A is integral we have Prob(A < 1) = Prob(A = 0) ≤ Prob(|A-E(A)| ≥ E(A)) ≤ Var(A)/E²(A) by Chebyshev's inequality. After simplifying we get Prob(A < 1) ≤ 2(n-1)/(m(m-1)) or approximately 2n/m². Setting that equal to 1/2 says that if m ≥ 2n^1/2 the probability that everyone has different birthdays is at most 1/2.

If m is the value that gives probability one-half that we have at least two people with the same birthday, we get n^1/2 ≤ m ≤ 2n^1/2, a factor of 2 difference. Not bad for a simple variance calculation.

Plugging in n = 365 into the exact formulas we get 19.612 ≤ m ≤ 38.661 where the real answer is about m = 23.

Enjoy the Thanksgiving holiday. We'll be back on Monday.

DIMACS at 20

Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event.

DIMACS has served the theoretical computer science community well over these two decades. They have hosted a number of postdocs and visitors usually around a Special Focus (originally Special years but one year is usually not enough). DIMACS runs a large number of educational and research activities but most importantly the great workshops over the years. DIMACS's reputation for having strong workshops allows it to continue to attract strong workshops and has helped make New Jersey (my home state) a major center of theory. 

The first DIMACS workshop I attended, Structural Complexity and Cryptography is where I first heard about about the first Gödel-prize winning research relating interactive proofs to hardness of approximation that was done primarily during that Special Year on Complexity Theory and Interactive Computation.

When I moved to the NEC Research Institute in 1999, I became quite active in DIMACS which had then started a Special Year on Computational Intractability including a great workshop on the Intrinsic Complexity of Computations with many great talks and discussions on the hardness of proving lower bounds. My talk on Diagonalization later became an article in the BEATCS complexity column.

I then joined the DIMACS executive board as the NEC representative just as the center was ending its 11-years of funding as an NSF Science and Technology Center. Amazing that DIMACS survived that transition and survived for these twenty years and beyond. Most of the credit goes to DIMACS director Fred Roberts who has often hustled for funding for specific special foci, projects and workshops, as well as finding people to run those foci and workshops.

The 2001 Workshop on Computational Issues in Game Theory and Mechanism Design truly established a new discipline in connecting computer science and economic theory. Based on the excitement from that workshop, DIMACS started a Special Focus on Computation and the Socio-Economic Sciences which Fred talked me into co-organizing with Rakesh Vohra, from Northwestern's Kellogg business school. After I moved back to Chicago in 2003, I met with Rakesh to plan the focus which led to collaboration and eventually my moving to Northwestern. 

The special focus had a number of exciting workshops particularly Information Markets which restarted that research area a couple years after the PAM disaster and our closing workshop on the Boundary between Economic Theory and Computer Science one of the few meetings that truly attracted both strong computer scientists and economists.

That's just a few of my DIMACS memories. Many others have similar stories for a center that helped shape the professional lives of myself and many other CS researchers. Congrats for 20 years and here's hoping for many more.

An undervalued Math Problem

As most of you know there are 7 problems worth $1,000,000 (see here). It may be just 6 since Poincare's conjecture has probably been solved. Why are these problems worth that much money? There are other open problems that are worth far less money. What determines how much money a problem is worth?

When Erdos offered money for a problem (from 10 to 3000 dollars) I suspect that the amount of money depended on (1) how hard Erdos thought the problem was, (2) how much Erdos cared about the problem, (3) how much money Erdos had when he offered the prize, and (4) inflation. (If anyone can find a pointer to the list of open Erdos Problems please comment and I'll add it here.)

Here is a problem that I have heard is hard and deep, yet it is only worth $3000 (Erdos proposed it). I think that it should be worth more.

BACKGROUND: Szemeredi's theorem: Let A&sube N. If the limit as n goes to infinity of size(A &cap {1,...,n})/n is bounded below by a positive constant then A has arbitrarily long arithmetic sequences. Intuition: if a set is large then it has arb long arith seqs. The CONJECTURE below uses a diff notion of large.

CONJECTURE: Let A&sube N. If &sum_{a&isin A} 1/a div

KNOWN: Its known that if A is the set of all primes (note that &sum_{a&isin A} 1/a diverges) then A has arbitrarily large arithmetic progressions. Nothing else is known! The conjecture for 3-AP's isn't even known!

Is this a good problem? If it is solved quickly (very unlikely) than NO. If absolutely no progress is made on it and no interesting mathematics comes out of the attempts than NO. It has to be just right.

Citing Papers

A student asked me which version of a research paper to cite, a journal (the last reviewed version) or a conference (the first reviewed version) of a paper. I generally cite papers in this precedence list.

1. The fully refereed journal version, even if it is "to appear".
2. The reviewed, though not usually refereed, conference proceedings version, again even if it is "to appear".
3. On an electronic archive, like arXiv or ECCC.
4. As a departmental technical report.
5. On a generic web page, like a personal page.
6. As a "Manuscript", if I have seen the paper but it's not publicly available.
7. As "Personal Communication" if the paper doesn't exist.

If the original paper is not in English I'll cite both the paper and an English translation if there is one.

The journal version can distort precedence. Paper A that depends on paper B can have a much earlier journal publication date. If precedence is a real issue, say when I am trying to give an historical overview, then I will cite both the journal and conference versions.

What if you use a theorem that appears in a page-limited conference paper but who's proof only appears in the longer tech report. Then I cite the conference paper for the theorem and the tech report for the proof. Even if a proof exists in a paper, I'll often cite another paper or book if it has a cleaner or simpler proof.

What if you cite a paper for a theorem for a proof that doesn't exist (the infamous "will appear in a later version of the paper")? If your paper critically needs that theorem, you really should give the proof for it yourself. At the very least later papers will cite your paper for the proof.

What if the conference or journal version is not on-line or behind a pay wall? I still cite the latest version figuring that if someone wants to read the paper they can use a service like Google Scholar to find an accessible version.

I try to use the same rules for links to papers on this blog because it's more important to give out the citation. If someone wants to download the paper again it's usually easy enough to find it.

In my .bib file (of bibtex entries), I replace the entries of papers as they get updated under the same citation-key. That way when I go back to latex older paper they get the latest references. We have too many people in our field who don't bother updating references, pointing to a tech report when the conference or journal version has been published.

Should you add hyperlinks in your bibliography to other papers? Nice if you do so and probably good if you are young and get into the habit now. But I haven't found the impetus to add links to papers in my now quite large .bib file.

In my ideal world, each research paper would have a web location which has human and machine readable descriptions of and pointers to all versions of that paper. We would just input that location into bibtex and it would automatically pull the information from the web and make the appropriate entry in your references. Then we would all cite correctly, or at least consistently.

Laptops in Church?

There are now bibles online where you can click for different versions, different translations, different interepretations, historical context, etc. The same is true, or will be soon, for other faith's holy books as well.

Will there come a day when people bring their laptops (or smaller devices) to church? They can claim that they are looking up things in their online bible. Some will indeed be looking up bible passages. Some will be balancing their checkbook. Some will be reading blogs. Some will be looking at porn. Will the church need to deal with this? If it does not distract others (and smaller devices won't) than perhaps not. But the notion of looking at porn while you are in Church is troublesome.

How does this compare to the laptops-in-classroom debate that we had here?

- Nothing I have said here is particulary to Christianity-- All faiths will have these problems. I wonder when it will come up and how they will deal with it.

FOCS Videos

As I tweeted yesterday, the videos of talks from the 2009 FOCS conference are now online. Thanks to FOCS PC chair Daniel Spielman and Georgia Tech's ARC Center for making it happen.

Let me be a bit Billish (or is it Gasarchian) and make my comments as questions. 

1. Which talks are most worth watching?
2. How many of these videos do you plan on watching?
3. Do you get value over these talks over reading the papers? The papers aren't on the IEEE DLs yet but Shiva has collected some links.
4. If STOC/FOCS talks were generally available on-line shortly after the conference, would this affect your attendance?
5. Are the videos useful even if you did attend FOCS?
6. Would you prefer videos on a established site like having a YouTube channel so the talks will always be available and you can use YouTube features like embedding?
7. Should STOC/FOCS and other conferences continue to make videos of their talks and post them freely on-line? How much would you be willing to pay in increased registration fees to make it happen? This would be a subsidy from those attending the conference to those who don't.

A Prayer Book for the Internet Generation

As a young kid in the Reform Jewish community we used the Union Prayer Book, a traditional book with Hebrew on the right and English on the left with lots of instructions for page jumping, standing, when to sing and whether everyone should speak. When I became a Bar Mitzvah in 1976, the temple sisterhood gave me a copy of the new prayer book, Gates of Prayer. The Gates of Prayer had services in a linear fashion using different fonts to denote when to sing and who should speak and with instructions on when to stand and sit. One could run an entire service giving no instructions from the Bima.

Gates of Prayer lasted more than three decades with only some rewording mostly to make the prayers gender neutral.

But in this Internet age people no longer read linearly. Last Friday I had my first taste of the new Reform Jewish prayer book, the Mishkan T'filiah.  No instructions or any indication when to stand or who should talk or sing. Here is a sample page (via the New York Times).

Each prayer gets its own two page spread with Hebrew, a faithful transliteration and translation and a couple alternative interpretations. No instructions or indications on when to stand, who should talk or sing and even when to turn the page. Our temple put in a notecard in each prayer book to explain the new book with some clues like whenever we hear "Baruch Atah (Blessed are you..)" we should turn the page.

One can easily see the Internet's influence. Each prayer gets the equivalent of a web page (or maybe a blog post). Lists on sides are like hyperlinks to other prayers. At the bottom are Twitter-length commentaries on the prayer. 

I expect this will be the last paper prayer book in the Reform movement. In the future we'll all download the prayers on our e-readers or smart phones with links to the next and other relevant prayers, all preset by the rabbis for that day's service. 

Rules about Blogs becaues Blogs RULE!

There are now laws about blogging and twittering that Lance and I (and all the bloggers) will need to be aware of. Here is a short summary:

1. If a blogger posts about a product that she got for free then she must disclose that she got it for free. (Applies to guys also.)
2. There are no such laws for traditional media.

Some questions:

1. What problem is this trying to solve? Did Lance get a free copy of some textbook, twitter about it, and it sold 1,000,000 copies? Or did Alaska Nebraska twitter about (say) a car she got for free and it sold alot? And if she did, so what? If the book or car is terrible then Lance's and Alaska's credibility will go down and people will stop following them. Thats how the free market is supposed to work. But does it?
2. Lets say that the evil trying to be prevented here is that Alaska Nebraka takes the car as a bribe and gives it a good review. Should that be illegal? And if so, why is that okay in old media? Because nobody pays attention to old media anymore?
3. If Lance just took straight-up-cash to write a good review, is that illegal?
4. If I get something for free, do not acknowledge that I got it for free, and TRASH IT on the blog, is that illegal?

What will Lance and I do? Well, in my SIGACT NEWS book review column I will put at the top of every column that the books were given to me for free. And if I ever comment about something I got for free (again, likely a book) then I will note that fact.

The wallet that Lance blogged about here is AWESOME!!!!!!!!!!!

Jobs

As many university's still feel the effect of the financial crises, many have limited or no positions to hire new tenure-track faculty so I expect the academic job market to be difficult again this year. But a few people have asked me to post announcements. Here are some places that are likely planning to hire tenure-track faculty in theory-related areas.

• University of Wisconsin-Madison (Theory)
• Aarhus University (Computational Complexity)
• University of Liverpool (Economics and Computation)
• University of Maryland-College Park (Comp Bio, Social Networks, Security/Crypto/Theory)
• University of Southern Denmark (Discrete Math and Algorithms)
• University of Texas-San Antonio (Algorithms)

Feel free to add other announcements in the comments.

Also watch the DMANet and TheoryNet lists, now collected in a new blog, and the listings at the CRA and the ACM as well as individual departmental home pages. Even if a place doesn't specifically advertise for theory, or at all, they still may hire so it never hurts to ask or apply.

Nevertheless finding a tenure-track job will be difficult this year. Should be a bit easier to find a postdoc position and no one will count it against you if you take a second or third postdoc to tie you over until the market improves.

Breaking Walls

Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in November of 1989 that changed all that. One marked the end of the Cold War. The other marked the start of the most exciting seven weeks of my research career.

It all happened during my rookie year as an assistant professor at the University of Chicago. On November 27, 1989, Noam Nisan emailed a paper draft showing that verifying the permanent (and thus co-NP) has multiple prover interactive proofs. Besides being a major breakthrough, this was the first time someone had proven a theorem where there was a previously published oracle result that went the other way. In my very first theorem in grad school (with Mike Sipser) we had an oracle relative to which co-NP did not have single prover interactive proofs (IP). With John Rompel, we extended the result to an oracle where co-NP did not have multiple prover interactive proofs (MIP). Noam showed co-NP did have multiple prover proof systems in the non-relativized world. This led me to thinking about whether we can find a single prover proof. I worked on this problem with then student Carsten Lund and Howard Karloff who had the office across from me. After a few weeks of hacking we finally did get such a protocol. Noam agreed to merge his now weaker result into ours and we quickly wrote it up and on December 13 emailed it out to the masses (these were the days before web archives, or even a web).

It took Adi Shamir less than two weeks to find the twist to add to our proof to get the full result that IP = PSPACE that he emailed out the day after Chirstmas. Babai (jokingly I think) chastised me afterwards for going away on a planned ski trip in mid-December.

In Fortnow-Rompel-Sipser we had also showed that MIP was contained in NEXP, non-deterministisic exponential time. After IP=PSPACE I then embarked on showing that you could put all of NEXP in MIP. At one point someone asked me why I didn't first try EXP in MIP and I mumbled something about how one ought to get nondeterminism for free in this model, but deep down I didn't want another partial result that someone else could usurp. My approach (not the one anyone would teach today) involved relativizing the LFKN co-NP in IP protocol using the provers to simulate the oracle. But we needed a low-degree test to make the relativization work, and working with Carsten and Laszlo Babai, we finally came up with a proof of the test. We sent out that paper on January 17, 1990.

I remember most the breakthrough moments when Carsten walked into my office asking me why his protocol for the permanent didn't work (it did) and when Babai, Lund and I discovered that the expansion properties of the hypercube was the last piece we needed to make our linear test work.

After MIP=NEXP, I thought we now knew nearly everything that matters about interactive proofs and moved on to other areas of complexity. Thus I missed the entire PCP craze that started about a year later.

At the 1990 Structures in Complexity Conference in Barcelona, Babai gave a cool talk E-mail and the Unexpected Power of Interaction describing those then recent results and the process behind them. I used that write-up to recover the dates above.

New York Theory Day

IBM-NYU-COLUMBIA theory day on Dec 11 ! Here are pointers to more information: here and here and here.

My advice: If you are able to go (distance, time, money all okay) then you should go. If you are unable to go then you shouldn't go.

Will this by available on video later? Also- if it is, will people actually watch it? There is something about BEING at a talk that is given at a particular time that seems more compelling then being able to look at it whenever you want, and hence not get around to looking at it. ~

Multi-Agent Biological Systems and Nat Algorithms Workshop (Guest Post)

Guest Post from Aaron Sterling

Multi-Agent Biological Systems and the Natural Algorithms Workshop

I attended the Natural Algorithms Workshop on November 2nd and 3rd. This was an event held by the Center for Computational Intractability in Princeton (which brought us the Barriers in Complexity Workshop). Bernard Chazelle was the organizer.

Chazelle is interested in applying complexity-theoretic techniques to the mathematical modeling of biological systems. Recently, Chazelle applied spectral graph theory, combinatorics of nondeterministic computation paths, and other techniques, to obtain upper and lower time bounds on two representative models of bird flocking. (Control-theoretic methods, e.g., Lyapunov functions, had obtained only an existence theorem the models converge without providing time bounds.) Chazelle's Natural Algorithms won the Best Paper Award at SODA 2009. (I found the SODA paper hard to read, as it moves through multiple difficult techniques in a compressed fashion. I recommend reading the first thirteen pages of this version instead, to get a sense of what he's doing.)

While computational complexity's entry into this field may be new, other areas of computer science have much longer-standing connection to multi-agent biological systems. A notable example is the work of Marco Dorigo, whose ant colony optimization algorithm has been influential. Dorigo's research group won the AAAI video contest in 2007; their video is a lot of fun to watch.

Back to the Workshop! The speakers were from diverse backgrounds (control theory, robotics, biology, distributed computing, mechanical engineering), and the talks were great. For reasons of space, I'll limit myself to summarizing one talk I found particularly exciting.

Magnus Egerstedt, a roboticist at Georgia Tech, talked about dolphin-inspired robot algorithms. He explained how dolphins feed. They use three basic strategies. In the first, a group of dolphins swims circles around a school of fish, in a formation called a carousel. Once the fish are well trapped by the carousel, the dolphins swim through the school one at a time to eat. The second strategy involves swimming on either side of the fish to herd them in a particular direction. The third involves physically pushing the fish from behind, either into a waiting group of dolphins, or onto dry land. Egerstedt showed a video of dolphins beaching themselves so they could push fish onto the sand. These feeding strategies demonstrate team effort, despite (presumably) limited ability to communicate. As one example, the dolphins have to take turns to feed during the carousel, or the entire strategy will be ruined. Egerstedt's group has used the behavior of dolphins to inspire several multi-agent algorithms. Here is a recent technical paper of theirs that was dolphin-inspired.

All the talks were videotaped, and are supposed to be on the Center's web page soon.

As a final note, Chazelle has written a followup paper to Natural Algorithms, and will be presenting it at ICS in January. There's no online version yet, but the abstract says the paper fits within a larger effort to develop an algorithmic calculus for self-organizing systems. With a battery of tools available, we might see quite a bit of TCS activity in this area over the next couple years.

Is FACEBOOK the new email?

Back in 1993 I had the following conversation with one of my relatives:

BILL: Just give me your email address and I'll email it to you.

RELATIVE: I don't have an email account. Why would I? Only you techno-geeks need email.

In 1994 I had the following conversation with the same relative:

BILL: Just give me your postal address and I'll mail it to you.

RELATIVE: Better- I'll give you my email address.

BILL: I thought you didn't have an email account.

RELATIVE: Only a techno-geek like you wouldn't know that everyone has email now.


At one time most people (outside of academia) did not have email. Now everyone has email. It is quite standard to have email on business cards and to ask for someones email address (are business cards still standard?).

I have run into people who are surprised that I don't have a FACEBOOK page. But here is the question: will having a FACEBOOK page be on the same level as having email in that everyone is expected to have it, and if you don't then you are just so 2005? My question is not tied to FACEBOOK per se--- I really mean will it be standard to be in some social network. Is having a webpage already standard?

(NOTE: My spell program tells me that its FACEBOOK not Facebook or facebook. So at least this time the capitol letters are not my idea.)

Button Button

Here is the offer: If you press the button you will receive $200,000. The caveat: Someone you don't know will die.


I was born during run of the original Twilight Zone but growing up watched them over and over again in reruns. People dealing with some small change in reality often with a clever twist in the ending. But they made you think.

CBS had a remake of the Twilight Zone series in the mid-80's. But nearly all the episodes were quite bland and highly predictable stories. But one episode in that new series, "Button Button", which made that offer above, caught be by surprise and worthy of being in the same caliber of the best of the original series. I won't spoil anything else about the episode.

A new movie The Box, a remake of Button, Button that opens today. I thank the commercials for The Box for reminding me of that sole great Twilight Zone episode of the 80's. Can a full length movie do justice to that short and powerful episode, even with the writer and director of Donnie Darko? I doubt it so skip the movie and rent the the original (disk 5) instead.

Innovation

The new Innovations in Computer Science conference announced their accepted papers earlier this week including my paper with Rahul Santhanam "Bounding Rationality by Discounting Time". Shiva is collecting PDF pointers (hope to get ours posted and on that list soon).

According to Noam, "this is the most interesting list of accepted papers that I’ve seen in years". Suresh seems happy too but some of his commenter's were less impressed. I view ICS as playing an orthogonal to STOC/FOCS, trying to present papers with potentially interesting ideas that wouldn't normally be accepted into STOC or FOCS. 

Why does STOC and FOCS not accept many innovative papers, even after adding the line "Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged" to the CFP? Since I can remember, STOC has focused more on solving well-defined problems with a deference towards technical proofs. A more innovative papers, that is a new model with a few simple results, tends to be harder to sell as one needs strong motivation and a model that really captures that motivation. When we do have more innovative papers they tend to be selected based on the authors more than the content. 

But this problem has gotten worse in recent years as our field has grown and PCs seem unwilling to trade a solid technical paper for a risky innovative one. When the PC meets, an innovative paper has a higher standard, the need to justify a new model or problem. Papers that answer old open questions or extend earlier work can justify their models simply because those models have appeared in earlier conferences. But no theoretical model can exactly capture a real world scenario so one can always find negative things to say about any innovative model, causing more traditional papers to often win the fight for those last few acceptance slots.

ICS did not accept as wide a spectrum of papers as I would have liked, probably due more to lack of a broad submission base. And the models of most of these papers will likely go nowhere but the hope is some will go to instigate new research areas.

Given the accepted papers can we tell yet if ICS is a success or a failure? Not yet and that's the point. Wait five years and see what fraction of papers from ICS (compared to STOC/FOCS) are still relevant and then we'll know.

Amir Pnueli (1941-2009)

Amir Pnueli passed away Monday from a brain hemorrhage. Amir was an expert in program verification who won the 1996 Turing Award primarily for his 1977 FOCS paper The Temporal Logic of Programs. Lenore Zuck shares her thoughts.

I'm reading through what people wrote about Amir in the past 30 or so hours since we received the sad news of his passing. I'm leafing through the citations of his numerous awards and honorary degrees, the list of academies of which he was a member, and the lists of his unique accomplishments. Throughout today I was helping with NYU's press release about him. Everybody mentions how brilliant he was, how modest he was, how pleasant he was, how gracious he was. Some mention his patience with those of us who are less talented than him. What is mentioned less is how much fun he was to work with, how he put the people around him at ease, how he managed to find good ideas in seemingly random thoughts people brought to him.

I recall the hours I've spent with Amir as a graduate student: joking, our regular Friday afternoon meetings solving the acrostic puzzle of "Koteret Rashit", discussing books, news, politics, and taking work breaks. It's a wonder we got anything done. It's a wonder we got so much done. This was Amir's style -- alternating between work and play, and making large strides in research while fostering the most pleasant work environment imaginable. Years later, when we were working together at NYU, it was the same with our joint PhD students. Long sessions consisting mainly of laughter, with some breaks for coffee and sweets, at the end of which I always found myself stunned how we made so much progress during all the hilarity.

I'm trying to recall Amir's funniest lines. Some don't translate, some require too much background. But I thought of a few that may illustrate Amir's special humor. When a student of his was called to military reserve duty whenever his oral exam for the completion of his MSc was scheduled, (temporal logic) until he found a note from Amir saying "you had your oral exam in absentia and you passed with flying colors." Or when I interchanged N and M in a paper, on which, upon proof reading, Amir wrote a note "even for N=M" when I claimed I proved something for any N. Or... after long arguments with me that the past operators in temporal logic are not needed, he gave a lecture in which he basically admitted they were useful, with slides whose titles were "Admitting the Past" and "Why Should We be Ashamed of the Past" that I felt were for me. And the list goes on.

I've collaborated with Amir since I was a graduate student. I've had several joint students with him. I've worked with his students. I've held regular meetings with him, the next one is scheduled for this Friday -- I still cannot bring myself to remove it from my calendar. I cannot imagine life without him. He was a genius, a friend, a colleague, one of a kind. I feel fortunate to have had the opportunity to know him, to have worked him, to have learnt so much from him. May his memory, legacy, and example stay with us.

Lenore D. Zuck, Arlington, Virginia, November 3rd, 2009

Update 11/15: NYT Obit for Pnueli

Really Liked Bertinoro- Ramsey Thing

(Reminder: STOC Deadline Thursday Nov 5, 7:00PM, Eastern: link.)

After yesterday's post about RaTLoCC 2009 (Ramsey Theory in Logic, Combinatorics, and Complexity) at Bertinoro some people emailed me and others commented asking Did you like it?. AH- my post was about what I learned there but not whether I liked it. IT WAS GREAT! I was at Dagstuhl Complexity a few weeks earlier and that was also GREAT! Some comparisons:

1. Both meetings had the same format. Guests are invited, the area is specialized, there are talks in the morning, then a long lunch break (12:00-3:00 or so) then more talks. Also an excursion-- a Hike in Germany and a Guided Tour of a city nearby in Italy.
2. Dagstuhl had 50 people or so, of which I probably knew 30 before hand. Bertinoro had 28 people of so, of which I probably knew 2 before hand. Both are good- I got to meet NEW people at both.
3. I got more out of Bertinoro. There were talks at Bertinoro where stuff I learned about Ramsey Theory 10 years ago was all I needed. At Dagstuhl I needed more recent background knowledge that I often didn't have.
4. I got more out of both then I do out of conferences which, by their nature, ONLY have the latest results.
5. At Dagstuhl out last meal was served late which was annoying since we had a plane to catch. At Bertinoro all meals were served on time. While some may use this to support the tired stereotype that Italians are better at organization then the Germans I stand by my prior postings about stereotypes (I'm against them).

Report From Ramsey-Logic-Complexity Workshop

Back from RaTLoCC 2009 which is Ramsey Theory in Logic, Combinatorics, and Complexity.

1. Here are the list of talks: here.
2. Reverse Mathematics tries to classify theorems by what is the strength of the axioms needed to prove them. There are five levels that almost all theorems in mathematics fit into. One curious outlier: the infinite Ramsey Theorem for pairs (for all c, for all c-colorings of the unordered pairs of naturals, there exists an infinite homogeneous set--- that is, a set of naturals where every pair has the same color). It does not fit in nicely. Ramsey for triples, etc, does.
3. One of the first natural theorems to be proven independent of PA was a Ramsey-type theorem. (One can debate if its natural.) See here.
4. Van der Waerden's Theorem In 1985 and earlier people thought that one of two things would happen with VDW's theorem. At that time the only proof lead to INSANE bounds on the VDW numbers. EITHER a combinatorist would obtain a proof with smaller bounds OR a logician would prove that the bounds were inherent. What happened: A logician (Shelah) came up with a proof that yielded primitive recursive bounds on VDW numbers. (Later Gowers got much better bounds.)
5. The talks on Complexity were all on Proof Complexity- things like blah-blah logical system needs blah-blah space to prove blah-blah theorem. Some of the theorems considered were Ramsey Theorems.
6. A while back I did two guest posts on Luca's blog on the poly VDW theorem here and here At the conference I found out two things that I said or implied that are INCORRECT.
   1. I said that the first proof of Poly VDW, using Ergodic theory, did not give bounds. Philipp Gerhardy gave a talk at RaTLOcCC that claims that the ergodic proofs either do yield bounds, or can easily be made to yield bounds. See his webpage (above pointer) for his paper. (When I later asked him if he prefers the classical proof of VDW's theorem or the Ergodic proof he said he can't tell them apart anymore.)
   2. I said that the only bounds known for PolyVDW numbers are the ones coming from an omega^omega induction. It turns out that Shelah has a paper that gives primitive recursive bounds. See either here or entry 679 here. (The entry 679 version looks like its better typeset.) The paper is from 2002. I am not surprised that this is true or that Shelah proved it. I am surprised that I didn't know about it since I am on the lookout for such things.
7. The conference was about 1/3 logicians, 1/3 combinatorists and 1/3 complexity theorists. There were only 27 people there, partially because it conflicted with FOCS and partially because there is some institute having the entire Fall devoted to Combinatorics (I forget which inst. but they are in California).
8. They plan to run it again, and if so I will so be there. Or I will be so there. Or something.