Do 50-1 longshots in the Kentucky Derby ever come in?

(I delayed posting this until after The Belmont Stakes since I wanted to see if there would be a Triple Crown winner.
Alas, I'll have another was scratched. From what I've heard it was the right decision.)

Watching the Kentucky Derby my wife asked Do  50-1 shots every win? Since the Derby has been run 138 times it is likely that a 50-1 shot came in at least once.  That is, of course, if the odds were correctly figured.  Were they?

Essentially yes.  For the  ten longest longshots to win the derby I call a horse UNDERVALUED if they showed (came in 1st or 2nd or 3rd) in at least one of the other legs of the Triple Crown, and FLUKE if not. If there are other reason to say FLUKE I do so. Sometimes I say DON"T KNOW.

1. Donerail won in 1913 and was 91-1. (The longest long shot to win.) The prob that a 91-1 shot would NEVER come in after 138 races is (1 - 1/91)¹³⁸ which is roughly 0.217647740202952.  So while this is possible, it's more likely that such a long shot would come in. I could not find information on if Donerail ran in the Preakness or the Belmont Stakes.  Even though I don't know I'll say FLUKE with odds that long.
2. Mine that Bird won in 2009 and was 50.6-1 The prob that a 50.6-1 shot would NEVER come in after 138 races is (1 - 1/50.6)¹³⁸ which is roughly .0636355836570341.  Extremely unlikely, hence not at all surprising that such a horse won at some point, though surprising when it happens.  He finished second in the Preakness and third in the Belmont Stakes. UNDERVALUED!
3. Giacomo won in 2005 and was 50.3-1. Two horses that were roughly 50-1 have won the Derby.  I leave it to the reader to calculate the prob that only one 50-1 horse wins. I suspect that it is quite low, so having two of them win is reasonable.  He finished third in the Preakness and seventh in the Belmont Stakes. UNDERVALUED. I recall at the time thinking that betting he would show in the Belmont Stakes would be a sure thing. Alas, there is no such thing as a sure thing.
4. Gallahadion won in 1940 and was 35.2-1 (The website mislabels the picture as being from 2005 and misspelled the horses name by leaving out the a after the ll. What are the odds of that?) He finished third in the Preakness and did not show in the Belmont Stakes.  UNDERVALUED.
5. Charismatic won in 1999 and was 31.3-1.  He won the Preakness and came in third in the Belmont Stakes. UNDERVALUED!
6. Proud Clarion won in 1967 and was 30-1.  He finished third in the Preakness and Fourth in the Belmont Stakes. UNDERVALUED.
7. Exterminator won in 1918 and was 29.6-1.  Wikipedia has nothing on the Preakness or Belmont Stakes, so I assume he didn't run them. DON"T KNOW
8. Dark Star won in 1953 and was 24.9-1. A better name would have been Dark Horse. Was fifth in the Preakness possibly because he got injured running it, and that injury ended his career. DON"T KNOW.
9. Thunder Gulch won in 1995 and was 24.5-1. He came in third in the Preakness and won the Belmont Stakes. UNDERVALUED!
10. Stone Street won in 1908 and was 23.7-1.  Wikipedia does not have anything about his performance in the Preakness or the Belmont Stakes so I assume he didn't run in them. Wikipedia DOES report that his time, 2:15 1/5 is the slowest winner ever of the Derby. Based just on this I say FLUKE.
11. Animal Kingdom won in 2011 and was 20-1. He finished second in the Preakness and didn't show  in the Belmont Stakes (I could not find how well he did).  UNDERVALUED

Some comments:

1. To answer my wife's question- in 138 Derbies a 50-1 or better shot came in 3 times, which I think is about right, or at least not surprising. So they DO win.  Sometimes.
2. I was surprised that 5 of the 10 longest longshots were since 1999.  I would think people know more about racing now and so a real long shot is less likely. That may be the wrong way to think about it.
3. Should you bet on longshots? If you always bet x on the longest longshots in the Kentucky Derby, and (I have not checked this) The first, second, and third on the list above were the longest longshots when they ran, you would have roughly 190x - 135x = 55x dollars.
4. How do you tell if a long shots is undervalued (the odds should have been better) or a fluke (the odds were correct but something weird happened)? Here are three ways: (1) See how they did in the other two legs of the Triple Crown, (2) See their runtime in the Derby, or (3) for each race see if there were odd odd circumstances. For example, sometimes, it all depends if it rained last night.
5. By my measure there were six undervalued, two flukes, and two don't knows. I don't know if this means my measure is wrong.
6. Actually I'm GLAD that long shots sometimes come in. If not then they are being overvalued.  This is similar to why David Pennock wrote Why we're happy we got one prediction wrong on Super Tuesday. I saw his talk the same week as the Derby, and both jointly inspired this post. What are the odds of that?
7. I asked Dave Pennock about these issues and got two interesting thoughts from him:
   
   
   
   1. There is evidence racetrack odds are just about right (efficient) except with a slight "favorite-longshot bias" where favorites win a little too often and longshots not quite enough (people bet a little more than they should on longshots).
   2. It is an interesting hypothesis that odds should be less long with more information. I'm not sure that's true. With more information, the entropy of the distribution should go down, which intuitively might lead to longer long shots (and surer sure things)?
8. Dave also told me that there has been A LOT of work on this.  Here are some references:
   
   
   
   1. There is a whole edited volume on the subject: Efficiency of Racetrack Betting Markets
   2. Horse racing Testing the efficient markets model by Wayne W. Snyder.  J. of Finance, V. 33, No. 4, 1978.  pp. 1109--1118.
   3. Probability and utility estimates for racetrack bettors by Mukhtar M. Ali. J. of Political Economy, V. 85, No. 4, 1977, pp. 803--816.
   4. Utility analysis and group behavior: An empirical study by Martin Weitzman.  J. of Political Economy, V. 73, No. 1, 1865, pp. 18--26.
   5. Anomalies: Parimutuel betting markets: Racetracks and lotteries by Richard H. Thaler and William T. Ziemba.  J. of Economic Perspectives, V. 2, No 2, 1988, pp. 161--174.
   6. Gambling and rationality by Richard N. Rosett.  J. of Political Economy, V. 73 No. 6 pp. 595-607, 1965.
   7. Informed traders and price variations in the betting market for professional basketball games by John M. Gandar, William H. Dare, Craig R. Brown, and Richard A. Zuber.
   8. Information incorporation in online in-game sports betting markets by Sandip Debnath, David M. Pennock, Steve Lawrence, Eric J. Glover, and Lee Giles.  Proceedings of the Fourth Annual ACM Conference on Electronic Commerce, pages 258-259, 2003.
   9. How accurate do markets predict the outcome of an event? the Euro 2000 soccer championships experiment by Carsten Schmidt and Axel Werwatz.  Technical Report 09-2002, Max Planck Institute for Research into Economic Systems, 2002.
   10. Here are some fun books on the subject: Sharp Sports Betting by Wong and Calculates Bets by Skiena. I reviewed Skiena's book in my SIGACT NEWS book review column here.
   
   

Fortnoy's Complaint

During my daughter's 8th grade graduation last week, the teacher reading the names said "Molly Fortnoy...I mean Fortnow". I felt for Molly. When my name was first mentioned in a conference talk back in 1986 the speaker also said "Fortnoy". For the record my name is pronounced as it is spelled, like "He's going to the fort now".

I've been called Fortnoy many times from people in my generation or older. I put the blame on Philip Roth's book Portnoy's Complaint.

My father's birth name was Paul Fortunow. The name has Russian roots, possibly connected to Fortunoff. The 'u' in Fortunow is silent. Go ahead and try and pronounce Fortunow. You forgot the "u" was silent. So a couple of years before I was born (and before Portnoy's Complaint) my father changed his last name to Fortnow.

Foreigners usually have no trouble pronouncing my name. But once when I was checking in at the Frankfurt airport, the agents said something like "Here are your tickets Mr. Fornow". I said "Thanks but that's Fortnow". She responded  "If it was pronounced Fortnow there would be a 'u' after the 't'". I should have asked her where she was from. 

A new bound on 3-hypergraph Ramsey Number! Why wasn't it discovered earlier?

When a new result is first discovered one question to ask is Why wasn't it discovered earlier? We look at a result in Ramsey Theory from 2010 and speculate as to why it was not discovered earlier.

Let R(k) be the least n such that no matter how you 2-color the edges of the complete 3-hypergraph on R(k) vertices there will be a homogenous set of size k (that is, a set H of size k such that all 3-sets from H are the same color). R(k) is known to exist by Ramsey's theorem.

1. Ramsey's original proof (in 1930) gave astronomical tower-like bounds on R(k).
   
2. Erdos-Rado (1954) showed that R(k) is bounded by 2^24k.
   
3. Conlon-Fox-Sudakov (2010) showed that R(k) is bounded by 2^22k. (They did a lot more in their paper- they looked at asymmetric 3-Hypergraph Ramsey Numbers and developed a new framework for them.) See Hypergraph Ramsey Numbers on that page.)
   

Why are these results important?

1. An improvement on the 3-hypergraph Ramsey numbers automatically gives an improvement in the a-hypergraph Ramsey numbers for any a ≥ 3.
   
2. There is an exponential gap between the upper and lower bounds of R(k) and all of the a-hypergraph Ramsey numbers. Hence any improvement may be a key to closing that gap.
   

I have (with Andy Parrish and Sandow Sanai) celebrated the result of CFS with a survey of bounds on the 3-hypergraph Ramsey Numbers here. Proofs and intuitions and historical context of the results enumerated above are in our survey. (If you read it and have corrections please email them to us- we plan to put it on arXiv next week.) The techniques in this paper did not depend on any mathematics unknown to Erdos or Rado (or others) in 1954. (This is in contrast to, say, Conlon's paper A New Upper Bound on Diagonal Ramsey Numbers which uses quasi random graphs- a technique and technology unknown in 1954.) So why didn't someone else prove the result earlier? Our speculations may apply to other results that are proven with techniques that were already known.

1. The CFS paper develops a framework for upper bounds on asymmetric 3-Hypergraph Ramsey numbers that involving a game (not a FUN game, but a game). This framework is used to prove many things. If all you want is the bound on R(k) then you don't need the framework and you get a proof that, IN HINDSIGHT, gives you the bound in a way that Erdos-Rado could have done. That's alot of HINDSIGHT. (Our Survey gives the stripped down proof of just that result, without their game framework.)
   
2. Not that many people worked on it. Hence that individual people didn't get it is not surprising. Perhaps Erdos-Rado was happy enough to get the bound from tower to merely 2^24k. More generally--- if an entire community is looking at a problem then the question Why wasn't it found earlier? may have a global answer. If its just a few people, it could just be local things like After working on this problem she switched to Computable Algebraic Topology.
   
3. CFS are very very clever. This is another HINDSIGHT argument- AFTER its done it looks easy.
   

Other reasons that might apply in other cases, though not to the case at hand:

1. Timing and Luck should not be underestimated. A paraphrase from The Honors Class: Hilbert's Problems and their Solvers, the chapter on Hilbert's 10th problem, page 112:
   

   All of these people, Robinson, Davis, Putnam, others had been reading Number Theory books full of obscure facts. Matiyasevich had just read the third edition of Nikolia Vorob'ev's ``popular book'' Fibonacci Numbers. In that book, published in 1969, there was a new result about the divisibility of Fibonacci numbers. Matiyasevich used it to prove If F(n)² divides F(m) then F(n)divides m. This allowed him to solve Hilbert's 10th problem (building on work of Davis-Putnam-Robinson). Robinson had read that book, but not the third edition!

   With the web is this more or less likely to happen? I ask nonrhetorically. (The spelling I give for Matiyasevich is the one given in the book. I have seen different spellings.)
   
2. Everyone thought the negation was true. This was one reason why NL=coNL was proven as late as it was.
   
3. The problem itself wasn't looked at earlier. Some of the Time-Space tradeoffs for SAT may be in this category.
   
4. A groupthink sets in and people are all thinking the same way. Laszlo Babai noted this concern in his 1990 article Email and the unexpected power of interaction where he writes:
   

   But will the diversity of thought that now exists be preserved in an era when intellectual fashions are dictated by the strongest? Shall we see more Levins and Razborovs come out of the Kolmogorov school, bringing in so prominently different, yet profoundly relevant ideas?

   He was referring to email, but the tendency of groupthink may be even more of a tendency with the web. (Levins and Razborovs, not Levin's and Razborov's, is how it appears in the original article.)
   

SO, READERS- your turn! Leave comments on results that, once proven, the question arose Why wasn't this proven earlier? and speculate as to why. You need not write a survey of the area.

Mihai Pătraşcu (1982-2012)

Update: Visit the Memorial Website

Mihai Pătraşcu passed away Tuesday after a bout with brain cancer. Even though he hadn't reached his 30th birthday, he had already produced a number of major achievements in the algorithmic community. The theoretical computer science community lost one of its brightest young stars.

During STOC, Yevgeniy Dodis arranged to have Mihai at the business meeting while we announced him as a co-winner of the EAPresburger award which Mihai will receive posthumously at ICALP next month. The standing ovation that followed made for the most emotional moment I have ever seen at an academic conference.

We asked Mohammad Taghi Hajiaghayi to write some personal thoughts on Mihai:

Last night I heard the very sad news that Mihai Pătraşcu has passed away at the age of 29. Though I knew about his cancer from 1.5 years ago and several steps that he took to fight the cancer still the news was quite shocking to me. Mihai's carreer was short but very productive with his lots of great papers in e.g., STOC, FOCS, and SODA.


Indeed Mihai is the second close friend of mine and a bright star researcher from my MIT times that I missed in the recent years (the first one was Misha Alekhnovich who died in 2006 in a white-water kayaking accident in Russia).


I became familiar with Mihai since 2002 when he joined MIT. He was interested in working on date structure with Erik Demaine who was my Ph.D. advisor as well. As a result, I got know him much better esp. since both of us had common experiences in IOI (International Olympiad in Informatics). One of Mihai's early ground-breaking papers is

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality - Almost. FOCS 2004: 484-490

In this paper, an O(lg lg n)-competitive online binary search tree is given which improves upon the best previous competitive ratio of O(lg n). This was the first major progress on Sleator and Tarjans dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist. Indeed Mihai could formulate the O(1)-competitive conjecture as an approximation factor of some algorithm and we worked together for some time to prove the conjecture (that so far we could not:)). This was my first research experience with Mihai. Since then we always have talked about research (but we never had a joint paper).


In general Mihai and I were close friends and talked about all things. For example some times the people asked me about Mihai's personality especially because of some posts in his blog that were a bit controversial. I always told them Mihai is a very nice guy to work or chat with and those posts are indeed some concerns that everyone has in this mind, but Mihai is just brave enough to mention them loudly in his blog for the hope of some changes in the way that our community think (and anyone else including myself may agree or disagree with them).


After Mihai's graduation with Ph.D. from MIT which was only for 2 years (the same was true for Misha Alekhnovich), he applied for lots of places and got several very good offers. I was one of the people who encouraged him to join AT&T research labs, the place that I was there at that time. Finally Mihai decided to decline several faculty offers and join AT&T esp. to work with Mikkel Thorup (before joining AT&T he went as a Raviv Postdoctoral Fellow to IBM Almaden for one year). He has also chosen AT&T because of its place near to NYC that was good for his wife's career. As a result since July 2009, I was very happy to have Mihai, a star researcher, as my colleague at AT&T research labs and we talked more about everything during the past years. For example, later I wanted to teach hashing in my Introduction to Algorithms course at UMD; I asked Mihai and he gave me a very good overview about the field including an overview of his recent ground-breaking paper on simple tabulation hashing.


I first knew about Mihai's cancer in Feb 2011. At that time he was taking chemo before a brain surgery in March 2011. Just a day after the surgery he sent an email to David Johnson from the hospital that he already recovered and started thinking about his research problems. After this surgery, doctors, Mihai, and all of us at AT&T were very hopeful that the bad days for Mihai have been passed and Mihai will recover fully and produce lots of papers again:). Indeed everything was fine since then and Mihai even applied for faculty positions in Fall 2011 (he always considered his AT&T (industry) position as a long-term post-doc position). He asked for my opinion about his research statement and I was happy to give him some comments (esp. since I was also a person who first took the path of the industry and then academia). Again everything was fine until mid Jan 2012 that Mihai understood the cancer is back. Unfortunately this time the cancer was very strong and in a week or two he went to a wheelchair from a completely healthy position. I saw him several times at AT&T recently (when I visited there) and I always was very sad to see him on a wheelchair. To my mind, the best good news for Mihai since January 2012 was the fact that Mihai was selected as a co-winner of the 2012 EATCS Presburger Young Scientist Award for his ground-breaking work on data structure lower-bounds. He was very happy about it as he posted in his blog about it as well.


At the end I pray that Mihai's soul rests in peace and the research area of data structure lower-bounds in which he had several ground-breaking works becomes more prosperous due to his work.

Which Books to Keep?

Moving is an excuse to go through your possessions and weed out what you don't need anymore. Over my professional life I've collected two large bookcases full of CS, Math and Econ books and all the STOC, FOCS and Complexity proceedings from 1986 until they stopped publishing proceedings a couple of years ago. I also have a surprisingly large collection of complexity Ph.D. theses.

What do I move and what do I toss or give away? All the proceedings are now on-line. Maybe keep STOC 1987, my first conference paper? How many different editions of Li and Vitanyi's Kolmogorov tome do I need? How many Introduction to Theory textbooks? Publishers send them to me since it is the one undergraduate class I have consistently taught. I use Sipser, partly because he was my Ph.D. advisor, but mostly because it's a great book.

One approach is to toss everything. As some of my students say, if it's not on the web it can't be of much value. But I can't imagine life without some of the classics. When I want to prove something NP-complete, I still start by finding the closest related problem in Garey & Johnson to reduce from. For that one needs to skim through their list of problems. I have yet to see a good way to skim electronically.

I'm not a luddite. I do all my pleasure reading on the Kindle and read and mark up PDFs on my iPad. But when it comes to math books, we still haven't found a good replacement for paper. 

17x17: Paper that solved it available!/A contest inspired by it!/NPC result inspired by it!

Three new 17×17 items:

1. The paper (and some sequels) that SOLVED the 17×17 problem and the 17×18 problem are now available here. The first three papers are relevent.
   
2. There is a contest going on (it started Tuesday) INSPIRED by my 17×17 problem. In brief, they want to, for all c=2,3,4,...,21 have you find the largest n you can such that n×n can be c-colored without any monochromatic rectangles. See here for details. There is prize money! Do it for the fame AND the fortune! Deadline is Aug 31, 2012.
   
3. (I posted this before but got no comments, so I'll just say it again.) The problem of GIVEN a partially c-colored grid does there exist a way to extend it to a c-coloring of the entire grid, is NP-complete. See
   here.
   

Theory Jobs 2012

The theoretical computer science job market has mostly settled so time for the annual spring jobs posts. I set up a Google Spreadsheet that everyone can edit so we can crowd source who is going where next year.

The rules

• I set up several tabs (sheets), for faculty, industry, postdoc/visitors and students.
• People should be connected to theoretical computer science, broadly defined.
• Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
• You are welcome to add yourself, or people your department has hired.

This document will continue to grow as more jobs settle. So check it often.



Edit

STOC 2012- workshop and honored talks

I went to an enjoyed STOC this year. Today I talk about the workshops and the papers that either won awards or seem to be in the running. I may blog on other things, or expand on these, at a later point.

1. On Saturday there were two workshops, one on Computational Finance by Mike Kearns and one on the Unique Game Conjecture by Subhash Khot and others (sorry- I don't recall who the other speakers were, though they were quite good- in comments tell me and I'll add it. The program says Arora and Charikar, though they didn't speak. I assume they organized it.) (ADDED LATER- CLARIFICATION AND CORRECTION: There was a Comp Finance TUTORIAL that, when
   it was happening, was the only thing happending, and then later there were FOUR WORKSHOPS going on at the
   same time: Computational Sustainability, Algs for Dist and Streaming Data,
   Algs for Memory-Sensitive Computing, and Unique Game Conjecture.)
   
   1. Computational Finance: A distinguished theorist once told me that he is tired of working on problems nobody cares about so he will now work on Computational Finance. He gave a talk that began A Hedge Fund is a set of Boolean Formulas. By contrast Mike Kearns has actually worked with Lehman brothers (Is that why they were not bailed out? Unlikely.) on REAL questions that arise from Finance. The talk gave the needed background on finance and was excellent. One odd thing: I understood the entire thing. I am not bragging- I suspect that everyone who went did. If I was a snobbish pure math guy I would say Since I understood everything it couldn't have been any good. I of course feel the contrary way- it is WONDERFUL that I understood the whole thing. This is partially because he skipped details which is a good thing to skip. Slides are here.
      
   2. Unique Game Conjecture: For past work on this I can't do any better than Lipton's blog here, Khot's surveys and slides here. Khot's talk were a good review if you already knew the material and a good intro if you didn't. The other talks introduced a possible approach to disproving the conjecture. Very High Level View: There is an algorithm using the eight level of the Lasserre hierarchy of SDPs that MAY disprove the UQC. The usual counterexamples don't work. (I may not be stating this quite right.)
      Note that: (1) The community of people who study UGC seems to NOT have a consensu of whether its true or false.
      And those who think its TRUE or FALSE are not dogmatic. (2) It may be resolved before I do my next Poll. If not then I'll
      ask about it. (3) Even if its false it has lead to results of interest that do not assume it.
      
2. There were poster sessions for graduate students. In some ways these are better than talks since you can interact.
   (ADDED LATER- A commenter helpfully pointed out that the posters were NOT just for graduate students.)
   
3. Kasper Green Larsen won best Student Paper award and co-won Best paper award for The cell Probe Complexity of Dynamic Range Counting
   which proved better lower bounds in the cell probe model. The talk inspired me to read the earlier papers on this material.
   
4. Fiorini, Massar, Pokutta, Tiwary, de Wolf co-won best-paper award for Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. This paper seems to use Quantum Techniques to solve a classical problem.
   
5. Most of the time there were two tracks so there were two talks going on at the same time. There were five exceptions: the best student paper and the two best papers, and in addition three other papers (the numbers work out that way since the best student paper also co-won best paper award). I assume those three are being unofficially acknowledged as runners-up for best paper or some such (I do NOT have inside information). Those three papers were
   
   1. Julia Chozhoy's Routing in undirected graphs with constant congestion.
      
   2. Chan-Kleinberg-Shmoys Improving Christofides algorithm for the s-t path TSP For the METRIC TSP problem the best known upper bounds is STILL 3/2. WOW. There are some lower bounds (see On Approximation Lower Bounds for Tsp with Bounded Metrics for a list of them) but they are pretty weak-- (1+delta)OPT for some small values of delta. (Someone at the conference told me that better was known, like (4/3)OPT, but I have not been able to find it online- if someone can confirm please leave a comment.) This paper is NOT on the TSP, but on s-t-TSP. They give an upper bound of ((1+\sqrt{5})/2)OPT for this problem, breaking the bound of (5/3)OPT. I don't think any lower bounds are known on this problem. (Note that Euclidean TSP can be approximated arb well by the algorithms of Arora and Mitchell.)
      
   3. Virginia Vassilevska Williams Multiplying Matrices Faster Than Coppersmith-Winograd" has been discussed before in in this blog and also in a blog by Lipton. Virginia did not give the talk since she was close to giving birth (I don't know if she has yet). (Prediction: Ryan and Virginia's kid will prove NP is not in ACC₀ by improving the matrix mult bound. Title of the paper: Improving William's Lower Bound by Improving William's Upper Bound by Williams.)
      

STOC Business Meeting

Last night I ran my last STOC business meeting as SIGACT chair. It was a three-hour affair until the hotel staff kicked us out at midnight. Lots of highlights. I put many of the slides online if you want to see details.

We had a very large turnout for STOC, over 360 participants. Being in New York definitely helped as did posters and workshop sessions. There were 90 accepted papers out of 303 submitted.

There were two best paper winners:

• “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”  by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf
• “The Cell Probe Complexity of Dynamic Range Counting,” by Kasper Green Larsen

Larsen also won the Danny Lewin best student paper award. There were three other papers considered strong enough to merit a single session talk.

Sampath Kannan won the SIGACT Distinguished Service Award for his work promoting theory at the National Science Foundation.

Both the SIGACT Distinguished Service Prize and the Knuth Award will be given annually for now because we have many excellent candidates for both. The Knuth Prize will be given in even years at FOCS and odd years at STOC.

SIGACT elections are still going on. Please vote if you are a SIGACT member and haven't done so.

Skipping ahead (so this doesn't become a three-hour post) FOCS 2012 is at Rutgers, ITCS 2013 in Berkeley, SODA 2013 in New Orleans, STOC 2013 in Palo Alto joint with Complexity and FOCS 2013 (and every two years thereafter) hosted by the new Simons Institute at Berkeley. 

2013 STOC PC chair Joan Feigenbaum described a new multi-tier structure experiment for her program committee. 

Finally László Babai led a discussion on ACM publication policies. More on that in a later post. 

Meetings/Conferences/Workshops/Seminars- whats in a name?

In June 11-14 will be a new workshop: Algorithmic Frontiers.




How many venues do we have for meetings?

1. What the call themselves:
   Meetings (e.g., MATHFEST), Conferences (e.g., STOC), Workshops (Barriers), Seminars (e.g., Dagstuhl), Tutorials, Lunches. More?
   (six options)
   
2. Criteria for getting a paper in: Refereed (e.g., STOC): lightly refereed (I think MATHFEST), unrefereed, talks-by-invite-only (Algorithmic Frontiers, Barriers)
   (four options)
   
3. Participants: Open (most)or by-invite-only (Dagstuhl and Bertinoro) (two options)
   
4. Size: This is more informal. However, CCC is small (100), STOC is larger (around 400), FCRC larger still, and Supercomputing is expecting 11,000. Medical conventions can get around 20,000.
   (five options, though could be more or less depending on your mood.)
   
5. Variety of activities: A venue can have any combination of the following: contributed talks (unrefereed), refereed talks (typical STOC), invited talks, rump sessions,
   tutorials, workshops, short courses. (128 combinations, though in reality only about 5 options actually happen, so I'll take it as 5)
   
6. Length: Number of days can be anything from 1 day to 2 months. However, I don't think all 60 options really exist. I've seen 1,2,3,4,5 days, 1 week, 2 weeks, 1 month, and 2 months. nine options.
   
7. Expense: Either expensive or VERY expensive.
   

So that would be 6x4x2x5x5x9x2. That's a lot! Of course its far far less since, for example, an invite-only gathering can only have invited talks. I would guess its more like 5 types. And some are inconsistent (e.g., STOC sometimes has tutorials and sometimes doesn't).

Algorithmic Frontiers seems to be a 4-day open workshop that has invited talks only. I don't know how big it will be but I would guess between 100 and 200.

Do the gatherings that we go to work? As my Software engineering friend Jim Purtilo often says If you don't know your goals you are not going to achieve them. So, what are the goals? Ultimately to help both us as individuals and us as a community in our research. The hope is we learn things and get inspired to work on problems. And these can be done by the formal talks in the ballroom and informal talks in the hallways. Does this happen? Yes. Is it cost effective (not just money but time)? Debatable, as this and other blogs have debated. Here are my experiences. What are yours?

1. DAGSTUHL SEMINARS. These are specialized one-week long meetings by
   invitation only. The talks need not be on the latest/greatest thing and hence are understandable. (I've been to DAGSTUHL- Complexity 3 times.)
   
2. Bertinoro is similar to Dagstuhl. I've been to the RATLOCC 2011 and
   RATLOCC 2009 which are on Ramsey Theory and Logic. Here there were even more talks
   that were surveys or historical-perhaps because math moves slower than computer science.
   If the talks were on the INTERSECTION Of Ramsey Theory and Logic then it would be too specialized.
   (I've worked in both, but not quite together.)
   As is, its a nice mix.
   But the main point- I understood the talks.
   
3. The Center for Intractability sponsors workshops which anyone can go to
   but the speakers are picked by them. I've been to one of the Barriers workshops and it was very good. The speakers have more time then at conferences,
   which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
   
4. The last few CCC's and STOC's that I've gone to I have enjoyed and gotten stuff out of, but not as much as the smaller venues.
   Partly because the talks are shorter.
   which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
   
5. MATHFEST is nice in that there is a VARIETY Of activities- workshops, seminar, tutorials, invited talks.
   Very large which is both good (that's why they can have all of these things and bad (I never met the same person twice).
   
6. One of my colleagues, Jeff Hollingsworth, is organizing SC12, Supercomputing 2012.
   This will have 11,000 people at it. The program committee has over 100 people
   on it. This seems... large. They seem to have a variety of activities
   so it more like MATHFEST.
   
7. Of course the talks are only part of the reason to go to these things. Even so, for me they are a big reason.
   

What venues to YOU get the most out of? Why or why not?

Gödel Prize

The ACM announced the 2012 Gödel Prize awardees, three seminal papers in algorithmic game theory. The prizes themselves will be presented at ICALP in Warwick in July.

Elias Koutsoupias and Christos H. Papadimitriou: Worst-case equilibria, Computer Science Review, 3(2): 65-69, 2009.

Tim Roughgarden and Éva Tardos: How Bad Is Selfish Routing?, Journal of the ACM, 49(2): 236-259, 2002.

Noam Nisan and Amir Ronen: Algorithmic Mechanism Design, Games and Economic Behavior 35: 166-196, 2001.

The first paper introduced the price of anarchy. The second applied price of anarchy to routing problems. The third applied algorithmic techniques and competitive analysis to auctions.

Congrats to all the winners.

Wall Street Complexity

There is much blame to go around for JPMorgan Chase's two billion dollar loss last week but part of that blame came back to us. In a New York Times web piece, How Moore’s Law Affects Wall St. Trading, Quentin Hardy argues

Faster, cheaper computing makes it possible to create more and better models for calculating cash movements, which can be turned into trading instruments. Areas like leasing, mortgages and project finance have exploded – as has the entire financial derivatives market — thanks to cheap computing...

Soon, it becomes nearly impossible to say what is going on where, and you get events like the 1998 blow-up at Long Term Capital Management, the creation and destruction of the subprime mortgage market in 2008 and perhaps even the “flash crash” in 2010. JPMorgan’s loss seems to be the latest in that series.

I've argued the dangers of reducing computational friction before. But here computational complexity comes in a different way. A derivative is just a function of current and future security prices. But a derivative complex enough can have a behavior that even its creator cannot understand. The Clay Math Institute offers a million dollars to settle "P v NP" but it cost Chase two billion.

So THATS why the 17x17 challenge was so hard. Or maybe not.

On November 30, 2009 I posted the famous 17x17 challenge:

(Paraphrase) Find a 4-coloring of the 17x17 grid that has
no monochromatic rectangles. For $289.00. It was solved in 2012
by Bernd Steinbach and Christian Posthoff (I posted about it
here
and will post their paper when they make it it is public, which should be soon.)
Even though it was solved, it seemed to be a hard problem.

On April 28, 2010 (before the problem was solved)
I wondered WHY it was so hard and posted the following question:

(Paraphrase) Consider the following problem:
Given (N,M,c,f) where f is a partial c-coloring of NxM,
can f be extended to a total c-coloring of NxM (without mono rectangles)?
Is this problem NP-complete?

Kevin Lawler emailed
me a sketch of a proof recently! So YES, it is NP-complete!
I cleaned it up, wrote it up, and put in a few other things, and the paper is
here.
(We will be posting to arXiv after we get comments from this blog.)

1. Does this really show why the 17x17 challenge was hard?
   Not really since the 17x17 challenge is just one instance.
   
2. Does this show that grid coloring problems are hard in general?
   Not really since the case we are really interesting in is where
   f is the empty function. While we do not believe this case is
   easy, we have not ruled this out.
   
3. What can we show about the algorithmic complexity?
   The problem is FPT. For fixed c its in time poly(N,M)+O(c^c4).
   

This is a problem for hardness-of-Ramseyian numbers in general. While it seems as if computing (say) Ramsey Numbers is hard, there is no real proof of this. Related problems have been studied by Marcus Shaefer here.
While this work is very interesting
it is NOT the same as showing that finding Ramsey Numbers is hard.I suspect that to prove such things we need a new framework for
lower bounds.

Paying to Publish

You proved a nice theorem, wrote up the paper and submitted it to a major computer science conference. Your paper was accepted! Congratulations. Now pay up.

An author of every paper accepted at a CS conferences is expected to present that paper at the conference. To do so requires at the least paying the registration fees, travel and lodging to go the the meeting. That can easily run one to three thousand dollars (or more) depending mostly on how far you need to travel.

You can use grant money for these expenses. Some conference offer support to those who need it, particularly students. CS departments will often help out if needed. Sometimes people pay out of their own pockets and, in any case, the funds come from limited pots that could have been used for other purposes.

In the "old days" this was less of a problem. There were only one or two conferences relevant to one's field and you were probably going to those conferences anyway. Now as the field has grown and it has been harder to get your papers published in the strongest conferences, you may find yourself traveling just to give the talk. Even many major conferences don't draw many attendees who don't have papers in the conference.

We haven't seen an outcry of these expenses, say compared to the outcry over the cost of digital library subscriptions. Perhaps we consider attending the conference a "reward" for getting published.

We could just eliminate the conferences and publish the proceedings and post videos of talks, made at the home institutions, saving the field huge amounts of money. Then we could actually choose to attend conferences to meet people in our field instead of just talking at them.

Note: Elchanan Mossel had a similar observation in a comment on a recent post.

Is it well known that we need to redefine well known?

A LONG time (so long ago I was a guest poster, not a co-blogger)
I posted
about how calling things that are on You-Tube rare is odd
since ITS ON YOU-TUBE! ANYONE in the world can look at it!
I now have a Contrasting thought: Can something be
well known if its not easily found on the web?

Last week I
posted
a proof that the intersection of a CFL and a REG lang
is CFL that did not use PDA's. I thought it was NOT new and indeed, the
comments politely gave me the proper reference.
So far, so good. But wait--- some of them called the proof Well Known.
Can a proof be well known if its not on the web?
The notion of a proof being well known has always been problematic
since one wonders what the scope is.

1. Addition
   being commutative is well known but might not
   to my 5-year old niece.
   Someone emailed me that I should take this opp to teach her
   about noncommutative algebras.
   
2. Binary search is well known but might not be known to my (then)
   8 year old great nephew.
   Some said I should use this opp to teach him logarithms.
   
3. Induction is a well known technique but it still puzzles some undergraduates.i
4. The poly vdw theorem
   is well known among mathematically inclined
   high school students in Maryland but
   is not even that well known among combinatorists.
   

The point really is well known to who?. But now with the web we can ask a more focused question: Can you find it easily? The proof I posted was not one that I found on the web. So here is what I want your thoughts on:

1. Should we redefine our definition of
   
2. If I were to make an article out of the three short notes on CFL's
   that I posted about, and submit to Math Archives,
   would that help the problem of what is easy to find
   or would it just clutter up Math Archives making things hard to find.
   (I would of course provide all references and make NO claim to
   originality.)
   
3. Should I post to Wikipedia?
   
4. Will the web ever replace
   asking someone who knows stuff?
   

Microsoft saves the Yahoo NY Researchers

I started working with David Pennock on prediction markets back when we both were at the NEC Research Institute in New Jersey a decade ago. After a major reorganization the dropped basic research from their mission, I went back to academics but David stayed in industry research first at Overture which soon was swallowed up by Yahoo. He ended up at Yahoo Research New York in a small but amazingly strong research lab including machine learning theorist John Langford and social scientist Duncan Watts. But with a new Yahoo CEO and Prabhakar Raghavan and Andrei Broder's departures for Google, it  became clear that the days of Yahoo research were numbered. 

Today Microsoft announced that they are hiring 13 researchers from the Yahoo lab including David, John and Duncan as they start a new Microsoft Research Lab in New York, initially led by Microsoft New England director Jennifer Chayes. Lots of nice coverage from the New York Times, All Things D,  blog posts from Jennifer and John, and a pictorial take from Chris Maase. Not the first time Microsoft has done something like this, Microsoft Research Silicon Valley got its start by hiring several researchers from the old Xerox PARC.

I'm happy the Yahoo researchers found a great home but I also mourn the loss of yet another company abandoning basic research in computer science.

Berkeley Wins the Simons

As reported today in the New York Times, the Simons Foundation has chosen U. C. Berkeley to host the new Simons Institute for the Theory of Computing, a $6,000,000/year center for studying core theoretical computer science and its applications to other disciplines. There will be 70 researchers (faculty, postdocs, grad students) at any given time affiliated with the Institute.

This will be a game changer for CS theory.

Is Moore's Law Good for CS?

Roy Friedman writes a blog post on The Expected End of Moore’s Law is Good News for Computer Science.

For a long time, people got used to being lazy. If computers become twice as fast every 1.5 to 2 years, there is no point in investing much efforts in writing efficient code. If something does not run fast enough, simply wait for the next generation of Intel x86 and everything will be resolved. In particular, CPUs became fast enough that traditional programming languages and efficient data structures and algorithms were being abandoned in favor of high level scripting languages whose most sophisticated data structure is an associative array. Suddenly, every Joe-hoe could become a programmer developing sophisticated Web applications with no effort  – no need for hard earned computer science degrees anymore.

Let's ignore the issue as to whether Moore's law is really coming to an end (Moore's law has had 5-10 years left in it since Gordon Moore developed his law). Friedman misses the bigger point, an end of Moore's law will do great harm to Computer Science.

Friendman's mistake is to assume that people always have the same problems to solve. Suppose computers stopped getting more powerful fifteen years ago. Machine Learning as we know now would not have been possible. Nor would we have the advances in graphics, robotics and virtually every other area of computer science. A good deal of CS systems research goes into making these new machines even more efficient, secure and reliable.

Even in theoretical computer science, the advances in computer technology make our work stand out. As we try to tackled larger problems asymptotic algorithmic techniques start dominating the running time. While we can now brute-force solve NP-complete problems on moderate input sizes, as computer performance improves, so does the thirst for solving even larger challenges and the P versus NP problem becomes a harder monster to slay.

Sure Joe-hoe can wait a year or two for his application to run fast without new coding ideas. While he waits Sam-ham takes advantage of new technologies making Joe-hoe's applications out of date.

Without the increased power of computers, we all become hackers to make our programs run better and that is not computer science.

Hanan Samet wins Kanellakis Prize!

(

1. Symposium on Turing in Princeton in about a month
   
2. UMCP is doing a job search for a lecturer
   
3. New York Area Theory Day
   

) The Paris Kanellakis Theory and Practice Award for 2011 went to Hanan Samet from University of Maryland at College Park. See here for the details. He works on data structures THAT PEOPLE ACTUALLY USE! The Kanellakis price honors Theoretical accomplishments that have had significant and demonstrable effect on the practice of computing. This raises the question: What theory accomplishments are
good candidates for the prize (that have not already won it)?

I left Push Down Automata out of my class and learned some things!

This semester in the Ugrad Course titled Elementary Theory of Computation
(Syllabus: Reg Languages, CFLs, Computability Theory, P and NP) I decided to NOT
teach PDA's. I mentioned them and told the students they were equivalent
to CFG's but nothing more.

This lead to a NEW (to me at least) piece of mathematics!

Proving

X={a^nb^nc^n | n ∈ N}

is NOT a CFL is easy using the pumping theorem.
Consider

Y={w | number of a's, b's and c's in w is the same}

How do you prove Y is not regular?
Why don't you just intersect Y with a^*b^*c^* to get X which
you know is not a CFL? I hear you say.
AH- you need to know that CFL intersect REG is CFL.
If we had the PDA/CFG equivalence then this would be an
easy cross product construction. But now?
SO, we need a proof that CFL intersect REG is CFL
that ONLY uses CFL's. That is, DOES NOT use PDA's.
Here is a proof.
We do not believe it is new but have not been able to find a reference.
If you know a reference please comment.
(NOTE ADDED LATER- The commenters politely provided a reference
and I have put it into the paper.)

Another point of interest: How do you show that REG is a subset of CFL.

1. 
   Normally you would note that DFA's are just PDA's without a stack,
   hence every lang recognized by a DFA can be recognized by a PDA,
   and then use PDA/CFG equivalence. I could not use this.
   
2. 
   You could use the proof that any DFA language is a left-linear grammar
   (left linear only has productions of the form X-->aY)
   and this is nice since, in fact, they are equivalent.
   Here is a proof.
   I ended up not doing this but I will next year
   when I do the course.
   
3. 
   On the midterm I had the following question:
   
   

   Recall that if α is a regular expression then $(α) is the
   set of strings that α generates.
   Recall that if G is a CFG then L(G) is the set of strings generated by G.
   
   Prove the following by induction on the formation of a regular expression:
   For all regular expressions α there exists a Context Free Grammar G
   such that L(α)=L(G).
   You cannot use PDA's (Push Down Automata). (If you do not know what this is,
   do not worry.)

   
   I could only ask this BECAUSE they had not seen PDA's or Left Liner Grammars.
   Of the 40 students about 20 got it right.
   
   
4. 
   One of my students, Justin Kruskal, wondered how to go from a DFA directly to a CFG
   (recall that he had not seen left-linear grammars).
   It is interesting to see what untainted students come up with on their own.
   He came up with a proof
   which is
   here.
   It is a weaker result than the left-linear grammar equivalence, but its his!
   

Questions for YOU, the readers.

1. 
   What do you think of leaving out PDA's? (I may heed your advice
   next spring when I teach it again.)
   
2. 
   Is the proof I point to that CFG intersect REG is CFG, that only uses CFG's, new?
   If not please give a reference. A comment like Bill you idiot, this is a well known proof
   that I have neither a reference nor a website to point to.,
   is not helpful. If you DO have a reference or website to point to you can call me whatever you like.
   
3. 
   Have you ever learned some new math be leaving something OUT of a course?
   

CS in the Sunshine State

As many of you've heard the Dean of Engineering at the University of Florida is planning deep cuts to the Computer and Information Science and Engineering Department (CISE) and focusing its mission solely on teaching. Here is the relevant part of her plan.

Roughly half of the CISE faculty would be offered the opportunity to move to Electrical and Computer Engineering, Biomedical Engineering or Industrial and Systems Engineering.  These faculty would continue to support the graduate and research mission in the Computer Engineering degree track.  The choice of which faculty and which departments will be made based on fit with the research program and with the receiving departments. Staff positions in CISE which are currently supporting research and graduate programs would be eliminated.  The activities currently covered by TAs would be reassigned to faculty and the TA budget for CISE would be eliminated. The faculty remaining in CISE would then focus their efforts on teaching and advising students in the existing Computer Science BS and MS degree programs, offered through both the College of Engineering and the College of Liberal Arts and Sciences.  Their assignments would change to reflect this new educational mission with sole focus on delivering quality education for students in these degree programs.  Any faculty member who wishes to stay in CISE may do so, but with a revised assignment focused on teaching and advising.

In other words Florida is eliminating core Computer Science research, something that makes no sense for a state flagship research university in this day and age. There is a website and petition protesting the move which has caused the Dean to respond. Perhaps because of geographical closeness, this was a big topic of discussion when I was down at Georgia Tech last week. The current and founding Deans of the College of Computing at GT wrote strong letters to the Florida president. The CRA has also expressed their concern.

Certainly the president and dean deserve much of the blame to allow the targeting of computer science at Florida. But as Steven Salzberg of Forbes points out, the real villains lie in Tallahassee with a governor and legislature that has cut funding for the school by 30% over the past six years.

How important is the PROOF of Cooks theorem for my ugrad class?

I am teaching Automata theory this semester. The topics are basically (1) Regular Languages, (2) Context Free Languages, (3) Decidable, undecidable, and c.e. sets, (4) P, NP, NP-completeness.

Other things can be added like Primitive Recursive Functions, the arithmetic hierarchy, the polynomial hierarchy.

I am considering NOT proving Cook's Theorem. State it YES, say how important it is YES, but prove it NO. I am not sure if I want to do this. This post is an attempt to get some intelligent comments on this. My mind is not made up yet so this is I raise the question TRULY non-rhetorically. Some thoughts:

1. The proof is coding a Turing Machine computation into a formula. It is interesting that you can do this. The details of it are not so interesting.
2. The very good students (I would guess 5 out of my 40) will get it. The bad students never get it. I am oversimplifying--- and if this was a reason to not teach a topic I may not have much of a course left.
3. The time spend IN CLASS on this is not so much- one lecture. The time spend in OFFICE HOURS on this re-explaining it is a lot. And its not clear that it helps.
4. Showing them NPC reductions is more important and more interesting. This is what I would put in instead. I usually only get to do a few.
5. Cook's Theorem is SO fundamental that the students should SEE a proof of it even if they don't understand it. but I am not a fan of they should see it even if they don't understand it.
6. Cook's Theorem, like many things, you don't get the first time you see it, but you do the second, helped by having seen it once.
7. Even if we now they mostly won't get it, we want them to know that we WANT them to get it.
8. Students should know that the proof that SAT is NP-complete goes all the way back to the machine model (very few other NP-completeness proofs do). Is it good enough to TELL them this. I would DEFINE Turing Machines, SAY that you CAN code a computation into a formula, but not actually do it?
9. I like to teach things that I can ask problems about. Cook's theorem IS okay for this- I usually show how to make a formula out of some TM instructions and leave as HW making a formula out of other TM instructions. Even so, not that much can be asked about it. The students have a hard time with this (Much more so than other parts of the course) so I wonder if its too much sugar for a cent.
10. I teach this course a lot so I want to mix things up a bit. I realize this is not really a good reason for the students.
11. An argument for: See how it goes! The decision I make this semester need not be what I always do.

Some Announcements

STOC early registration deadline is Thursday. This year STOC will have both tutorials and workshops and its second poster session. Hope to see you all there.

The Simons Foundation is offering Ph.D. Fellowships in Theoretical Computer Science. Deadline May 1.

Finally a big congratulations to Josh Grochow who defended his thesis yesterday at the University of Chicago. Josh was co-advised by Ketan Mulmuley and myself and he'll be joining Toronto as a postdoc next year. Josh is my seventh and last Ph.D. at Chicago.

ACM/IEEE Curriculum 2013

[STOC 2012 Early Registration Deadline Thursday]

On a roughly ten-year cycle, the ACM and IEEE Computer Society get together to create a list of core topics that every getting an undergraduate CS degree should know. The joint task force has a strawman draft proposal and would like your comments for a final report hopefully next year.

This version breaks the requirements into Core-Tier 1 and Tier 2 with the more critical material in Tier 1 and also suggests some elective topics.

In Algorithms and Complexity there is a combined 21 lecture hours of material for Tier 1 and Tier 2 that should comfortably fit into a single quarter long course though that seems aggressive given the list of material. That is built on 41 hours of "Discrete Structures" that includes basic combinatorics and proof techniques. It's a testament to the fundamental importance of theory that it holds more core hours than most other areas.

While I'm always wary of outside committees setting courses and topics, these reports do give guidance in what the "community" believes are important topics for all well-trained computer scientists to know. They can heavily influence curriculum in theoretical computer science especially at the too many CS departments that don't a significant theory group. So take a look at the draft and give your comments to the task force.

Unique Golf Winners

In the Masters Golf Tournament held last weekend there were 55 players who had a final score between 10 under par and 9 above. By the pigeonhole principle one would expect many players to have the same score and in particular multiple players to have the best score. There was a tie for first that required a playoff.

But this is the exception, there were only four playoffs in the last twenty years of the Masters. In most years the Masters tournament has a unique player with the lowest score. Why?

I used Golf Tournaments to motivate the Mulmuley-Vazirani-Vazirani isolation lemma. If you have a collection of sets over {1,...,n} and choose random weights w₁,...,w_n from {1,...,r} let the weight of a set be the sum of the weights of its elements. The MVV lemma states there will be a unique maximum weighted set with probability at least 1-n/r.

It's a cool lemma with a short proof: you argue that with high probability each element i is either in all or none of the max weighted sets.

So how do I tie the lemma to golf tournaments? Actually I don't see a direct connection. But the spirit is the same.

I'll be on that list until the day I die. Or later.

How hard is it to get OFF of lists?

1. Univ of MD at College Park (UMCP) Professor Carl Smith was an editor for JCSS before his death in 2004. I put together a memorial issue of JCSS in his honor that appeared in 2008. SO HOW COME HE IS STILL GETTING ISSUES OF JCSS AT UMCP IN 2012? Normally I would email JCSS about this, but whenever I do that they stop it for a while and then it starts again. So I am not going to bother.
2. I recently got the following email:

   
   William Gasarch
   SIGACT News
   
   Hi William,
   
   The winners of Russia's prestigious Debut Prize are
   presently in the U.S.  The newest of the winning books
   is Irina Bogatryreva's Off The Beaten Track which
   contains her story and two others about hitchhiking in
   Russia.  Irina is also available for interviews as she
   speaks English fluently!
   
   Please let me know if you would like to receive a copy
   of this new and interesting novel.
   
   The Debut Prize winners will be visiting select cities
   (Washington, Boston and New York) during their stay and
   will also return in June for BEA.
   
   I look forward to your thoughts.
   
   Best,
   Shirley
   

Why did I get that? As SIGACT NEWS book review editor I am on lists of book review editor. Technology is sophisticated enough generate lists of book review editors. I suspect it is not cost effective to figure out which editor is appropriate for which types of books since email is free. I have sometimes gotten actual books in the mail that are not math or CS--- that seems like more of a waste of the companies money (though the Biography of Ted Kennedy that I got was a good read.)

Is this a problem? Overall yes since it costs society something (money? time?) to have people (even dead people) on lists where they shouldn't be. But there does not seem to be an incentive on anyone who could fix it to fix it.

Guest post on Tom Cover by Yoav Freund

(Details on registration and student travel awards for the 2012 IEEE Conference on Computational Complexity in Porto available at here.

New York Area Theory Day information here.)



Tom Cover passed away recently. Today we have a guest post about him from Yoav Freund which was written with help from Gabor Lugosi, Nicolo Cesa-Bianchi, Avrim Blum, Rob Schapire, Sanjoy Dasgupta and Manfred Warmuth.

Tom Cover was a leading light, a mentor and an inspiration. I was shocked to hear of his passing away. It was only a few weeks ago that I saw him in the recent ITA conference in San Diego. As usual, engrossed in conversation with a young colleague, gesticulating with his long arms to punctuate his words.

I was first introduced to Cover's work when, as a graduate student in UCSC, I read the classical book of Cover and Thomas on Information theory. Lured by the psychedelic cover I was enchanted by the lucid examples (betting in the horse races) and the elegant math. Like me, many computer scientists were introduced to the deep connections between probability, information, coding and prediction. It is a standard reference for information theory in computer science.

Beyond the book, Cover wrote wrote many of the foundational papers in information theory and its applications. A very partial list of his contribution include his work with Peter Hart on the convergence of the nearest neighbor classifier, His work on the capacity of linear classifiers preceded Vapnik and Chevonenkis. His work on finite memory algorithm for deciding whether the bias of a coin is rational or irrational is a beautiful mind-bender. His papers on gambling and portfolio management started much of the work on online learning.

Speaking of online learning, Cover took part in the first workshop on online learning that was held in UC Santa Cruz at 1992. Cover, with his typical sense of humor, suggested we call the workshop something for nothing. Later we had a bon-fire by the beach, I will always remember Cover as he was that day, a brilliant scientist, a wonderful communicator, a pursuer of beauty and of fun.

Annotated Bibliography

There's also his work on "Nearest neighbor pattern classification" (mid-60s, with Hart).

Yes, that's a very important one. He had two other early influential papers on nearest neighbor classification:

Thomas M. Cover. Rates of Convergence for Nearest Neighbor Procedures. Proceedings of The Hawaii International Conference on System Sciences, Honolulu, Hawaii, January 1968. Thomas M. Cover. Estimation by the Nearest Neighbor Rule. IEEE Transactions on Information Theory, IT-14(1):50--55, January 1968.

Even before Vapnik-Chervonenkis, he calculated the VC shatter coefficient for half spaces:

Thomas M. Cover. Capacity Problems for Linear Machines. Chapter in the book Pattern Recognition, Thompson Book Co., 1968. ed. by L. Kanal.

Then, of course, he was among the pioneers of online learning:



Thomas M. Cover. Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin. Stanford University Dept. of Statistics Technical Report No. 12, October 1974.

Robert M. Bell and Thomas M. Cover. Competitive Optimality of Logarithmic Investment. Mathematics of Operations Research, 5(2):161--166, May 1980.

Thomas M. Cover. Log Optimal Portfolios. Chapter in Gambling Research: Gambling and Risk Taking, Seventh International Conference, Vol 4: Quantitative Analysis and Gambling, ed. by W.E. Eadington, 1987, Reno, Nevada.

Paul H. Algoet and Thomas M. Cover. Asymptotic Optimality and Asymptotic Equipartition Properties of Log-Optimum Investment. The Annals of Probability,, 16(2): 876-898, 1988.

Robert Bell and Thomas M. Cover. Game-Theoretic Optimal Portfolios. Management Science, 34(6): 724-733, June 1988.

He was among the first to use Blackwell's approachability for online learning:

Thomas M. Cover and David H. Gluss. Empirical Bayes Stock Market Portfolios. Advances in Applied Mathematics, (7):170-181, 1986 This one was a big seminal paper for structural risk minimization: Andrew R. Barron and Thomas M. Cover. Minimum Complexity Density Estimation. IEEE Transactions on Information Theory, 37(4): 1034-1054, July 1991.

Avrim Blum says: I don't know if the following had a big influence on COLT but I remember Ron Rivest describing this result which totally blew my mind: COVER, THOMAS M (1973). On determining the irrationality of the mean of a random variable. Ann. Math. Statist. 1862-871. COVER & HIRSCHLER (1975). A finite memory test of the irrationality of the parameter of a coin. Annals of Statistics, 939-946

You are observing a sequence of flips of a coin of unknown bias p, and after each flip must predict if p is rational or irrational. Shows that with prob 1 you can do this making only a finite number of mistakes....

We Think Like Our Fields

Have lunch with economists and they'll talk about the decision making processes and equilibriums of everything from politics to sports. Computer scientists worry about the misuse of information. Systems people create policies that look like computer programs. Mathematicians internally create models of society and derive consequences from it. I find myself treating the world as one large computational process. Isn't it?

It's not just academics, I've seen the same kind of thinking from lawyers, doctors and business owners. In one sense this isn't a bad thing. It's hard to reason about the world and using our tools and talents to makes sense of it all helps us cope with society. We all have our own religion whether it be spiritual or scientific. 

The problem comes when we just hang with our own, in our social networks both in person and online. We start believing that everyone else thinks the same way we do. Then we have difficulty working with people outside our community and that just isolates us even more. 

Trick question or Stupid question?

April fool days Blogs or Columns may

present an open problem as closed,

present a closed problems as open,

make us wonder if it's a joke or not, (Lance STILL isn't telling!), or

make us question some well held beliefs.

This year I will take a different route- similar to what Lipton did here, which is NOT try to fool you, but present a post ABOUT tricky or foolish or odd things.

When is a trick question a stupid question? I give some examples and my opinions. But I want your opinions- are these questions (with the answers I give) TRICK QUESTIONS or STUPID QUESTIONS?

1. How many states are in the United States? Answers and Commentary
2. What is the least common Birthday in America? Answers and Commentary
3. What is the degree of (x-a)(x-b)(x-c)... (x-z)? Answers and Commentary
4. What US state has the eastern most point in America? Answers and Commentary
5. What is the least common first names for a U.S. President? (The answer is a tie.) Answers and Commentary
6. Which two numbers come at the end of this sequence?

   2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,y

   Answers and Commentary. See also this blog entry on the problem.
7. An expert on tracking animals notices one day that there are bear tracks and rabbit tracks converging on the same spot. He can estimate that they converged at 6:00PM with a margin of error of 17 seconds. Hence they must have been there at the same time. He also notices that from the spot they converged only rabbit tracks can be found. HOW CAN A RABBIT EAT A BEAR FOR DINNER? Answers and Commentary
8. There are 6 blue socks, 8 white socks, and 10 black socks in a drawer. How many do you need to take out of the drawer in order to get a pair. Answers and Commentary
9. What is the square root of nine? Give the answer as an anagram of the question. Answers and Commentary

The Value of an Academic Publication

Russell O'Connor's paper was accepted into last years ACM SIGPLAN Workshop on Generic Programming. Russell put the final version of his paper on the ArXiv under a public domain dedication. Russell couldn't transfer author's rights to the ACM since he gave them up. After much discussion the ACM decided not to publish the paper in the proceedings. The abstract in the proceedings states

We note that one of the papers presented in the workshop is not included in the proceedings. This paper, "Functor is to Lens as Applicative is to Biplate: Introducing Multiplate" by Russell O'Connor, is accessible as arXiv:1103.2841v2 [cs.PL].

Russell gives his account but he focuses on ArXiv instead of the public domain aspect. In the STOC CFP we encourage putting your submissions on ArXiv and similar sites. The issue that worried ACM was the loss of rights. ACM could have published the paper, it was in the public domain, but it wouldn't have control of that publication and didn't want to set precedent. Scott Delman of the ACM responded here.

An academic paper you write has little direct value to you (the paper itself not the Intellectual Property within). No one is likely to give you any money for that paper. But your paper does have financial value as part of a collection in a journal or conference proceedings. Commercial and non-profit publishers know how to collect on this value. You might complain that this puts your paper behind a firewall but all the major publishers in CS allow you to post earlier drafts on your homepage and archive sites. As long as you make that effort, people will have access to your papers.

It does take some money (or considerable person hours) to maintain even an electronic journal or conference proceedings. But publishers get more value than that. For the ACM, the DL revenue is a major source of funding for ACM activities and those of the SIGs.

Of course you should never trust the opinion of someone who has a financial interest in a position and as SIGACT chair, we certainly make use of the DL revenue. We are hoarding some in case the DL revenue shrinks in the future.

It seems a shame to leave the monetary value of our papers on the table but also that value shouldn't be exploited. Big discussions will continue on the publications issue, at ACM and other publishers and at all levels of the CS community. There will be a Dagstuhl workshop focused on this topic in the fall. Figuring out the right model for publications will not be an easy one.

My biggest fear is that lack of a plan will lead to a degradation in the quality of our publications and then everyone loses.

Sanjeev Arora wins ACM-Infosys Award

Sanjeev Arora will receive the 2011 ACM-Infosys Foundation Award, the highest honor ACM gives to a mid-career scientist.

Sanjeev Arora is one of the architects of the Probabilistically Checkable Proofs (PCP) theorem, which revolutionized our understanding of complexity and the approximability of NP-hard problems. He helped create new approximation algorithms for fundamental optimization problems such as the Sparsest Cuts problem and the Euclidean Travelling Salesman problem, and contributed to the development of semi-definite programming as a practical algorithmic tool. He has played a pivotal role in some of the deepest and most influential results in theoretical computer science, and continues to inspire colleagues and new generations of researchers.

Congratulations to Sanjeev!

In other news, the IEEE Computer Society W. Wallace McDowell Award is being awarded to Ron Fagin, and the US gives a big push for big data (CCC blog has details).

Another reminder for upcoming deadlines: STOC Posters (3/31), ACM Turing Student Travel (4/2), STOC Student Travel (4/4) and FOCS papers (4/4).

"Math was a mistake- I made it too hard"

(REMINDER- IF you are a STUDENT who wants to GOTO STOC 2012 but needs money to go then you should GOTO the STOC 2012 homepage and click on Travel Support. Deadline to apply: April 4.)

In the movie Oh God Book II God, played by George Burns, says

Math was a mistake, I made it too hard

Or at least I thought he said it. I have repeated this quote both in the blog and as a comment on Scott's blog. As I noted on my blog, if you Google

"Math was a mistake, I made it too hard"

all of the hits that you get lead back to me. This is still true. (Though it won't be after this post goes up.)

I thought it was a great quote so I am surprised it is not better known. FINALLY Oh God Part II came TV so I watched it just to see if what I've been quoting all these years is really in the movie. (Also, its a pretty good movie, for what it is.)

Alas, that is NOT the quote! What God really said was

"Mathematics, that was a mistake. I should have made the whole thing a little easier"

I think my version is better.

There are other misquoted quotes. My favorite: Stalin never said

The capitalists will sell us the rope with which we will hang them.

He did say:

The capitalists will furnish credits which will serve us for the support of the Communist Party in their countries and, by supplying us materials and technical equipment which we lack, will restore our military industry necessary for our future attacks against our supplier. To put it in other words, they will work on the preparations of their own suicide. (The Yale Book of Quotations (2006))

Both for George Burns and Stalin I am troubled- are we better off using the pithy version of the quotes, which DOES capture what they meant, or the original?

We have a similar issue when we teach- do we teach math the way it was invented or discovered (messy but motivated) or the way it is understood now (clean but unmotivated). Hopefully its not an either-or question and we can do some of both.

What is an Elegant Proof?

What is an elegant proof? I do not know and I doubt it can be well defined; however, we all know it when we see it. I welcome comments on the topic; however, I will give a very simple example for a contrast of elegant and non-elegant. All of the math discussed here informally is done formally here.

Consider the following theorem:

There is no 2-digits number that is the sum of the squares of its digits.

One crude measure of elegance is to minimize the number of numbers that you need to check directly are not the sum of the squares of their digits. With this in mind. With this in mind, here are several proof sketches.

1. One could proof this by enumerating all possible 2-digit numbers. If you wrote a program for this then you could use it on similar problems. Even so, I suspect most of us would call this proof NOT ELEGANT. This requires 89 CHECKS.
2. There is a proof that first easily eliminates 10, 20, 30, 40, 50, 60, 70, 80, 90 and then looks at every interval [11,19], [21,29], ..., [91,99]. More elegant than enumeration and certainly shorter. This required 8 CHECKS.
3. There is a proof that looks at the equation 10a + b = a² + b². We look at it mod 2, mod 4, and mod 10. This gives what I thought was the most elegant proof; however, after writing it down carefully it was about the same length as the interval proof. This required 2 CHECKS.

Consider the following theorem:

There is no x ≥ 2 that is the sum of the squares of its digits.

The cases of 2 ≤ x ≤ 9 and x ≥ 100 can be done with zero checks, so using the best proof of the last theorem, we can do this theorem with 2 checks.

Consider the following theorem.

The only 3-digits number that is the sum of the cubes of its digits is 153. (NOTE ADDED LATER: This is INCORRECT. A commenter pointed out that 370, 371, 407 also work. I will fix the proof and statement later and see if these are the only ones. Score a point for the `do it by a computer enumeration' argument!)

I have a proof of this which is... not quite elegant but not brute force. I get it down to only 21 CHECKS. If you have a better proof in terms of NUMBER OF CHECKS that is not contrived to reduce NUMBER OF CHECKS I would be very interested to see it. Of course, I cannot define contrived rigorously or elegantly.

David Waltz (1943-2012)

David Waltz, head of the Center for Computational Learning Systems at Columbia, passed away yesterday after a battle with a brain tumor at the age of 68.

David Waltz is best known for his research in artificial intelligence but I'll remember him most for his leadership of the NEC Research Institute when I was there. David fought hard and risked his career to protect basic research, particularly theory, at NEC. He would end up losing the presidency of NEC in this conflict. It is a great leader that is willing to risk all to support his people.

A Busy Time of The Year

It's spring break week at Northwestern so life is supposed to be quiet. No such luck.

Endre Szemerédi will receive the 2012 Abel Prize, perhaps the most prestigious annual award in mathematics. Tim Gowers has a nice summary of his work.

With this tweet the head of Yahoo Research officially leaves for Google.

Farewell @YahooLabs it was a fantastic ride. Hello @google
— prabhakar raghavan (@WittedNote) March 20, 2012

This likely marks the beginning of the end for what was a great corporate research environment.

FOCS submission deadline is April 4. There are some minor changes in the submission format from last year.

Registration for the ACM Turing Centenary Event is full but students can still attend through a limited number of ACM SIGACT Student Scholarships.


Registration for STOC is now live. The final program will be posted soon.

• Submit to STOC's second poster session. Deadline March 31.
• Student Travel grants are available Deadline April 4
• This STOC will have the inaugural Student Presentation Award

Even as I write this post, breaking news that U. Illinois president Michael Hogan resigned. Can't wait to see what Jeff has to say about this.

Heading South

Starting in July, I'll be chair of the School of Computer Science in the College of Computing at Georgia Tech. Annie Antón from NC State will chair the School of Interactive Computing. Here's the official announcement. I'm truly excited to be working with Annie, the Dean of Computing Zvi Galil and the incredible faculty there to move Georgia Tech forward.

I can anticipate many of your questions: How does moving from the land of Lincoln to the land of Lipton affect the blog? How do I get a job at Georgia Tech? Wait, does this mean there is a theory opening at Northwestern? Is this really the fourth job you've had since starting the blog ten years ago? All in due time.

Intel Science Talent Search

Last week I went to the Intel Science Talent Search Awards Ceremony in DC, probably the most prestigious math and science competition for American high school students.

I mentored one of the finalists, Adam Kalinich, of the Illinois Math and Science Academy. Adam studied poset games, where each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. The complexity of deciding who wins a poset game is wide open. Adam showed how to convert a game where one players wins to a game where the other wins, a surprisingly tricky task. His paper appeared in IPL (also on ArXiv).

Lots of math and computer science among the finalists and winners. The other Illinois finalist, Jordan Cutler, worked on practical implementations of quantum cryptography with Prem Kumar, another professor in my department. Jordan, who is a cousin of complexity theorist Steve Homer, came in 10th place.

Anirudh Prabhu had the coolest math result on perfect numbers. It's been conjectured that there are no odd perfect numbers. Anirudh showed a non-constant lower bound for odd perfect numbers (if they exist) as a function of the number of factors. Only constant lower bounds were known before. Anirudh came in 7th place.

David Ding got 4th place for his work on representation theory of Cherednik algebras. I don't know what those are either.

First place went to Nitin Tumma for work related to cancer.

The ceremony itself was a great scene. I'm a sucker for the pomp and circumstance. Walter Isaacson gave the keynote address and we all got autographed copies of his biography of Steve Jobs. Great fun was had by all.

I've seen the future of American science and it is awesome.

Judea Pearl wins Turing Award

(In this age of lightenting fast communication I suspect you all already know that Judea Pearl won the Turing Award. Even so, it is worth posting about.)

Judea Pearl has won the 2011 Turing award (given in 2012). (see here for the announcement). He is not a theorist; however, he did champion the use of probability and graph theory in AI.

Strong AI is the attempt to make computers match or exceed human intelligence. People in Strong AI might see how humans do things and try to get a program to mimic that. Putting aside philosophy (are we all just rather complicated DFA's?) the goal of Strong AI seems to just be hard to do even if it is possible (complexity issues?)

Weak AI has more modest goals (and a much shorter Wikipedia Page)- lets get a computer that can do a well defined task (e.g., Medical Diagnosis) well. They want to get things to work and may very well NOT take how humans do it as an inspiration. Do humans do the kinds of probabilistic calculations that Judea Pearl works with? I tend to doubt it.

Once Strong AI produces real results it is called Weak AI. Once Weak AI produces real world products its called something else (Robotics, Nat. Lang Proc, Vision, there are other examples).

I ask all of the following nonrhetorically. NONE of the questions are meant to question the award.

Did Judea Pearl work in Strong AI to Weak AI?

Was Judea Pearl one of the first people to incorporate serious AI on a more rigorous foundation?

Does AI use serious math? (I know that Control theory does, though is that AI?)

Did Judea Pearl (or his group) build software that is actually being used someplace?

What is the criteria for good work in AI?

Who might be the next AI Turing Award Winner?

How do legit fields of knowledge decide between competing theories? How does Astrology?

Euler was born April 15, 1707. Hence by the Western Astrology that we all ignore he is an Aries. However, I recently heard about another way (also worth ignoring) of doing the signs where he is a Pisces (see here). The other system has 13 signs. (There are some other systems, all worth ignoring, here.) For a serious article about what astrology really claims to say and why its worth ignoring see here.

What does a field of study do if there are several competing theories?

1. The Natural Sciences: I would like to think that the truth wins out... eventually. There may be struggles and politics and whatnot but in the very end experiments are performed and the more predictive theory wins out (I know its more complicated then that.) There are some fields where it is hard to do experiments (e.g., String Theory). Others where the theory gives great explanatory power but might be hard to do direct experiments (Evolution). Those cases may be hard to deal with, but they manage. Does String Theory have great explanatory power?
2. Mathematics: Here the question is not WHAT IS TRUE since we can use proofs (Again, I know its more complicated than that) but WHAT IS WORTH STUDYING. Applied Math may still use the real world for a litmus test to some extend. More abstract kinds of math may be harder to test by looking at the real world. Do Large Cardinals exist? Is the Axiom of Determinacy true? Some people claim that they look for internal consistency and also intuitions. And some people live-and-let-live (you want to use AC, fine, I won't) (Again, I know its more complicated than that.)
3. Astrology : What does a field do when its predictions are either vague or no better than chance? If there was a well designed experiment to test which theory has more predicative value then I suspect they would all be found wanting. (Then again, I'm a Sagittarius and we are known to be skeptical.) So what other criteria could they use? Internal Consistency and Intuition? Whichever one makes people feel better (some astrologers might claim that they are really psychologists, telling people what they want to hear to sooth them). Whichever sells more books? Makes more money? Is there some sort of aesthetics involved? I ask this nonrhetorically. (An idea for a scam: The old astrology doesn't work because they don't take into account relativistic effects on the planets. Use my Relativistic Astrology! For people who like what they believe in to have some buzz words from science thrown in!)

This does raise the general question- if there are competing theories in a field where its hard or impossible to do experiments, what does a field do? Whoever yells loudest wins?

March Madness

Once again, America's favorite binary tree, the NCAA Men's National Championship Bracket. The tree seems to get more unbalanced every year. There are four regions, the East has the traditional 16 teams, the West and South have 18 teams each and the Midwest has 19 teams for a total of 68 teams. Single elimination starts tomorrow.

Many Americans participate in office pools where they fill out the bracket to predict which team wins each game. There's lots of math one can use for your bracket. But here is my advice: Pick the higher seeded teams to beat the lower seeded teams. Every time. There will be upsets but you can't predict where they will be so you have the best chances predicting none of them.

The most likely seeds to make the final four are two number 1's, a number 2 and a number 3, 3 times in the last 27 years. So why follow my advice which predicts four number 1's. Because there are 12 ways to get 11 2 3 and only one way to get 1 1 1 1 and you have to pick a specific combination when you fill out your bracket. The four first seeds all went to the final four only once in the last 27 years but given there's only one such combination that makes it more likely than any other possibility. 

May the madness begin.

Scott wins the Waterman

The NSF's most prestigious prize, the Alan T. Waterman award, recognizes an outstanding young scientist (35 or under) in any field of science or engineering. Breaking with tradition this year the NSF picked not one but two winners, computer scientists Scott Aaronson (MIT) and Robert Wood (Harvard).

Most of you readers know Scott well. He's already an established leader in quantum computing and computational complexity and has his own awesome blog. Not sure why NSF decided to use a photo of Scott proving Karp-Lipton wearing a skirt. The CCC blog post points to Scott's TedxCaltech talk. I'll just link to the podcast I had with Scott back in 2005.

Computational complexity has won two Watermans in the last three years as Subhash Khot received the award in 2010.

Robert Wood is the principal investigator of the RoboBees project, which is pretty much as the title suggests, insect-inspired robots. Sweet revenge for being called the number one example of government waste by Sean Hannity.

When a+b is harder than b+a

Is 1+4 a harder calculation than 4+1? It may be if you are 2+3 years old. I asked my 7-2 year old great niece Noelle the following sequence of questions. I include how long it took her to answer.

Bill: How old are you?

Noelle: (2 seconds) 5

Bill: What is 3+2

Noelle: (3 seconds) 5

Bill: What is 2+3

Noelle: (2 seconds) 5

Bill: What is 4+1

Noelle: (1 seconds) 5

Bill: What is 1+4

Noelle: (8 seconds) 5

Bill: What is 7 take away 2

Noelle: (4 seconds) 5

Bill: What is the least d such that there is general dth-degree equation.

Noelle: (11 years) 5

Bill: What is the least k such that the kth Ramsey Number is not known

Noelle: (21 years) 5

The most interesting of these to me was that 1+4 took much longer than 4+1. Why is this? To do 1+4 she starts at 1 and adds 1 to it four times so its 1 + 1+ 1+ 1+ 1. To do 4+1 she starts with 4 and adds 1 once, 4+1. More generally, if we don't use the addition is commutative and we view +1 our basic operation than the complexity of a+b is b.

It is important to realize that concepts such as commutativity of addition which are now obvious to us as adults, there was a time when it was not obvious. Or perhaps not obviously useful for calculations.

Could a model of children's addition be defined and studied? Would this be a Math Project, a Math Ed Project, or a Child-Development Project? Has it already been done? I suspect that how children learn things has been studying extensively, but that well defined questions of complexity-of-children's-addition has not. My ONE data point suggests that the complexity of a+b is b, but to really study this you would of course need more samples. SO, if any of you relatives that are 5 or under (but can talk), and try this out, let me know what you find.