1. Show that for every set of three integers we can find two of them whose average is an integer.
2. Show that for every set of five integers we can find three of them whose average is an integer.

(Conjecture) For all k, every set of 2k-1 integers, there exists k of them whose average is an integer.

1. The UMCP competition asked for the k=2 and k=3 cases of the conjecture. They are true and easy.
2. I have done the k=4 case. It was tedious but not hard.
3. I think I have done the k=5 case but it was alot of cases so I may have missed one.

1. W(k) &ge sqrt(k)2^(k-1)/2 is an easy application of the Prob Method. The proof is so easy that I could not find it written down anywhere, so I wrote it down in the paper pointed to above.
2. W(k) &ge sqrt(k)2^(k-1)/2 can be proved constructively by the method of conditional expectations. This is also so easy that I could not find it written down anywhere. So I wrote it down myself in the paper pointed to above.
3. Berlekamp showed that, if p is prime, then W(p) &ge p2^p constructively. (I prove a slightly weaker result in the paper linked to above.) (Berlekamp's original paper can be found on my website of VDW papers: here.)
4. Using the Local Lovasz Lemma one can show that W(p)&ge 2^k/ek. This proof is nonconstructive and does not yield and almost-all result, so it cannot be turned into a randomized algorithm.
5. Moser and Tardos (above link) (and later Beigel with a different proof) showed that the LLL can always be made to yield a prob algorithm. Hence they have a randomized algorithm to obtain a 2-coloring of {1,...,2^k/ek} with no mono k-AP's. This is not a constructive algorithm in the way that Erdos or Spencer might accept, though it does yield a feasible algorithm.
6. Chandrasekaran, Goyal, Haeupler in the paper Deterministic algorithms for the Lovasz Local Lemma have a deterministic version of the LLL with slightly worse bounds. From their paper one can obtain: W(k) &ge 2^{k/(1+&epsilon)} via a poly algorithm.

1. The mean or median of all of the episodes.
2. The probability that a randomly chosen episode is rated above t. (Could also get into prob that it is within one standard deviation from t.)
3. The probability that a randomly chosen disc has an episode rated above t.
4. The probability that a randomly chosen disc has fraction f of its episodes rated above t.
5. Rate each disc in the DVD set for the entire season. The mean or median of all of these ratings.
6. The mean or median of the best season.
7. The mean or median of the worst season.

There is an absolute truth. People don't vote on mathematical things like 2+2=4.

1. AD is known to be true for A a Borel Set (Donald Martin proofed that).
2. AD contradicts the uncountable AC but implies the countable AC.
3. AD implies that every subset of the plane is measurable.
4. I don't think AD implies CH or not CH (are both AD + CH and AD + NOT(CH) known to have models?)
5. AD has a Wikipedia entry. This should not be taken as a sign that it is true of false. It should not even be taken as a sign that its well known. It just means someone put up an entry.
6. My wife thought AD was false in 1995 but true in 2005. I do not know what changed her mind. She is not a set theorist and had not thought about it in the intervening 10 years.
7. All finite games are determined so this is taking something true of finite games and assuming it is true for infinite games.

1. Geometry: Use Euclidean Geometry when appropriate, for example if you are designing a bridge, use Riemannian geometry when looking at space time, and use geometries when they are appropriate. So there is no correct geometry, its more of a right tool for the right job thing. So far Set Theory does not seem to have a strong enough connection to the real world for this to make sense. I supposed you use ZFC when dealing with most of mathematics, but I doubt you would ever say something like: When dealing with Quantum Mechanics its best to assume AD. So what can you use to decide what axioms to use? You may decide what axioms to use based on your tastes. For example see this prior blog posting. This is good for an individual but will not really work for the whole community. For example, I happen to like AD since I like a world where the Banach Tarski paradox is false. But that's just me.
2. People concerned with these issues in the early 1900's were much more passionate then we are today. They had strong opinions on foundations and on non-constructive proofs. Mathematicians commonly carried firearms. We are far less passionate today on these issues. As an example, there are today people who study constructive proofs and prefer them, but I doubt anyone today would reject a theorem that was proven nonconstructively. Why the change of heart? Possibly Godel's theorem, but also the fact that people in different parts of math can't talk to each other so they can't argue.
3. Another axiom of interest: The existence of Inaccessible cardinals. MOTIVATION: Take omega. If |X| < omega then |powerset(X)| < omega. Does any other cardinal have this property? Why should omega be so unique? Kappa is an inaccessible cardinal is such that if |X| < Kappa then |powerset(X)| < Kappa. Do such cardinals exist? The existence of an inaccessible cardinal large than omega cannot be proven in ZFC. An inaccessible cardinal would be a model of ZFC and hence would prove that ZFC is consistent (omega does not prove ZFC consistent since no proper subset of omega is infinite). It is known that ZFC cannot prove its own consistency (I think that's true of any theory but there may be some conditions.)
4. Penelope Maddy has two nice articles on why mathematicians believe what they do: believing the axioms I believing the axioms II Also good to read: Shelah's Logical Dreams

We may not use these books much but they will be good to have on your shelf if you go into theory.

1. There are some results in COLT that are of interest to CCC and vice versa. But there is not much overlap. That is, the papers at COLT would be out-of-scope at CCC. And vice versa.
2. CCC has its original roots in computability theory. The basic notions of reductions and completeness were adapted from computability theory. COLT has some roots in Inductive Inference (computability-theoretic model of learning) but the connection is much weaker. The PAC model, and the other models, do not really take things from Inductive Inference and adapt them.
3. Both conferences used to have more of the Computability-theoretic material but it is faded in recent years.
4. Both fields use tools from discrete math; however, virtually all of Theoretical Computer Science uses discrete math.
5. COLT is co-located with ML (Machine Learning). They have done this before (I'm not sure how often.) COLT would like to be relevant to ML and probably is. CCC does not have a (more) applied field that it would like to be relevant to. CCC co-locating with STOC since there is a overlap in the people who want to go to both.

1. There are people who normally can't go but now CAN go (e.g., CCC in Prague has 12(?) people from Prague, most of whom normally would have a hard time going). So- are there people in Israel who want to go? I would think yes since there is a strong theory community.
2. It is not too hard for the people who usually go to go. How hard will it be for Americans to get to Israel? For Europeans? I don't know.
3. The Guest Speakers (in this case Noga Alon and Noam Nissan) are close by thus saving on travel expenses. Actually, I had never thought of this one until I saw that they were the guest speakers.

FOCS and STOC only take technically hard results on problems that we already agree are worth studying. Papers that are truly innovative, starting new directions, have a very hard time getting into those conferences.

1. If you know of an innovative paper that DID make STOC or FOCS the then please leave a comment on it. Include the year the paper appeared.
2. If you know of a submission that was rejected that was innovative, that the authors would not mind if it was known the paper was rejected, comment on that. Include the approx year the paper was submitted.

1. Uganda is in the process of passing a law which would make homosexuality a crime with very harsh penalties, including the death penalty in some cases (See here for some details.) If Uganda offered us money to go to a conference, would we turn it down on those grounds?
2. When South African had Apartheid many organizations boycotted them for this reason. If they had offered money to hold a conference there, would we have done it? My guess is that we would TURN DOWN The money. Since our actions would have been part of a much bigger movement they may have been effective. If we are the only organization who does not go to China because of their Human Rights Policies I doubt it has any affect.
3. If Saudi Arabia offered a monetary prize (say $400,000) for advances in Mathematics would you turn it down because of the nature of the regime? (I'll be honest- I would take the money.)
4. Hyatt Hotels in Boston fires 100 of their workers, who are then known as The Hyatt 100. Should STOC/CCC not use their hotels for the 2010 STOC/CCC meetings? For this one there are other organizations boycotting so it may be effective to join it (I do not know what STOC/CCC are actually doing.) What if they reach a compromise that some of the workers are happy with and some are not? Then what do we do? Do we really want to get involved with the details of a labor negotiation? However, the orignial boycott might help get Hyatt to reverse their decision.
5. To protest Human Rights Violations in America (Gitmo, the treatment of the American Indians, Abu-Ghraib, the shooting of Randy Weaver, pick-your-favorite-cause) its not clear where you would decide to NOT have a conference. America is so large and diverse, and no one state or city did these things, that its not clear how you would express your outrage. Also, the government is not that connected to Academia as in other countries. The only thing I can think of is to not take money from the Military for a conference. But then the arguments goes better they spend it on Interactive Proof Systems Oracles then on Machine Guns.
6. We should NOT have a conference in California, or any other state where they voted against Gay Marriage. Or maybe not stay at the Marriott since they put alot of money on the anti-gay side. How about countries that do not allow gay marriage? (I apologize to the 3 readers of this blog who are against gay marriage if you find this notion offensive.)
7. We should NOT have a conference in any state that has laws against interracial marriage. Actually, I don't think there are any such states. But there may be countries that do not allow it. (I apologize to the 0 readers of this blog who think the government should make interracial marriage illegal. I also apologize to the 1 reader who thinks its a states right issues where states can decide for themselves.)
8. Should we ban Nazi Mathematics? See here for an opinion, actually the 88th Opinion of Doron Zeilberger.

1. The Fundamental Lemma was proven. I won't embarrass myself by even trying to blog on it, but will instead point to a blog that did report on it: here. I found out about it when I saw it listed in Time Magazine as one of the top science stories of the year. The results seems to be really important.
2. The Fundamental Pizza was proven. This was proven in 2009 but seems to have gotten attention on some blogs recently. Unlike The Fundamental Lemma this one I can state. Can I prove it? I doubt it--- it was conjectured 40 years ago. The paper is here. Here is the result:
   
   A waiter picks a point on a pizza and makes N slices through that point. Each slice has the same angle. One player gets every other slice and the other gets the other every other slice. Will they each get the same amount? This problem has now been completely solved:
   1. If the point is in the center then yes.
   2. If any of the slices happens to go through the center then yes. (Henceforth assume that no slice goes through the center.)
   3. If N=1 or N=2 or N &equiv 3 mod 4 then the person who gets the slice that has the center gets more.
   4. If N &ge 5 and N &equiv 1 mod 4 then the person who gets the slice that has the center gets less.

1. In 1978 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref FOCS 78).
2. In 1981 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref JACM 81).

1. In his FOCS 1978 paper (see also Journal version in JACM 1981) Yao proved the following:
2. In his JACM 1981 paper (original in conference version in FOCS 1978) Yao proved the following:

1. There are two players and they want to pick a random number between 0 and 5. They want the process to be such that neither player can bias the outcome. Each picks a natural number in secret. They are revealed, added, and then the remainder upon division by 6 is taken. Brother Edvin noted that the players really only need pick numbers between 0 and 5; however, he thought it best not to tell the players this since they will think they have more choice then they do.
2. What if its only one person. It is too easy to bias things. But Brother Edwin proposed the following in modern notation.
   1. Pick a 4-digit number x.
   2. Compute y₁=x²,
   3. y₁ will be 7 or 8 digits. Remove the two leftmost digits and one or two rightmost digits to obtain a 4-digit number z₁.
   4. Repeat this process four times to obtain z=z₄.
   5. Divide z by 6 and take the remainder.

One wonders if the failure of computer scientists to articulate the intellectual excitement of their field is not one of the causes of their current funding crisis in the U.S. Too often, policymakers, and hence funding agencies, treat computer science as a provider of services and infrastructure rather than as an exciting discipline worth studying on its own. Promises of future innovation and related scientific advances will be more credible to them if they actually understand that past and current breakthroughs arose from an underlying science rather than from a one-time investment in 'infrastructure.

It is high time the computer science community began to reveal to the public its best kept secret: its work is exciting science -- and indispensable to society.

1. Websites. For STOC there is an obvious website, and indeed it is there under Travel Support. This works for conferences. It does not work if the info is hidden deep in a non-obvious place OR if its not there and should be. This happens more than it should. Big Plus: Posting on a website is NOT intrusive like email.
2. Blogs: There are so many blogs and its not clear who reads which ones. Also, some do not do annoucements like this. However, blogs are not intrusive and some people who did not know the info now do.
3. Email: We all get too much and ignore lots of it. Not reliable. See this blog entry for more on that.
4. Twitter: There are still people who don't get tweets. I am one of them. Though I do read Lance's Tweets on the Complexity Home Page---to see how he tweets my posts.
5. Facebook: There are still people who don't do facebook. I am one of them. I may have to at some point. See here.

1. Johnny Cash's 10 Favorite Country Songs of all Time includes his own I Walk the Line (at number 1) and Folsom Prison Blues (at number 4). To be fair, they are awesome songs!
2. Oliver Stone's 12 Best Political Films of all Time actually lists 10 movies (films?) but then says Stone Notes: And two more with apologies: 11-12. JFK and Salvador. Because I never thought either could be made, much less be appreciated by a large audience. This strikes me as a good way of doing it- since 10 is the usual number on a list make it 12 and include two of your own and apologize for it. However, the movie JFK was way too long. The point of the movie was made more concisely here here
3. Federico Fellini's 10 All Time Favorite Films include his own 8 1/2 as number 10.
4. Lucille Ball's 10 Favorite TV Series has as item 10 and of course I Love Lucy.
5. Charles M. Schultz's 10 Greatest Cartoon Characters includes, at number 1, Charlies Brown and Snoopy.

1. Cash: When is the last time you used cash in a transaction that was over 20 dollars? Over 10?
2. Slide rules: I thought they were already gone gone gone. You can buy them off the web here. The site does not seem to think of them as antiques.
3. Truly blind dates: In my day we couldn't Google our dates ahead of time.
4. FAX machines: Not sure they are really going going gone. If they had come out earlier they would be far more popular. If they had come out later they would have been far less popular. Are they here to stay?
5. Secretaries: I can't imagine having someone type my papers for me or book a trip for me.
6. Tonsillectomies: I actually got one when I was 8. I hope that wasn't a mistake.

1. An Elementary Proof is one that does not use Complex Analysis. Basic Calculus is fine. This was the criteria when people asked for an Elementary Proof of The Prime Number Theorem. Such a proof was found by Erdos and Selberg. (See this paper for the history) Later Oliver Sudac (TCS, The Prime Number Theorem is PRA Provable, Vol 257, NOT Online) showed there is a proof in Primitive Recursive Arithmetic which is weaker than Peano Arithmetic. An interesting article on this which IS online is by Jeremy Avigad on all of this is at Number Theory and Elementary Arithmetic. From what I hear, the original proof is still the easiest way to prove it. (NOTE- Oliver Sudac, if you are reading this put your paper on line. If you do not then over time it will be called ``Avigad's theorem''.)
2. An Elementary proof is one that can be taught to a class of bright college students in about two hours. If you hear someone say Shelah's primitive recursive bounds on the VDW bounds is elementary this is what they mean. (See here. for the paper.) )
3. An Elementary proof is one that does not use advanced techniques. The original proof of Szemeredi's Theorem is rather difficult; however, it does not use advanced techniques. You could probably teach it to a class of bright college students in about two months. Even so, I would hesitate to call it elementary. It might be easier to learn the background mathematics for one of the non-elementary proofs rather than follow the elementary one.
4. An Elementary proof is one that some bright high school students can come up with during a High School Math Competition.
   1. The following is elementary: Show that any for any 3-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square.
   2. The following is probably not elementary: Show that any for any 4-coloring of the natural numbers there exists x,y that are the same color such that x-y is a square. I wanted to put it on the Maryland Math Competition to find out if it was elementary, but alas they didn't let me. I do not know of a proof that a bright college student could do on his own. The theorem is true by poly VDW thm; however, I would very much want to see an easier proof.
   3. The following is elementary: Show that if n is a power of 2 then if there are 2n-1 integers then some n of them sum to 0 mod n.
   4. The following is probably not elementary: Show that if n is any integer then if there are 2n-1 integers then some n of them sum to 0 mod n. The proof in here is elementary in that you could explain it to a bright college student in 30 minutes; however, I don't think they could come up with it themselves.
   5. In Elementary Particle Theory it is the particles that are elementary, not the theory.