1. It wasn't quite a vote- it was YES if you thought there should be a free online CG journal AND you were strongly committed to it (I suppose willing to be editor or author). NO if you thought it was a bad idea, or NO BUT SOMEONE ELSE SHOULD (a good idea but you are not commited to it). I am so far removed from the community that I couldn't even vote NO BUT. (I will browse through ***SORELLE***'s Comp Geom Proceedings. The probability that I find an article I care about is 1/3--- every third year there is some article on Geometric Ramsey Theory.)
2. Reading the post and talking to ***SORELLE*** my impression is that the poster and ***SORELLE*** think running an online journal costs $0.00. The reasoning goes that authors, referees, editors, all work for free. If the authors do their own typesetting and there is no print version then the cost should be $0.00. Is this true?
3. A while back Elsevier had the editoiral board of Information and Computation (which I was on) meet in Boston to discuss the journal. From what they said I honestly believe that running a journal does cost money. How much is a fair question, but it does cost something. Running the computers where its all stored, maintaing stuff, does cost money. But I am not an expert on these things and I would like a commenter who is to comment on this.
4. One obvious cost---Elsevier paid for our flights, hotel, and dinner at a really good resturant.
5. There are three free on-line journals in math/tcs that I know of Electronic Journal of Combinatorics, Theory of Computing, and Chicago Journal of Theoretical Computer Science. If someone knows how they are doing, do they cost money to run, and if so how they get it, please comment. Also, are there others? How are they doing? Do they need money? Where does it come from?
6. One advantage of an online journal, which Electronic Journal of Combinatorics has, is dynamic survey articles. That is, these are survey's that are updated over time. (My favorite: Ramsey Theory Applications. And no, I didn't write it.)

For any finite coloring of NxN there exists a square such that all corners are the same color.

1. This can be proven from the Hales-Jewitt theorem. (Advantage: automatically get out the full Gallai-Witt theorem with this approach.)
2. This can be proven from the Gallai-Witt theorem trivially.
3. This can be proven by using VDW theorem on the diagonal.
4. This can be proven by using VDW theorem on the side.
5. This can be proven by directly. It has a VDW flavor to it but can be shown to HS students who have not seen VDW theorem (I've done it).

For any finite coloring of NxN there exists an s &ge 2 and an s by s² rectangle such that all corners are the same color.

1. Is there a proof either from scratch, from poly vdw, or from Ordinary HJ? If so then please comment.
2. Normally one asks for an elementary or (I prefer the phrase) purely combinatorial. Even so, I can't rephrase my question with this term since there is a purely combinatorial proof of Poly Hales-Jewitt. (See either Walters paper or the rough draft of the book on VDW stuff I am co-authoring with Andy Parrish pages 77-89.)

The EATCS Award is awarded in recognition of a distinguished career in theoretical computer science. The Committee, consisting of Catuscia Palamidessi (Chair), Paul Spirakis and Emo Welzl in charge of evaluating the nominations to the 2009 EATCS Award has come to the decision to propose Gerard Huet as the candidate for the 2009 EATCS Award in view of the excellent research contributions to theoretical computer science produced throughout his outstanding scientific career. The Committee unanimously shares the motivations contained in the nomination letter. The proposal has been unanimously approved by the EATCS Council. The Award will be assigned during a ceremony that will take place in Rhodes (Greece) during ICALP (July 5-12, 2009).

1. n the early 70's, Huet developed both resolution and unification for higher-order logic: these results have became the core of several modern systems that perform deduction in higher-order logic.
2. Huet has done fundamental research in the areas of rewriting and Knuth-Bendix completion. His writings in this area are extensive and elegant.
3. Between 1982 and 1989, Huet directed and contributed to the design and implementation of the CAML functional programming language. That language and its descendants have given academics and industries an efficient and well structured programming language.
4. In the 1990s, Huet and his students designed and built the first version of the Coq proof assistant. Today, Coq is one of the most used and trusted platforms for formalized mathematics and formal methods.
5. Huet has a broad culture inside and outside of computer science. He has made, for example, important contributions in other areas as well: he is the author of executable lecture notes; he is the designer of the Zipper data structure; and he has built the Zen toolbox for phonological and morphological segmentation and labeling of Sanskrit.

Barbara Liskov has won the 2008 Turing Award!

I spent the entire commercial trying to guess what company was paying for this. Should have recognized the IBM blue.

Consider the first two lines:

Math is the only language all human beings share.
Math can better predict financial markets…

Perhaps these days IBM should have left out the part about "financial markets". Though the New York Times Tuesday gave the credit (actually mostly blame) to the physicists.

--
Posted By Lance to Computational Complexity at 3/12/2009 05:25:00 AM

Homer has with him Baby Maggie, his dog, and a jar of poisons that look like delicious candy. (Homer: Oh, why did I take my baby and my dog with me when I went to buy poison! And why do the poison has to look so delicious!?) He needs to get all three across the river. He can only take one of them at a time in his rowboat. He can't leave Maggie with the poison. He can't leave the dog with the poison. (He CAN leave Maggie and the dog.) How does he do this?

1. The Fields Medal (established 1936, around $15,000). (Also see Wikipedia Entry.) (Note that the IMU also gives out the Rolf Nevanlinna Prize (as of 1982) and the Carl Friedrich Gauss Prize for Applications of Mathematics (as of 2006). The webpage indicates they are on par with the Fields Medal.)
2. The Turing Award (established 1966, around $250,000). (Also see Wikipedia Entry.)
3. The Milennium prize problems (established 2000, $1,000,000 per problem). (Also see Wikipedia Entry.)
4. The King Faisal International prize (established 1976, around $200,000). (Also see Wikipedia Entry.)

1. Money: But the Fields Medal, at $15,000, is still more prestigious then the King Faisal international prize.
2. Time: The Fields Medal and the Turing Award were established longer ago. At the time there weren't that many other prizes out there to compete with.
3. Focus: The King Faisal international award is for both Islamic Studies of various sorts and for science of various sorts. This makes it may make it harder to report on and talk about. The Fields Medal and the Turing award are focuses. Milennium Prize even more so.
4. Quality of the Winners: A quick glance at the people who have won the King Faisal International prize for Science who did mathematics shows that they made excellent choices. So this is not the issue.

1. I went through all of the exams and classified which problems were in physics and which were in combinatorics (to confirm some suspicions that I had- see next two points). The results are in this document. I am sure that if you were to do a similar classification you might disagree with me on some problems, but our tallies would not differ by much. (You can find the problems from 1985 until now here. Most years the problems and their solutions appear in the The American Mathematics Monthly.)
2. The older exams asked more about physics. To be more precise the exams have had 18 problem on physics: 14 of them before 1960, and only 4 of them since then (1973,1974,1975,1981). Why this trend? I suspect that before 1960 it was just assumed that a math major knew basic classical mechanics--- now it's not as universal an assumption. Any other ideas?
3. Combinatorics has been a relatively recent popular topic for problems. There have been 32 problems in Combinatorics. 21 since 1978. In my lifetime I have seen combinatorics become more part of the ugrad curriculum, so this may be the reason.
4. In 1953 one of the problems was to show (in today's terms) that if you 2-color the edges of K₆ then there will be a monochromatic triangle. This is now so well known that I doubt they would ask it.
5. What is better for a young math major to do: study for competitions like the Putnam exam, or do a research project? Both are certainly good. I've asked around and got the following responses.
   1. Several students have told me that taking the exam got them interested in some parts of math they had not heard of, so then they wanted to (and did) do research.
   2. Some other students told me that the exam is good since its a finite well defined goal that they can focus on. By contrast, for a younger (perhaps immature) student doing research is uncomfortably vague.
   3. Another student likened math competition people to people who know lots of words for SCRABBLE but don't know what they mean. I disagree. To understand answers to old exams and to generate answers to new exams you need to understand some real math. (I think that in World Champion Scrabble they should only give you 1/2 of the points if you don't know the meaning of the word.)
   4. There are many Putnam winners who went on to become research mathematicians.
   5. There are many Putnam winners who did not go on to become research mathematicians. I've heard it said of some of them that they could do a problem given to them but not come up with problems on their own. I am skeptical of this as an explanation since there are all kinds of people who and good and bad at all kinds of things. Certainly being a good problem solver does not decrease your problem-creation ability.
6. Personal note: I took the Putnam exam three times. My best score was a 33 (basically 3 problems right out of 12) in 1980. For one of the problems I felt a bit odd getting it right. I had a year long course in combinatorics (rare in those days) so I knew how to do it from nowledge not cleverness. How good is a 33? Respectable, but not worth putting in my essay to grad school. It was 125th in the country (I think out of around 2000) and my school (SUNY Stonybrook) gave me a copy of Godel-Escher-Bach since it was the highest score at the school. Joel Spencer proctored the exam and finished it, I suspect with a perfect score, in half the time.

1. In 2006 The Hungarian Government set up a website to take a vote on what to name a particular Bridge in Hungary. Stephen Colbert urged his viewers to vote for The Stephen Colbert Bridge. (At the time The Chuck Norris Bridge was leading in the vote.) The Government overturned it since Colbert is not Hungarian and he is not dead. They should have NOT allowed writeins OR not have an election.
2. In 2009 NASA set up a website to have a vote on what to name a room on the international space station. They already had two of the three rooms named: Unity and Harmony. I've read that they were hoping the last one would be Serenity- claiming that they wanted world peace to be a theme, though I think they were fans of the TV show Firefly. Once again Stephen Colbert urged his viewers to vote for Colbert. And this name won. NASA could overturn this (they will decide in April). I've read on websites statements like Stephen Colbert embarrassed NASA and NASA made the mistake of allowing writeins. However, if they just go with Colbert and say they are happy with it this will be far less embarrassing then overturning the vote. I hope the don't overturn it. But if they do then why have an election in the first place? They can say It was only a Poll but it sure looks like a election to me. But, to be fair, they have not overturned it yet so I can't be mad... yet.
3. When my nephew's wife was pregnant my nephew set up a website for people to vote on the name of the baby. No, Stephen Colbert did not urge his viewers to vote for Stephen as first name and Colbert as middle name. And my nephew did not allow writeins. But they didn't end up using the top vote getter! This upset the family terribly if by the family you mean Bill Gasarch and by upset you mean told them that they destroyed democracy. They named the kid George even though Al had won (this is a joke, though the rest of the story is true).

1. Should conferences have double-blind referereing? This was brought up by ***SORELLE*** who thinks that double-blind is good, and later followed up by ***LANCE*** who thinks that double-blind is not needed. I think conferences should have it to avoid bias and perceived bias, so I agree with ***SORELLE***. But that is not the point I want to make.
2. Should PC members be allowed to submit? This was discussed in this blog. 10 years ago I thought NO but over time I've changed my mind---it seems counterproductive to not allow some of the best people in our field to submit. But that is not the point I want to make.
3. Should these issues be brought up, discussed, with an actual chance of being CHANGED at various business meetings? I STRONGLY think so. Whenever these items are brought up they are shouted down without any real debate. (They are rarely brought up in the first place.) I imagine the following story: Alice goes to CRYPTO and someone brings up stopping doing double-blind submissions. Alice is among the people who shout it down giving the usual arguments against the change, but the real argument is because we've always done it this way. Later in the year Alice goes to STOC. Someone brings up having double-blind submissions. Alice is among the people who shout it down giving the usual arguments against the change, but the real argument is because we've always done it this way.

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;

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;