1. If you have a paper all set to go, with proofs complete, that is in scope and interesting, then you certainly COULD submit. Whether you should depends on other factors.
2. If this is the first you've heard of the deadline then you probably shouldn't RUSH to get it done in time. However, some people work well that way. Not only am I not one of those people, I don't understand those people.
3. This year STOC and CCC are back-to-back in Boston. That's my favorite arrangement- the advantage of FCRC (STOC and CCC in the same place) without the disadvantage (too big!). Hence, submit, accept, or not, I think you should GOTO STOC and CCC if circumstances permit.
4. Should you look at who is on the committee and based on that decide if it will get in? I tend to ignore the committee. So many papers are subrefereed. Trying to figure out which conference will be better for you based on the committee is too hard to deduce. Better to go for SCOPE- is your paper a complexity paper or not? Also, if for some reason a STOC or FOCS paper is better for your resume you can submit there; however, you can then end up with NO conferences for a while and resubmit later and and and...
5. If you submit then make sure to get your submission spellchecked and proofread before you submit.

1. If you have a paper all set to go, with proofs complete, that is in scope and interesting, then you certainly COULD submit. Whether you should depends on other factors.
2. If this is the first you've heard of the deadline then you probably shouldn't RUSH to get it done in time. However, some people work well that way. Not only am I not one of those people, I don't understand those people.
3. This year STOC and CCC are back-to-back in Boston. Thats my favorite arrangement- the advantage of FCRC (STOC and CCC in the same place) without the disdvantage (too big!). Hence, submit, accept, or not, I think you should GOTO STOC and CCC if circumstances permit.
4. Should you look at who is on the committee and based on that decide if it will get in? I tend to ignore the committee. So many papers are subrefereed. Trying to figure out which conference will be better for you based on the committee is too hard to deduce. Better to go for SCOPE- is your paper a complexity paper or not? Also, if for some reason a STOC or FOCS paper is better for your resume you can submit there; however, you can then end up with NO conferences for a while and resubmit later and and and...
5. If you submit then make sure to get your submission spellchecked and proofread before you submit.

1. 2-player, no luck. Go, Chess, Nim: Nim has had some nice math associated to it. Chess and Go have inspired very nice computer techniques (was alpha-beta pruning developed for chess originally?). There are some recent techniques for GO which I will talk about in a later posting.
2. 2-player, some luck: Backgammon, Can't Stop (a natural game but not that well known). Sorry! (that's not be apologizing, that's the game Sorry!). Parcheesi.
3. Multiplayer, no luck: Chinese Checkers. I do not know of ANY other examples.
4. Multiplayer, luck: Monopoly (and similar games).

1. 2-player, no luck. Stratego, Battleship: These are debatable. In fact, it may that that if defined carefully this combination is impossible.
2. 2-player, luck: Gin and most 2-player card game.
3. Multiplayer, no luck: Clue where each player only moves 5 squares per turn, so dice needed. One of Clyde's students families plays it this way, hence it is a natural game.
4. Multiplayer, luck: Poker. Most multiplayer card games.

This is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually. this is really bad for academia in general. Never again propose such things, please.

1. When a teacher assigns students to write code for a system the students are forced to do it in order to get a good grade. I am not forcing anyone to work on the 17x17 challenge.
2. When a teacher assigns students to write code for a system and the students do not get a co-authorship then this could be bad (this might depend on the situation). I stated explicitly that whoever cracks 17x17 can publish it themselves, or, if they do enough other stuff, with me. In any case the terms are out in the open. Also note that whatever I do will get much scrutiny because I posted it on a public blog rather than a private classroom.
3. When a teacher assigns students to write code for a system the students might get nothing for his efforts. If a student cracks my problem they will get $289.00. If they try and fail they may learn things of interest (to be fair, this may be true for student-code-writer as well).
4. The 17x17 challenge has already stimulated discussion on three blog and might get some people interested on the math end (Ramsey Theory) or the computer end. How is this bad for academia?
5. As Michael pointed out what I am doing is similar to what Erdos did, though my problem is not deep mathematics. Do you think that when Erdos offered money for problems, this was bad?
6. If I had posted about the problem WITHOUT the cash prize would you still object to it? (One point: if I offered it without a cash prize I would have asked to RESOLVE the problem rather than to GIVE ME a verifiable coloring). If I had offered ALOT MORE money would you object? Is it a U-shaped curve: offer either less than 10 or more than 2000 and you are okay with it? I am not being funny--- I look forward to your intelligent to comment on this.)

1. The typos in the chart were fixed. THANKS for the corrections.
2. The equation that Aaron Sterling pointed out was incorrect had a typo. THANKS Aaron. That should be fixed soon.
3. The Obstruction set raised alot of questions. OBS_c is NOT the set of all non-c-colorable grids. It is the set of all MINIMAL non-c-colorable grids. More precise: if nxm is in OBS_c then nxm is NOT c-colorable but both (n-1)xm and nx(m-1) are c-colorable.
4. Sky thinks 9,10,11 are in conflict. I corrected the chart so that may no longer be an issue, but if it is, please comment.
5. Grid coloring is not related to coloring planar graphs. Grid coloring problems can be rephrased at hypergraph coloring problems. I doubt this is helpful, but I could be wrong.
6. Why $289.00? Because 17x17=289. I originally thought I would offer $2.89 but Lance pointed out that that might not be enough to generate interest. Then I thought $28.90, but Lance again thought that would not get people interested. $289.00 seems just about right to get people interested but not break the bank of Gasarch. The person who won't give away the answer fo $289.00--- will you take $2.89 instead? How about $28.90?
7. dut asks if the 74-sized Rect Free Subset is the smallest there is, or could there be one of sized 73. Actually we could just take out one element and get a 73-sized Rect Free Subset. I think dut meant to ask: in a 4-coloring do we know a number x such that no color appears less than x times? YES. Lets say (and this is true but probably can be improved) that there is no Rect Fres set of sized 80 of 17x17. Then the smallest possible number of times a color can appear can easily be lower bounded. li> One of the Anon posits that its impossible since this person thinks you can't have a 73-sized Rect Free Set. Alas, my original post had a 74-sized Rect Free Set. In fact, thats why I think you CAN 4-color 17x17. I look at it as a barrier result: All of the techniques to show a grid can't be c-colored used rect free sets. Hence 17x17 (and the others) will not be able to be proven not 4-colorable using our techniques. Hence new techniques are needed. Not quite as impressive as Oracles, Natural Proofs, or Algebraization.
8. Scott claims that my claims are riddled with errors. Scott- please either point out an error or post that you are mistaken. Clearly the CHART was riddled with errors, but has been corrected.
9. I agree with commenter after David Benson who would like to know what David Benson did. David Benson- please elaborate so we can see what you did and if its right.

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, 9x25, 7x29, 6x31, 5x41
5. Exactly one of the following sets is in OBS₄: 23x10, 22x10, 21x10.
6. Exactly one of the following sets is in OBS₄: 22x11, 21x11, 21x10.
7. Exactly one of the following sets is in OBS₄: 22x11, 22x10, 21x10.
8. Exactly one of the following sets is in OBS₄: 21x13, 21x12, 21x11, 21x10.
9. Exactly one of the following sets is in OBS₄: 19x17, 18x17, 17x17.
10. If 19x17 is in OBS₄ then 18x18 might be in OBS₄ . If 19x17 is not in OBS₄ then 18x18 is not in OBS₄ .
11. A chart of what we do and do not know about 4-colorings of grids is here.
12. 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.

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.

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 &ge 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 &ge 1) = Prob(A > 0) ≤ Prob(|A-E(A)| > E(A)) ≤ Var(A)/E²(A) by Chebyshev's inequality. After simplifying we get Prob(A &ge 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.

--
Posted By Lance to Computational Complexity at 11/25/2009 05:31:00 AM

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.

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?