People solve math problems for the prize money! NOT!

Why do people or organizations offer Prize Money for mathematics?

1. Paul Erdos: He offered money to solve problems that he found interesting. I assume he wanted them solved but he also wanted to encourage a line of research beyond the problem. He had a (well deserved) reputation as a brilliant mathematician, so if he couldn't solve a problem it was hard. People would somtimes not cash the check and frame it. I've heard that with color copiers people now copy it, frame the copy, and cash the check. Did he insist that it appear in a journal or just need to be convinced? I don't know but I would think just need to be convinced.
2. Bill Gasarch: He offered $289 dollars for one problem, which, as you know, was recently solved by Steinbach and Posthoff (see here). While Gasarch has nowhere near the reputation of Erdos and his problem was not a deep math problem, this problem caught on as a matter of luck and timing. The blog helped, and Brian Hayes picking up on it helped. Gasarch wanted to get this problem solved, but did not quite know if it would inspire a line of research. It did (according to the solvers) present a problem just on the edge of what is possible to solve of this type. Gasarch used paypal. Hence, alas, Steinbach and Postoff won't be able to frame a check or its copy.
3. Scott Aaronson: His 100,000 offer (see here) for ...demonstration, convincing to me, that scalable quantum computing is impossible in the physical world This is different than most prize offers in seveal ways: (1) He gets to decide, not a ``refereed journal''. (SIDE NOTE-here is an idea: a prize that pays out only if the article appears in a non-elsevier journal.) (2) He does not expect to pay out (but he happily will if someone really convinces him). I believe him on this, though 100,000 is a lot of money. He wants to inspire people to think about these questions. The only thing analagous I can think of is prizes for REAL parapsychology- they don't expect to pay out but would be happy to since the world is more interesting if parapsychology is true.
4. Millienium prizes: I believe these one million dollar prizes are the most ever offered for solving particular math problems by an order of magnitude (if that is not correct, please leave a polite comment correcting me). Clearly the Clay Instuite wants to encourage research in these areas. Why so much money? I assume to REALLY put these problems on the map. There is no mathematician of the stature of Hilbert nowadays who could state problems of importance in a way people would listen. Smale tried (see here) but those problems never got the status of either Hilbert's problems or the Millenium problems.
5. Godel Prize: Best paper in theory published in the last 14 years (used to be 7). I wonder- if someone posted a solution to P vs NP on arXiv and it was correct, would they really not get the Godel prize? I suppose not. A bit awkward in that if your publish in a period of time when many good papers come out you could be out of luck. Why did they extend the window from 7 years to 14 years? Speculation: people are getting worse at getting papers out into journals so they had to extend it. Enablers? Given once a year.
6. Turing Award: I am not quite sure if this is for one paper, a body of work around one idea, or a career. It can go to people who never proved a theorem since its open to all computer scientists. The prize money has gone from $2000 to $250,000. Given once a year.
7. Fields Medal: Given for a body of work. About $15,000. High Prestige, low dollars. How come the Turing Award was able to increase its money value but the Fields medal was not? I honestly want to know. Given once every 4 years to a set (group? locus?) of people.
8. King Faisal prize: I blogged about this here so I'll be brief: High dollars ($400,000), but low prestige. I assume the origin was to try to give glory and prestige to Saudi Arabia who gives out the prize. I don't think it worked. Aside from its origins it also has the problem of being unfocused in that they have awards for Sciene (which is sometimes math) and also for Muslim scholarship, and other areas.
9. Here is a list of other prize. Some thoughts
   1. Some are for solving a particular problem, some are for a body of work in a particular area, some are for a body of work and the area can be anything within mathematics.
   2. Some are restricted to a subset of people, some are not. Thats a tautology!
   3. People do not solve problems for the money. Most of the prizes are too small for that and those that are large are for really hard problems.
   4. There are many of them, more than I thought. I still doubt I'll win one. The closest I ever came was being linked to on the Wikipedia page on the Godel Prize (see this Blog Entry about why that happened.)

Sloans and More

The Alfred P. Sloan Research Fellows were announced today including Northwestern's own Nicole Immorlica. Other winners in theoretical computer science include Xi Chen, Nate Foster and Prasad Raghavendra. A shout out to TTIC who have their second Sloan Fellow in Jinbo Xu.

Computer science did well in the president's budget for FY 2013. CISE head Farnam Jahanian gives the details. Of course now the budget has to get through congress.

Tomorrow there will be a celebration of twenty years of the NITRD (Networking and Information Technologies Research and Development), an interagency program that has heavily supported CS research over the past two decades. Quite an impressive list of speakers. There will be a live webcast of the event.

FOCS call for papers is out. Submission deadline is April 4.

Barney the Evil Dinosaur

This is an old story from before I had a blog, but one of my favorite on when technology goes bad.

In the late 90's, the undergraduate CS coordinator at the time, Don Crabb, also wrote a column on technology for the Chicago Sun-Times and would get tons of tech stuff to review. One of these items was a robotic Barney the Dinosaur that interacted with the Barney and Friends show on PBS. I took Barney home and tried him out with my then 3-year old daughter Annie.

He worked as advertised, singing along with the characters on TV. But at one point Annie said "Let's read a book Barney". Barney replied "Let's watch TV". Annie said "OK". Definitely sending the wrong message here.

Later Annie was playing with Barney in the kitchen. Annie, who was toilet training, said to Barney "I have to go wee-wee". Barney said "Let's play a game". Annie said "OK". Soon I had a mess to clean up.

That was the end of Barney.

STOC 2012 accepts are posted

STOC 2012 paper accepts are posted here. Travel support for grad students (which I am involved with) is posted here. On a quick glance:

1. I tried counting the paper for how many were in which categories. I got dizzy so I stopped. Also, for some its hard to tell the area just from the title. There DO appear to be many papers on complexity.
2. I hope that when the papers are finished there are pointers to all of them on the website.
3. There will be four workshops (see here) Under Tutorials it says TBA, so there may be some of them. What is the difference between a workshop and a Tutorial? I ask nonrhetorically.
4. When I goto an MAA or AMS conference there are (1) invited papers, (2) contributed papers, (3) Math Jeopardy game, (4) demos, (5) other things. When I goto STOC or FOCS or CCC or just about any theory conference its (1) submitted papers that got accepted. There MIGHT be a rump sessions (CCC, Crypto does this) a workshop or tutorial (STOC, FOCS does this- anyone else?) an invited talk (FCRC has these, Sometimes others do) a poster session (FCRC has had these. Have others?) My objection here is NOT that STOC has the submitted paper format and that STOC and FOCS are other conferences are too highly valued. (That is another debate which we've had before.) My objection is that all of the theory conferences only have VERY FEW kinds of activity- talks on papers that were accepted. I would like to see more VARIETY in activities.
5. The word Quantum only appeared in two titles. Are there other Quantum papers (I would guess yes).

The 17x17 problem SOLVED! (also 18x18)

THE 17x17 PROBLEM HAS BEEN SOLVED!!!!!

On Nov 30, 2009 I posted here the following challenge:

If someone emails me a 4-coloring of 17x17 with no monochromatic rectangles then I will give you $289.00

Bernd Steinbach (Institute of Computer Science, Freiberg University of Mining and Technology, Freiberg (Saxony), Germany) and Christian Posthoff (retired from Department of Computing and Information Technology, The University of the West Indies, Trinidad and Tobago, but now in Germany) have found a 4-coloring of 17x17 without monochromatic rectangles!! The coloring is here. I have verified it (actually I asked Daniel Apon and Jim Purtilo to separately verify it, and they have. Also, Semmy Purewal and Brian Hayes did later.) The methods Steinbach and Posthoff used to obtain the coloring will appear in their paper

Most Complex Four-Colored Rectangle-free Grids - Solution of an Open Multiple-Valued Problem (ISMVL 2012. ISMVL stands for International Symposia on Multiple-Valued Logic). They will present this paper on May 14, 2012 during session B1 of ISMVL in Victoria, Canada.)

Once the paper appears there will be a post (with their help, perhaps guest posted by them) on the techniques they used.

Some thoughts:

1. Some very serious people had worked very hard on this. I actually began thinking that 17x17 is NOT 4-colorable.
2. CONGRATULATIONS to Bernd Steinbach and Christian Posthoff!
3. They also found a 4-coloring of 18x18.
4. The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!
5. If you are going to ISMVL 2012 then find Bernd and Christian and say hello. More important, talk to them about there work. (I won't be there alas.)
6. The reason I thought that 17x17 was 4-colorable is that there is a rectangle free subset of size 74, so I assumed that one of the colors would appear 74 times. WRONG- The max number of times a color appears is 73.
7. I thought that each color would appear 4 or 5 times in each row and column. WRONG- some appear 3 times in a row or column.
8. I am DELIGHTED to pay out the $289.00.
9. I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem.
10. How did they do it? I do not know, but I am looking forward to reading their paper in May when it is available and blogging about it.

Competition

A few people have asked me my opinions on Oded Goldreich's essay On Struggle and Competition in Scientific Fields. I read through Oded's essay I expected to highly disagree with Oded, after all he attacks competition, which is just un-American, and he lays some blame on a small number of scientists "especially those holding administrative positions in the field" which as SIGACT chair puts me in that group.

But as I read the essay, I find myself agreeing with much of what he says. Our conferences have become too much more like competitions rather than focusing on distributing knowledge or bringing the community together. I also agree with many of his suggestions including having conference with more plenary talks, that program committees should create a "program" more than just choosing best papers and that hiring/promotion committees should focus more on the research itself rather than the decisions of program committees, awards committees and grant committees.

There is an faulty underlying assumption in Oded's essay that competition within theoretical computer science is a zero-sum game. Theoretical computer science competes within computer science for faculty slots and grant money. Computer science competes with other sciences and science competes with other needs.

SIGACT is not in the business of choosing winners and losers within the community but rather to promote the field to help increase the number of jobs and grants available to theoretical computer science. As I mentioned last week, awards are an important mechanism that lets us highlight the important research in theory.

Competition for grants, jobs, awards and just attention of other computer scientists helps make us all better allowing us to push for more resources for theory. It would be nice to say that we should just all do good self-motivated research, but the reality is we need those resources if we want theoretical computer science to continue to thrive.

Why do we have awards?

You have a month to get in your nominations for the Donald E. Knuth Prize and the SIGACT Distinguished Service Award.

Why do we have these awards and others like the Gödel Prize, The Turing Award, conference best paper awards, ACM Fellows, Nobel prizes and so much more. Are we just creating CV stuffers? Are we giving departments another measure to rank people? Are we trying to encourage good research through competitive awards? Does anyone have the conscious thought, "I wouldn't normally work on this problem but it could win me the Turing award so I'll do it"?

None of the above. We have awards for the publicity. We want to tell the world about the great researchers and work that they produce. A major award rises above the clutter and let's us say "Les Valiant must be a great computer scientist, he won the last Turing Award" or " Håstad's optimal approximation bounds are a great work in theoretical computer science as you can see from the Gödel Prize." Not a surprise that almost every award comes with a press release.

Are all awards fairly given? Of course not, prize committees are full of humans often comparing apples and oranges. But that's not the point. Awards let us celebrate what's great in computer science with ourselves and with the world.

Dusting off my bookshelf I find a book on FORTRAN

The following quote is from the back of a book that I dusted off and took off of my shelf recently:

FORTRAN is one of the oldest high-level languages and remains the premier language for writing code for science and engineering applications. (NOTE- The back of the book uses Fortran but the spell checker I am using insists on FORTRAN. As a fan of capitol letters, I don't mind going along.)

Was this book written in

1. The 1960's
2. the 1970's
3. the 1980's
4. the 1990's
5. the 2000's (meaning 2000-2009)
6. the 2010's (meaning 2010-2012)

Some questions and thoughts about FORTRAN:

1. How much is FORTRAN used? Perhaps more than you might think: Its in packages that have been running smoothly and quickly for a long time. It may not be worth it to swap it out for C or C++ or something else. However, it may be hard to modify.
2. How much new code in FORTRAN is being written? I suspect not much. UMCP does not have a course in it. Does your school?
3. Since people are not learning FORTRAN we will we become like one of those Science Fiction Aliens who says: Our ancestors left us these machines,but over time we only know how to operate them, not how to fix them or build new ones.

So, when was the book written?

The book is Modern Fortran by Clerman and Spector. The book came out in 2012 (I really need to dust my shelves). I doubt that FORTRAN is the premier languages for writing code in science and engineering. But how far off the mark is this? As always I ask non-rhetorically.

A result of Specker in Recursive Combinatorics

Ernst Specker passed away in December. He has 91. He was not the oldest living mathematician. That title likely belongs to Sergey Nikolsky. A former student of Specker's, Martin Furer, posted about his life and his math on this blog here.

In this post I discuss a results of Specker that is not his most famous (that seems to be the Kochen-Specker theorem) but instead a result that I actually know. Hope you like it.

Background: Ramsey's theorem states that if COL is a 2-coloring of pairs of naturals then there exists an infinite homogenous set H (so every pair from H has the same color). The standard proof is non constructive.

More background: What if you were GIVEN a Turing Machine for a 2-coloring. Could you GIVE ME BACK a Turing machine for a homogenous set? The standard proof does not give this to you, so we are really asking if there is a more constructive proof. So, what is known?

Specker showed that there is a computable 2-coloring of pairs of naturals so that there is NO computable Homogenous set. Here is the proof in brief:

1. Let A be a bi-immune set (no subset of A or its complement is decidable) that is decidable with oracle HALT. You can easily construct such by an initial segment argument.
2. By the Shoenfield limit lemma there exists computable f(x,s) such that A(x) = limit_{s→ ∞} f(x,s). (Easy proof of the direction we need: if A is computable in HALT via oracle Turing machine M let f(x,s) be the result of running M for s steps and using as oracle the first s elements of HALT in some enumeration.)
3. Let COL(x,y) = f(x,y), for x< y. (NOTE- This is a correction, I earlier just had COL(x,y)=f(x,y).)
4. Assume, by way of contradiction, that there is an infinite homogenous set
   
   x₁ < x₂ < x₃ < x₄ < x₅ ...
   
   For all L we have f(x_L,x_L+1)= f(x_L,x_L+2) = f(x_L,x_L+3) = f(x_L,x_L+4) = ... (NOTE- I corrected this- I originally had x_1, x_2, x_3, x_4 where I now have x_{L+1}, x_{L+2}, ..)
   
   Since all of these values equal they also equal limit_{→ ∞}f(x_L,s) and hence equals A(x_L). Hence either ALL of the x's are IN A or all of the x's are NOT in A. Hence an infinite homogenous set yields an infinite subset of either A or the complement of A, which contradicts that A is bi-immune.

More has been proven since then:

1. Jockusch showed that (a) there is a 2-coloring of pairs so that no homogenous set is Sigma₂, and (b) every 2-coloring has a Pi₂ set.
2. More is known- see the paper by Cholak, Jockusch, Slaman On the strength of Ramsey's theorem for pairs

Specker's result is probability the first theorem in infinite combinatorics to be proven to be non-constructive.

Guest post on ITCS by Chazelle

(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012. Applications are due on: Feb 29, 2012. Go here for all the relevant information. Hoping to see you in June. From: Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin.)

(Guest Post by Bernard Chazelle) Why ITCS?

Thanks to Lance and Bill for their kind hospitality. I am delighted to be here. With the third edition of ITCS (formerly ICS) behind us, I thought it would be good to share a few personal, biased thoughts on the subject -- "personal" because I do not claim to speak for the Steering Committee; "biased" because I happen to chair that august body.

First, let me reach for my big bucket of gratitude. Shafi Goldwasser and Silvio Micali did an amazing job as PC & local chairs and I cannot thank them enough. A big shout-out to both. Toda Raba to Yael Kalai, too, for her great help, and to Omer Reingold, Nir Shavit, and their fellow actors for a fabulous "playback" show. If you missed it, fret not. If future organizing committees have any sense, the Nir-Omer show will soon come to a conference near you.

This year's ITCS had about 100 submissions, roughly a 20% growth from previous years, and 118 registrants. Talk attendance never seemed to dip below 90, a heart-warming figure that would be the envy of many conferences. In Shafi's and Silvio's deft hands, innovation came out swinging in all sorts of endearingly creative ways, from session chairs giving annotated previews of the talks to postdocs and graduating students making 5-min pitches to introduce themselves and their research. Brilliant! After watching the new generation of theorists in action, I can tell you that the future of theoretical computer science looks very bright, indeed!



And the future of ITCS, you'll ask, how bright is that? When I chaired the PC last year, a reviewer's comment struck a chord: "This submission would be good for STOC but might not be innovative enough for ICS." Now, that's the spirit! Of course, plenty of ITCS papers would fit in nicely at STOCS/FOCS. (Apparently, more than a few tried to fit in.) That said, it would take an advanced case of color blindness to miss the contrasting hues between ITCS and the rest. All PC members were instructed to add an innovation axis to their evaluation space, and, by golly, they did! (And when I use the word "golly," you know I mean business.)

STOC/FOCS has been accused of all sorts of dastardly deeds unmentionable on a family blog -- from accepting too few papers to boosting trends to rewarding technical wizardry. No less. STOC and FOCS might be four-letter words to some, but to me they're venerable legacy institutions that serve worthy professional functions, such as allowing junior researchers to trade these four-letter words for Theory Club membership cards. Nothing to sneer at. Over at Michael Mitzenmacher's corner, here, Umesh Vazirani bravely suggested merging STOC and FOCS into one mega-conference --- SFOCS, I guess. Much as I love the idea, beginning with the soothing effect of pronouncing the word SFOCS out loud, I didn't come here for a food fight, so I'll fall back on old New Jersey wisdom and say we cross that landfill when we come to it. Yet definitely something to mull over.

ITCS provides a venue for quality outside-the-box thinking. Not without reason, a few have wondered whether the best place outside the box is inside a new conference. On the plus side, conferences provide ideal platforms to publicize new work and, for younger scholars, increase the visibility of their research. With its particular focus on the uncharted, ITCS offers a welcome new outlet for a glut of quality papers. A conference is a big heads-up, a "breaking news" banner flashing on the Theory Channel. It's also a chance to initiate lasting collaborations and meet extraordinary people in pursuit of extraordinary ideas. It's fun.The downside is that a human being can attend only so many conferences before "their budget glares red and their head bursts in air" (as they say before kick-off at the Super Bowl).

This dichotomy, however, isn't quite right. It ignores the tangled web the online revolution has woven into our lives. Whereas in the past I'd have to go to a conference to hear a new result, this is no longer so. The PDF will come to me. It's a given that attendees at many talks will already know the results, perhaps even the proofs. This has diminished the relative importance of attending a conference while at the same time increasing its reach, and hence its influence. Don't get me wrong. I am not saying ITCS is so cool you don't even have to go. I am saying that, in the age of instant downloads, missing this month's Jay-Z & Kanye West "UGC" gig at the Garden ain't gonna be the heartbreak it would have been in the days of old. So, while I recognize that the burden of extra travel is a drawback and the timing always an issue, our wired world alleviates these concerns somewhat. And if you find this argument too subtle for its own good, well, remember, there's always the Umesh option.

Another worry heard on Theory Street is fragmentation. I don't get that. The sociological makeup of all these conferences is pretty much the same, anyway, so the risk of fragmentation is about as high as that of Dr. Jekyll and Mr. Hyde parting ways -- OK, make that Superman and Clark Kent if you prefer. In fact, this has it exactly backwards. Theory has yet to penetrate many geographical markets. Eurotheory shares a name with our kind, and little else. With Asia a promising growth area for our field, it is of more than symbolic value that ITCS was born in China. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc). Maybe ITCS can be the exception. At any rate, to expand both the intellectual footprint and the geographical reach of Theory is a central goal of this conference.

To close on a personal note, let me get my crystal ball out of its dusty case and tell you what I see. As the new sciences of the 21st century further embrace their algorithmic nature, I see ITCS getting enriched with a growing flow of conceptual imports from physics, biology, economics, etc (and vice-versa). While the letter T was added to ICS for mundane reasons -- an ACM conference had a previous claim on the acronym -- I hope ITCS remains unabashedly theoretical. Yes, you heard right. And as you watch me adroitly duck the tomatoes sure to be hurled my way for this impolitic stand, you might even spot a contradiction or two. I mean, how can computing theory reach out to the sciences without losing its theoretical core? Well, well... Leaving aside the fact that math developed with precisely that sort of outreach, the answer is easy. What the "new" sciences (bio, neuro, socio, and all that) lack more than anything is a conceptual framework. Theoretical computer science can do for them what mathematics did for physics. Why? Because algorithms are the differential equations of the 21st c. They are the language of modern science. That's why. At this point, you expect me to clear my throat and indulge in a tasteful round of name dropping: "Moreover, as Newton and Einstein used to say, blah blah..." (I got that from my physicist friends. Works every time.)



But not today. Truth is, delusion won't help our cause one bit. Neither will diffidence or skittishness, however. These are heady times for computing theory, my friends. Hand wringing over fine tactical points should not distract us from our common goal, which is to allow Theory to expand and flourish, to unite and conquer. ITCS aims to do just that. It is an exciting experiment worthy of your support.

Thanks for your attention and, in a nod to ITCS' roots, a happy Year of the Dragon to all!

Bernard Chazelle

Ernst Specker (1920-2011)

Martin Fürer remembers his former advisor. 

While traveling, I received the unexpected sad news that Ernst Specker passed away on December 10, 2011. He was born in Zürich in 1920. After receiving his doctoral degree at ETH Zürich in 1949, he spent a year at the Institute for Advanced Study in Princeton. Then he returned to ETH in 1950 and stayed there with the exception of two visiting appointments at Cornell University.

Ernst Specker was teaching Linear Algebra when I started my studies at ETH Zürich in 1967. His teaching style was different from the typical polished and streamlined presentations of that time. He was looking for interaction, and did not hesitate to interrupt a proof to insert an example when he sensed that the audience was not following.

Outside the classroom, it was a turbulent time. The youth movement started to question many long established rules of society. For a long time, it seems that the majority of people, without ever thinking about it, had accepted the claim that the US with its war in Vietnam was defending western values. Quite suddenly, this consensus was widely questioned.

ETH had its own little problem. A new law governing the ETH (the only federal university in Switzerland) had just been adopted by the parliament. Many students took issue with the idea that the main goal of ETH was not to satisfy a general human right for education, but to prepare the students to serve the interests of business and industries.

Ernst Specker, who always liked discussions, never accepted anything based on authority without asking some critical questions, had quickly established a relationship with the young students at this time of evolving political turmoil.

Here are two examples, typical for Ernst. The mathematics and physics students of each semester had an open discussion about the ETH law. One professors came to our group to tell us, we should not complain, its our fault, we should have had this discussion a year ago, when it was the proper time to voice any opposition. He was not happy, when Ernst disagreed, noticing that this group of students has only been here for half a year.

A more important move was Ernst Specker's engagement for the Manifesto of Zürich, a public declaration against police brutality after some excesses when the "establishment" was shocked and fearful of the demonstrations in downtown Zürich.

During our studies, we all had to give talks in four seminars in different areas of mathematics. This rule was widely followed with one exception. A large group of students participated in the logic seminar, and they came back ever since (naturally in addition to the other seminars). Every semester, there was a different theme. My first subject was the solution of Hilbert's tenth problem, presented with all background information and details. The seminar was conducted with Hans Läuchli. Paul Bernays, who had started the seminar when he came from Göttingen before the second world war, was still a regular participant. He often followed the talks reading the blackboard with a two minute delay.

Ernst conducted the seminar still long after his retirement, because unfortunately ETH no longer had a position for mathematical logic. I participated in Ernst’s last logic seminar during my sabbatical in 2002. We ended the semester with a talk of Ernst that was intended for a general mathematical audience. I reserved the beautiful and rather spacious Aula of the ETH for this purpose. Luckily, we could still switch to the Auditorium Maximum, in the last minute, when we saw the people  arriving.

Scientifically, Ernst Specker has worked in many areas as illustrated in by the Selecta volume published by Birkhäuser on the occasion of his 70th birthday.  In his dissertation with Heinz Hopf, Ernst worked on cohomology groups. Then he moved on to investigate constructively in analysis, and the foundation of set theory, in particular Quine's new foundations. He also solved one of the early Erdős problems. Ernst’s most famous results are the works with Simon Kochen on the foundations of quantum mechanics, proving that certain hidden variable theories are not possible, and thus colliding with the assumptions made in the famous Einstein-Podolsky-Rosen paper. The results of Kochen and Specker are still discussed today in the physics literature. Early on and in his additional weekly seminar with Volker Strassen starting in the early seventies, he reached out to complexity theory.

Ernst Specker will always be remembered for his teaching and his scientific work, but most of all for his friendship, his openness and his engaging discussions.

Martin Fürer
Pennsylvania State University

What should we do?

Time for a post by tweet request.

Is a wave of action against big publishers' practices brewing?gowers.wordpress.com/2012/01/21/els…thecostofknowledge.com Should CS do more? @fortnow
— Tugkan Batu (@tugkanbatu) January 22, 2012

Quite a lot on the Internets on Tim Gowers' promise not to work with Elsevier anymore. I'm not as anti-Elsevier as Gowers or many of my readers but I understand the frustrations.

It's easy to make a promise not to publish, edit or referee papers, especially when you don't need to improve your academic reputation. Still a mathematician of his magnitude really puts a spotlight on that publisher.

Because of the Elsevier stigma we've had for several years, all the theoretical CS journals of Elsevier are not nearly as strong as they have been in the past. So you don't accomplish much more just by boycotting Elsevier.

Making a difference means what you do, not what you don't do. Be sure and support journals that are worthy of support by submitting and refereeing papers and serving on editorial boards. The best attack on publishers that you don't like is to have several strong alternatives. The best way to make them strong is by having your support.

No journals is completely free of cost, they require money or time. Open access journals without page charges generally have no revenue stream and require effort to make to publish the journal. For these journals you can volunteer your time as well as submitting, refereeing and editing.

Remember it's easy to complain and say what you won't do but it is what you do do that makes the difference.

Teaching an Honors Section of Discrete Mathematics

A few years ago I was assigned to teach the HONORS section of Discrete Math (a course for sophomores who have had a year of programming and a year a calculus). They told me it was up to me to figure out what to do to make it an honors course. (My section had 30 students, the non-Honors has about 60.) There were several options:

1. This could be taught separate from the non-honors course. Diff homework, diff exams.
   PRO: the homework and exams can be more interesting since you do not have to worry about how they are for the non-honors student.
   1. CON: If a student would have gotten (say) an A in the non-honors course, but gets a B in the honors section, that is not good. OR the teacher could grade inflate so that the students who got a B in the reg section gets an A in the honors section.
2. You could give the same exams and homework to the honors students but REQUIRE them to do more work- extra problems on the homework, extra problems on the Exams.
   1. PRO: They will get to do more fun problems.
   2. CON: They are being penalized for taking an honors course.
3. Same Exams and homework as the regular class. The regular class meets Tu-Th for 75 minutes. The Honors class meets MWF for 50 minutes each. What the Regular class does on Tu-Th, the honors class does on MW. On FRIDAY the honors class has an HONORS DAY- they work in groups of 3 or 4 on problems of more interest than usual. (example: For Logic devise a way to do do AND, OR, and NOT if the variables take on values BETWEEN 0 and 1 (including 0 and 1)). There is a LIGHT homework on this work just to keep them honest. But its not graded seriously.
   1. PRO: They get to learn more stuff in a fun way.
   2. CON: More work for the professor to make up these kinds of problems. (To brag- this is the sort of thing I am good at so not a problem for me.)

I did the last one and I think it worked, for some definition of worked. That is, the students liked it and found it interesting, but its hard to compare it to other ways of doing it. (Doing real studies that tell you things in the field of Education is hard.)

How have you, or would you, run an honors course in discrete math? How about for a programming course?

How important are the Fib numbers in math? in Nature? In History of Math books?

The following quotes is from In the book Algebra in Ancient and Modern Times by V.S. Varadarajan.

Fibonacci numbers thus grow very fast with N, indeed in geometric progression. This is often called exponential growth. They remained as curiosities till in the 1960's they were found to be crucial in certain studies in mathematical logic.

I suspected they were refering to its use in Hilbert's tenth problem even though that was really 1970 (a quibble) and I would hardly call it crucial (a more substantial objection). In fact Fib Numbers are not even needed in the end. I asked Chris Lastowksi who is a Model Theorist at UMCP and he told me the folowing:

Yes. Matijasec showed that the Fibonacci sequence was diophantine, and this sufficed to solve Hilbert's tenth problem (actually to show it could not be solved), by earlier work of Davis, J. Robinson and Putnam. However, Davis almost immediately showed that the exponential function is diophantine, which yields the solution to H-10 more easily, so I would hardly call that a deep connection.

V.S. Varadarajan wanted to make the Fib numbers interesting and important. The attempt was not quite right.

1. How bad is it for a history-of-math book to exaggerate how important some concept is?
2. How important are the Fib Numbers? Do they come up in Mathematics?
3. Could V.S. Varadarajan have picked a better example of their use in mathematics?
4. It has been said that the Fib Numbers come up in Nature. According to Fib Flim Flam most of the statements made about Fib numbers and nature are suspect.

The Information Flood

Twitter, Facebook, Google+. Information now comes to us as a faucet. If you don't drink it all it disappears forever. Try to find status updates and tweets from even a few days ago. Many of you wouldn't have seen this blog post if you didn't catch it on Twitter or Google+.

I try to keep my faucet turned relatively low. I still like RSS feeds like Google Reader. Stuff stays until you discard it. I try not to have too many Twitter followers or Facebook friends.

But the trend is for people, especially the younger generations, to subscribe to whatever fills their fancy. They get a continual stream of information and ignore what they don't see. So Google and Facebook develop algorithms based heavily on what the crowds and your friends are looking at, to determine the order of what you see. Twitter will surely have to follow. Google even tries to decide which of my emails are important.

As goes the Internet goes so does academic knowledge. How do we cut through the research clutter? Will we have algorithms and the crowds tell us which research papers to look at? That used to be the job of journal editors, conference program committees and my grad students.

Being Random and Trivial in Dagstuhl

This week I'm at the Computability, Complexity and Randomness workshop at Dagstuhl in Germany. This meeting brings together two groups, complexity theorists and computability theorists, who share a common love of Kolmogorov complexity.

From the logicians I learned about K-trivial sets. Let K(x) be the prefix-free Kolmogorov complexity of x, i.e., the size of the smallest program that generates x. There are several equivalent definitions of K-trivial sets, here is two of them. A are K-trivial if

1. For some constant c, for all x, K(x) ≤ K^A(x)+c, where K^A(x) is the smallest program generating x with access to oracle A.
2. For some constant c, for all n, K(A_1:n) ≤ K(n)+c, where A_1:n are the first n bits of the characteristic sequence of A.

Lots of interesting properties about K-trivial sets.

• All computable sets are K-trivial and there are K-trivial sets that are not computable.
• There are only a countable number of K-trivial sets. In fact there are only a finite number of K-trivial sets for each fixed constant c above. 
• Every K-trivial set is super-low, that is the halting problem relative to a K-trivial set is non-adaptively reducible to the halting problem.
• Every K-trivial non-adaptively reduces to a computably-enumerable set.
• Every set reducible to a K-trivial is K-trivial.
• The disjoint union of two K-trivial sets is K-trivial.
• Random sets are still random relative to A.

More about K-trivial sets and everything else computably random in a great book by Downey and Hirschfeldt. 

Us complexity theorists started thinking about polynomial-time versions of K-trivial sets but probably won't have as many nice properties. 

The Conjunction Paradox

In Yesterday's post you were told about Susan:

Susan is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

You were asked to rank the probabilities of certain things about Susan. Two of the choices were

a bank teller

a bank teller and an active feminist

LOGICALLY bank teller and feminist would have a HIGHER probability than bank teller and and active feminist. Some people (including me when I first was given this exercise) ranked bank teller lower bank teller and active feminist. Why? I think that either people are not good at logic in real-world situations or people implicitly view bank teller as bank teller and NOT an active feminist. This problem has been extensively studied and there are other opinions.

Of the 30 responses I got before posting this roughly 10 ranked bank teller higher than bank teller and and active feminist (which is correct), 10 ranked bank teller and and active feminist higher than bank teller, and 10 of the answers were not relevant (e.g., clarifications of the question). (One person I blocked since he explained the above and would have given away the game, and one person who left a comment 5 minutes ago I will let through but only after I post this.)

I recommend giving this exercise to students in a class that covers logic and/or probability to see what they say.

Clyde Kruskal told me about this problem. He found it here though its also at other sites. This source credits the following (which I would guess is correct). Tversky, Amos; & Kahneman, Daniel (1983), Extensional Versus Intuitive Reasoning: The Conjunction Fallacy in Probability Judgment", Psychological Review 90(4) (October): 293-315. They are famous for these sorts of psychology questions. The latter won the Nobel prize in economics for joint work with the former.

The notion that A is less likely than A AND B is called The Conjunction Fallacy. The article pointed to only gives the two choices: (1) Bank Teller, and (2) Bank Teller and an active feminist. I think its better to give all of those choices as is done here other presentations of this exercise.

Rank these possibilities by probability

Readers- I want you to answer this question and post your answers as comments. I will tell you WHY I am asking tommorow.

Susan is 28 years old, single, outspoken, and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

Please rank the following possibilities by their probability. List them LOW to HIGH. (Just post your answers. Other comments I may block so that others can enjoy the question.)

1. a kindergarden teacher
2. works in a bookstore and takes yoga classes
3. an active feminist
4. a psychiatric social worker
5. a member of the Sierra club
6. a bank teller
7. an insurance salesperson
8. a bank teller and an active feminist

Starting the Year with Turing

This week I was in Boston for the Joint Math Meeting, a combined meeting of the AMS, MAA and a couple of other three-letter math societies with 7000 of my closest math buddies. This is the main American meeting of mathematicians one part of which are interviews for math jobs which seem few and far between.

The conference didn't seem large to me because I spent most of the meeting at the AMS-ASL Special Session on the Life and Legacy of Alan Turing. I got to see some exciting speakers I haven't seen before including Martin Davis, Andrew Hodges (who authored the famous Turing biography soon to be re-issued) and my great-grand advisor Marvin Minsky. Minsky talked mostly about the sorry state of AI over the past few decades including how the Watson people were working on the wrong problem. I found myself in the strange position of defending AI before my talk the next day.

Craig Bauer, a math historian, talked about the early days of voice encryption during Work War II, basically digitizing and then applying a one-time pad. Turing developed a mechanism that used a hardware PRG improving the quality of the audio and reducing the space needed from a large room to small box, though it was never deployed in the field.

Ted Slaman send me this link with Turing suggesting that PRG can help in searching. I guess Turing did care about running time after all but we still haven't found his lost letter on P v NP.

Interesting fact: Gödel and Turing both admired each other's work but there is no evidence that they ever met or had any direct communication of any kind.

A fun workshop but I'm all Turing'd out and it is only the first week of the Alan Turing Year though I am still looking forward to June to attending the ACM Turing Celebration in San Francisco and CiE in Cambridge.

Next week I'm off to Dagstuhl for Computability, Complexity and Randomness. The fun also continues in the Boston area with ITCS.

Is there a NICE gadget for showing PLANAR HC is NPC?

(I have already posted this question on CS Theory Stack Exchange.)

If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget that removes crossings (see here for some lecture notes on it. They are not mine. The original link is here but I can't figure out the real author, though it is likely whoever taught Algorithms at CMU in Spring of 2004.)

Lets say we know that HAM CYCLE is NPC (we do!). Is there a gadget to remove crossings so you can show that PLANAR HAM CYCLE is NPC? The problem of PLANAR HAM CYCLE is NPC so there sort-of has to be a gadget; but is there a NICE one? (The proof that PLANAR HAM Cycle is NPC is from SAT and I find it rather complicated (see here for the original paper.) I have tried to extract an uncrossing gadget from it but have not been able to it.

SO- I ask you, do you know of a NICE gadget for removing crossings in a graph so that we can easily go from HAM CYCLE NPC to PLANAR HAM CYCLE NPC.

I'll be happy with HAM PATH or HAM CYCLE or DIRECTED HAM PATH or DIRECTED HAM CYCLE.

Complexity Year in Review 2011

Result of the Year goes to the new bounds on Matrix Multiplication by Andrew Stothers and Virginia Vassilevska Williams. It's not every year that we see progress on an important problem where we've had no progress since the 80's. Well there was last year. But not every year.

Some other notable results: Impagliazzo's relativized separation of Algorithmica and Heuristica, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup and Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef

We celebrated Les Valiant's Turing Award. We remember Patrick Fischer, Phillipe Flajolet, Steve Jobs, John McCarthy and Dennis Ritchie.

Thanks to our guest posters Daniel Apon, Lauren Cowles, Annie and Molly Fortnow, Nadia Jones, Samir Khuller, Ryan O'Donnell, John Rogers, Jeffrey Stein, Aaron Sterling and Anonymous.

2011 will go down as a year when computer science started changing the world (again). Watson won on Jeopardy. Social networks brought down dictators and congressmen. Obama opens Robotics Center at Carnegie-Mellon. My daughter's high school had their first computer science class in a very long time and Stanford's AI course goes big time. The New York Times has sections on Computer Science's Sputnik Moment and the Future of Computing. The director of the Mathematical and Physical Sciences at the NSF declares "software is the modern language of science". Is there nothing CS no longer touches?

In 2012 we celebrate the man who started it all with a series of events celebrating the 100th anniversary of the birth of the father of computer science. I'll get it started next week talking on "Turing's Influence on Computational Complexity" during the AMS-ASL Special Session on the Life and Legacy of Alan Turing at the Joint Math Meeting in Boston.

Game Changers

Two announcements on Monday connected to my two Alma Maters mark the changing face of universities.

New York City chooses Cornell and the Technion to create new technology campus on Roosevelt Island

It didn't hurt that Cornell got a $350 million donation and that their main competitor, Stanford, dropped out.

Foreign countries have been creating campuses for some time now, like Northwestern's Qatar campus. Great to see this happening in my own country, a realization of the importance of technology and that New York knows it must make these investments. May this lead to other cities building tech campuses like they build sports arenas. Unlike sports, we can have many winners.

What's going to happen on this tech campus? Education, research, start-up incubators? Will there be a separate CS department in New York or just a branch from Ithaca? I can find very little details on the web, though there is this cool fly-over.

MIT launches online learning initiative

Following up on Stanford's online courses, MIT is creating their own tools for teaching online courses and will share these tools with other universities. Those taking the courses may receive a certificate but will have to pay a small fee to do so and the certificate will not bear the MIT name. According to the FAQ "MIT plans to create a not-for-profit body within the Institute that will offer certification for online learners of MIT coursework. That body will carry a distinct name to avoid confusion. MIT awards MIT degrees only to those admitted to MIT through a highly selective admissions process." Nevertheless these courses will allow people to get access to great MIT courses at little cost.

In the 90's, Newspapers decided they could better serve the public by putting their news stories online. How did that work for them? Are universities starting to go down the same path today?

Romney vs. Aaronson

How are Mitt Romney and Scott Aaronson similar? Different?

Similarities:

1. Both live in Massachusetts. Actually, Scott lives there but its not clear where Mitt lives since he's been running for president for the last four years.
2. Both, deep in their heart and soul, believe that Global Warming is a real problem.
3. Both use money to make a point:
   1. Mitt tried to to bet Rick Perry $10,000 that Mitt was never in favor of the individual mandate here.
   2. Scott blogged that if Deolalikar's proof of P ≠ NP is correct, Scott would give Deolalikar $200,000 here.
4. Both were somewhat misinterpreted: Some thought that Scott was insulting Deolalikar. He was not. He was just expressing his certainly the proof was not correct. Some thought Mitt showed he was out of touch with Middle Class American (who normally can't afford to casually bet $10,000 on anything). While Mitt might be out of touch, I think this was more of a way to forcibly express that there is no evidence that he was in favor of the individual mandate.
5. Both Mitt and Scott seem to be right. Deolalikar's proof is no longer believed to be correct, and fact check says that Mitt never supported the individual mandate.
6. There exists people who say Scott is smart. There exists people who say Mitt is smart. I don't know if this means anything since there exists people who say Newt is smart.
7. They both seem smarter than Michelle Bachmann, Herman Cain, and uh,uh, I can't think of the third candidate they both seem smarter than. Oops.

Differences:

1. Scott believes his belief that Deolalikar didn't prove P ≠ NP. Mitt has no beliefs.
2. Mitt can easily afford $10,000. Scott would have to struggle to raise $200,000.
3. Mitt's bet made him look bad. Scott's offer made him look good. He put-his-money-where-his-mouth-is unlike other bloggers who just asserted the proof was likely not correct.
4. Mitt made a bet partially in jest- it is unlikely to really involve an exchange of money. Scott made a real offer- if Deolalikar's proof had been correct he really would have paid out.
5. There is one of them that I would vote for. The other was once Governor of Massachusetts.
6. Scott knows a bit more about Quantum Computing than Mitt.

I emailed the Romney Campaign this post (without this paragraph), and the information that I would post it on Monday Dec 19, in case they had a comment. They did not respond. Perhaps Mitt is miffed about my saying Scott knows a bit more about Quantum Computing.

Algorithmic Driving

In my post last week, my commentors took me to task on my prediction that cars will drive us in ten years. Some thought Americans would wise up and learn to love mass transit. They don't know Americans.

Others thought the hardware cost would even in ten years remain out of reach. Google did not build an autonomous car by creating the hardware but by harnessing and training good machine learning algorithms. No amount of hardware would have given you a car able to navigate the streets of San Francisco five years ago.

What hardware do you need for an autonomous car, beyond the car itself? A good camera, a GPS device, wireless Internet access, gigabytes of RAM and a fast processor. I carry all that in my pocket. Google does use other sensors including lasers and radar but as the algorithms get better, the cost and need for this hardware can be reduced. Wiring the car to drive itself won't be difficult, already the steering wheel and pedals are mostly just a user interface into a computer that is controlling the car.

I have no doubts that technologically we will have autonomous cars in ten years adding at most a couple of hundred dollars over the cost of the car itself.

Other problems could get in the way. One is legal but Nevada is already changing their laws that will allow a testbed for autonomous cars in that state. Once the cars are viewed as safe one would expect the law to expand and other states to open up as well.

The other issue is social. As with every technological change we will have the usual technological life cycle: Innovators willing to pay the big bucks to try stuff first, Early Adopters who love to jump on new technology (where I usually sit), the early and late majorities following the crowd and finally the laggards who still insist on manual transmission and pumping their own brakes.

There are other issues like patents and industries, like auto insurance companies, that will try to fight autonomous cars. Autonomous cars will be too much of a win, in terms of parking, fuel efficiency, shorter and more productive travel time and most of all safety, not to prevail.

Solution to the reciprocals problem

In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant to post this on WED so I posted it at 12:06AM East Coast Time. I didn't know that the blog is on Chicago Time. So it got posted on Tuesday. Oh well.) Here is the problem:

Prove or disprove: there exist natural numbers x₁,...,x₁₀ such that

1. 2011=x₁+... +x₁₀ and
2. 1=1/x₁+... +1/x₁₀.

Several solutions and some other points of interest about this problem are here. The answer is YES and here are the solutions that I know of -- both my solution and the ones emailed to me. (The explanation of how they were obtained are at the paper pointed to above.)

1. My Solution: 2,4,5,80,80,80,160,320,640,640. This used known theorems.
2. Sam Solution: 2,4,5,40,120,160,300,300,480,600. Sam is a HS senior who is very good at these contests. It took him 30 minutes,
3. David Eppstein Solution: 3,4,7,16,16,16,20,43,80,1806. This used a bit of advanced knowledge and some hand computations that were probably above what you want for a UMCP Math Competition.
4. Matt Howell Solution: 2,4,5,50,100,100,250,500,500,500 This solution could have been found by a HS student (it is similar to Sam's solution.) Matt has a BS in Math and Engineering and did the problem in 20 minutes.
5. An anonymous commenter send me 6,6,10,10,12,15,15,15,62,1860. This solution could have been found by a HS student (it is similar to Sam's solution.)
6. Another one from same anon: 6,8,8,8,12,15,16,16,62,1860 This solution could have been found by a HS student (it is similar to Sam's solution.)
7. Mike Roman Solution: 5,5,6,8,8,12,15,32,960,960

So what to make of this?

1. Much to my surprise, enough people got it right and in ways that a HS student could have gotten it. And one did- Sam took the real exam.
2. The systematic solution that I got required very little hand calculation. All of the others, which includes the one I think a HS student could have or did get, required quite a bit of hand calculation. That may be a reason to not ask it.
3. I wonder how many solutions there are. This could be figured out by a Dynamic Program but there may be issues with large ints. (See later in this blog.)
4. I wonder if there are any that have distinct numbers. This can also be figured out by a Dynamic Program, though there may be an easier way.
5. I wonder about the computational complexity of the following problems:
   1. Problem 1 Given a,b in N, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=1. (Can also ask with the stipulation that the x's are distinct.)
   2. Problem 2 Given a,b in N and r in Q, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=r. (Can also ask with the stipulation that the x's are distinct.)

Possible Dynamic Program (more likely you would do it as a recurrence but save all answers found and check to see if you have already computed it, to avoid recomputing.) Let f(a,b,c,r) (where a,b,c are naturals and r is rational) be

num of sols to x₁+...+x_a=b and 1/x₁+...+1/x_a=r. where c ≤ x₁ ≤ ... ≤ x_a.

Note that

1. f(1,b,c,r) = 1 if r=1/b and r ≥ c
2. f(a,b,c,r) = sum as x in {c,c+1,..., min(b,floor(a/r)) } of f(a-1,b-x,x,r-1/x)

(NOTE- Use f(a-1,b-x,x+1,r-1/x) if you want to enforce distinct solutions.)

A math point: Ronald Graham showed that, for all n ≥ 78, n can be written as a sum of natural numbers whose reciprocals sum to 1. The lower bound of 78 is tight: 77 cannot be. A sketch of a proof of this is in the file pointed to. (The proof I give is inspired by one of the comments on the blog. YEAH BLOG COMMENTERS!) (ADDED LATER- Ronald Graham actually proved that for all n &ge 78 n can be written as the sum of DISTINCT natural numbers such that... . The proof I presented in the pointed to document just gives nat numbers, not necc distinct ones.)

Is this problem too hard for a HS Math Competition

The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for an incorrect answer). If you do well on it (the threshold changes from year to year) then you can do Part II which is 5 problems in 2 hours, 30 points each. The winner is the person who does best on the sum of the two parts.

This year I submitted a problem for Part II. The people on the committee who tried it couldn't do it so we decided to NOT put it on the exam. I only knew the answer because I read a theorem and build a problem around it. The people who couldn't do it are very sharp. Since they could not do it the problem was too hard. But... lets see what you think?

I would like YOU to try it without consulting any resources, (and don't look at the comments- someone might post questions that lead to a hint, or the answer) and keep in mind that you can't use advanced techniques (I'm do not think they would help anyway). See if you can do it so I can get a sense if it really is too hard. Post your opinion on if its too hard for a HIGH SCHOOL math competition. Here is the problem:

Prove or disprove: there exist natural numbers x₁,...,x₁₀ such that

1. 2011=x₁+... +x₁₀ and
2. 1=1/x₁+... +1/x₁₀

(ADDED LATER- A commenter thought that the x_i's in the first and second condition could be different. They are not. We want x₁,...,x₁₀ that satisfy both of these simultaneously.)

I'll post a pointer to the solution next time I post. (Probably Wednesday.) ADDED LATER- a commenter wants to know if there is a solution or not and can't wait until WED. Also wants to know if there is a solution is it constructive or proof of existence. To answer the question but NOT ruin it for others, I put it in a file you can click on (or NOT) over here: here.)

A Great Time to be a Computer Scientist

Ask your friends if they'll be driving an electric car in ten years. The answer: No, cars will be driving us.

Today is the 105th anniversary of the birth of computing pioneer Grace Murray Hopper and Computer Science Education Week is being held this week in her honor. If only she could see what we have reaped from what she has sown.

The New York Times this week devoted Tuesday's Science Times to the Future of Computing. The section includes a series of essays from CS researchers including Daphne Koller, Stefan Savage, David Patterson, Kai-Fu Lee and fellow theory blogger Scott Aaronson. Scott also blogged about the experience. Though what would you do with a quantum computer on your desk? The factoring number thing could get boring pretty quick.

The Times also has a crowdsourced interactive timeline of future computing events. Try to guess which one I submitted. Almost all the advances listed are realistic and should keep CS very active for the long future. The most exciting future computer science advances will be the ones we haven't even thought of.

Finally the new class of ACM Fellows includes many theorists including Serge Abiteboul, Guy Blelloch, David Eppstein, Howard Karloff, Susan Landau, Joe Mitchell, Janos Pach and Diane Souvaine. A great year to be an ACM Fellow because the awards ceremony in June will follow a workshop celebrating the Turing Centenary featuring over 30 former Turing award winners.

What is a Breakthrough?

The recent discussion on Matrix Mult inspires the general question of WHAT IS A BREAKTHROUGH? Last year I tried to get an intelligent discussion on this topic but I failed. After saying what some criteria were I applied them in a silly way to several results. This derailed the discussion. My bad, my fault. SO, I'll try again to get an INTELLIGENT discussion on this topic. (NOTE- some of this post is a reworking of the old post.)

Here are some criteria. The first three are extracted from a comment Gowers made on Scott's Blog. I do not know how many a result has to have to be a breakthrough or even if such a threshold makes sense. Perhaps some sort of weighted sum, but would be hard to define.

1. The result breaks a long standing barrier.
2. The techniques introduce a fundamentally different method.
3. The result is practical (or close to it).
4. The problem being discussed is important. This may be a bit circular in that it then depends on What is Important?
5. The result has to make substantial progress on the problem. This may depend on What is substantial? That notion may depend on how long the problem has been open.
6. There has to be a reason why the problem was thought to be hard. E.g., a proof that a new technique is needed, problem has been open for a long time, people in the field say its hard.
7. A paper that STARTS an important field could be a breakthrough. Cook's Theorem and Valiant's PAC learning qualify here.
8. A paper that FINISHES a field could be a breakthrough if the field is important. Again this may be a bit circular in that it then depends on What is Important?
9. The techniques are new. One might end up debating what is new.
10. The techniques can be used on other problems.
11. The paper inspires other papers. For this criteria you need to wait a few years. Some papers are not appreciated for a while.

The notions of important, substantial, new are not Boolean. As Gowers pointed out in his comment, the notion of breakthrough is not Boolean.

Do you have other criteria, examples, counterexamples, constructive criticism of my criteria, or anything that is an intelligent contribution to this topic? Is so, please post a comment!

Probability

On Saturday, Terrence Fine gave a talk on probability at a workshop at Northwestern. Before the talk he asked who thought probability was subjective (an individual's belief in the chance of an event) or a frequentist (a probability represents what happens if an experiment can be repeated many times). Someone noticed I didn't raise my hand either time so I said that I had a computational point of view of probability, since I have a computational point of view of everything.

I didn't mean computation as in Turing machine but as a process. A process that creates events according to some distribution. How does this process work? I don't care. That's the beauty of computational thinking, we abstract out the notion of probability and just make use of it. I've written papers on quantum computation having no idea of the physical processes that create entanglement. I study nondeterministic computation where we have no physical counterpart. Probability works the same way, at least for me.

My contribution to the workshop was to explain Kolmogorov complexity, the universal distribution and its relationship to inductive learning to the mostly economics crowd. Perhaps I could have explained things a bit more clearly as one econ student said to me afterwards "You lost me at prefix free". 

Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)

(Guest post by Ryan O'Donnell)

Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean functions. I am writing a textbook on analysis of Boolean functions and serializing it on the blog as I go. When I'm done, the book will be available online; hopefully it will also be published in the conventional format. (NOTE FROM BILL- its also linked to off of our blog page.)

The topic is sometimes called Boolean Fourier analysis, though my perspective is a bit more from probability theory than harmonic analysis. I hope the book will be accessible and of interest to grad students and researchers in theoretical computer science and other areas of mathematics. Each chapter will end with a "highlight" illustrating the use of Boolean analysis in problems where you might not necessarily expect it. To give you a flavor of the contents, my planned list of highlights is:

• Testing linearity (the Blum-Luby-Rubinfeld Theorem)
• Arrow's Theorem from Social Choice (and Kalai's "approximate" version)
• The Goldreich-Levin Algorithm from cryptography
• Constant-depth circuits (Linial-Mansour-Nisan's work)
• Noise sensitivity of threshold functions (Peres's Theorem)
• Pseudorandomness for F_2-polynomials (Viola's Theorem)
• NP-hardness of approximately solving linear systems (Hastad's Theorem)
• Randomized query complexity of monotone graph properties
• The (almost-)Polynomial Freiman-Ruzsa Theorem (i.e., Sanders's Theorem)
• The Kahn-Kalai-Linial Theorem on influences
• The Gaussian Isoperimetric Inequality (Bobkov's proof)
• Sharp threshold phenomena (Friedgut and Bourgain's theorems)
• Majority Is Stablest Theorem
• Unique Games-hardness from SDP gaps (work of Raghavendra and others)

If you're interested, you can think of it like an online course -- I've been publishing Mondays, Wednesdays, and Fridays, and there are even exercises. (Also like a course, I'll go on break for a few weeks around the new year.) Come see why "juntas" are important, what hypercontractivity "really" means, and why functions on Gaussian space are the "easy special case" of Boolean functions...

PS: I'm using MathJax for the posts; if anyone has suggestions for me or for readers on how to make it look nicer or load better, please do let me know.

Matrix Mult (you heard it here... third?)

(INNOVATIONS CONFERENCE: here)

(While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog: You heard it here THIRD.)

Let w be the exponent for matrix mult. A very brief history of Matrix Multiplication (years given are years of publication, though it is odd to say Pan in 1978 showed that w < 2.796 since, for all I know, he did it in 1977 or even earlier.)

1. The obvious way to do this shows w ≤ 3. This is obvious to us; however, I wonder when it was first stated.
2. Strassen in 1969 showed w ≤ 2.808. This is important since it shows that Gaussian Elimination is not optimal (that is the name of the paper) and also because it is a cautionary tale for lower bounds- w=3 seems optimal... but its not!
3. Pan in 1978 showed that w < 2.796.
4. Bini, Capovani, Romani, Lotti in 1979 showed w < 2.78.
5. Schonhage in 1981 showed w < 2.522 This was significant since it used a brand new technique.
6. Romani in 1982 showed w < 2.517.
7. Coppersmith and Winograd in 1981 obtained w < 2.496. This was significant in that it broke the 2.5 barrier.
8. Strassen in 1986, using a very diff technique, obtained w < 2.479.
9. Coppersmith and Winograd in 1987 obtained w < 2.376. (See here for the Journal Version.) This paper uses the large 3-free sets of Behrend. (See here for Behrends article (it might now work- its the Proceedings of Nat Academy of Sciences website and I don't know if its free to ALL or just to some schools.) or here for my survey of large 3-free sets.)
10. Cohn and Umans in 2003 proposed a group theoretic approach which had the potential for new algorithms. Kleinberg and Szegedy in 2005 obtained new algorithms using the approach, but couldn't beat 2.376.
11. Elkin in 2008 (here) obtained larger 3-free sets than Behrends. Elkin in 2010 (here) used these sets to get a log^v improvement over CW for some v > 0.
12. Andy Stothers 2010 PhD thesis (here) claims to have w ≤ 2.374. The result was not stated in the abstract. He didn't post a preprint or email a blogger so this work was relatively unknown. He did tell some experts in the field. (See the comments on Scott's blog for what might be the full story on that).

Virginia Vassilevska Williams has obtained (ind of Stothers) w < 2.3727 (see here) with a very sophisticated analysis. How do I know its sophisticated? Because the paper is 71 pages long and looks scary.

1. This is clearly a breakthrough! There had been NO improvement in two decades!
2. The improvement is small; however, it may lead to more improvements (this seems to be common in this field).
3. Can Elkin's 3-free sets be used to get a log improvement over Virginia's result? Not sure we care- from what I understand (which is not much) (1) the current techniques can likely be pushed further, and (2) Elkin's 3-free sets will only give a log-ish improvement, no more. (Is log-ish a new word? Should it be?)
4. Is the algorithm practical? I suspect not.
5. Two breakthroughs in theory within a year from the same family. Impressive!

The Death of Complexity Classes?

In the 2011 Complexity proceedings there are three papers that analyze complexity classes, Ryan Williams' great paper on ACC, Russell Impagliazzo's paper on average versus worst case for NP and a Hartmut Klauck's paper on AM in communication complexity. That's the complexity conference. At STOC, there was only the Aaronson-Arkhipov paper on linear optics.

Complexity classes capture important aspects of problems based on how they can use various resources. The complexity zoo has nearly 500 classes. Many of the greatest theorems in theoretical computer science relate classes like NPSPACE = PSPACE, NL = co-NL, PH ⊆ P^#P, IP = PSPACE, NP = PCP(log n,1), SL = L, NEXP not in ACC and many others. The most important open question in our field (and maybe any field) is the relationships of the classes P and NP.

So why do we see so few papers about complexity classes these days? We are victims of our own successes and failures. We have succeeded in classifying and relating most of the connections between classes where we don't have relativizable counterexamples and have failed, outside of interactive proofs, to develop many tools that let us get around relativization and other barriers.

So here we sit, still putting out the occasional paper on complexity classes but mostly hitting a wall. Occasionally we see a nice breakthrough like Ryan's paper but mostly we are just clawing at that wall waiting for someone to create a wrecking ball so we can make real progress. 

The Jobs Bio

I just finished the Walter Isaacson biography of Steve Jobs. Seems like everyone in the blogosphere has analyzed every sentence in the book, so I won't do that.

Instead I viewed the book as a trip down memory lane. The Apple II was my second computer and while I never owned a Mac you can't avoid them in the CS community. My family has by now gone through a dozen or so iPod/iPhone/iPad devices.

The biography opens up the curtain and you get to see the man behind these devices. Jobs was not a computer scientist or even a computer engineer. He was a designer who understood computers enough to make them beautiful and make them work better. His simplicity sometimes goes too far, I like the context-sensitive menus from a right mouse button and often double click the one button on my iPhone instead of single click or vice-versa.

I found myself least interested in Jobs' personal life, most of the problems he dealt with were of his own doing. He wasn't a nice guy and often got upset with people who don't share his values. But he also knew how good technology should work and we're better off for it.

I love reading biographies of successful people, you really get to see a fuller picture both the good and the bad. Walter Isaacson's book is rather unique, rarely do we get such a complete picture so soon after his untimely death.

If Steve Jobs isn't your thing, try Isaacson's bio on Einstein instead, another great read.

Short Bits

Because some things are too long to tweet and too short for their own blog post.

What's the algorithm for the perfect sushi? Enjoy it with some cool refreshing SODA in Kyoto. Early registration deadline is December 20th and lots of travel support still available (apply by Nov 29).

What's new for STOC 2012 in New York City? An open call for workshops (apply by Dec 2) and a best student presentation award. Practice up. Please also nominate people for Gödel, Knuth and SIGACT Distinguished Service prizes.

Google scholar citations now open to all. Now you can see my papers at Google, Microsoft, ACM, DBLP and my own papers page. Google has the best stats and ranking, DBLP the best links, my page the most accessible downloads and Microsoft has the coolest graphics.

Google gives all the stats so we can rank job applicants. Why stop there? Google can use their magic algorithms to tell us who to hire. No more messy recommendation letters and awkward interviews.

Are these journals real?

Consider the following email I got:

Dear Professor,
 1. Antarctica Journal of Mathematics
 2. ArchimedesJournal of Mathematics
 3. BesselJournal of Mathematics
 We are charging only $3 per page,
 which is very cheap when compared to
 other money oriented journals.
 Further we request you to withdraw your paper,
 if you have already submitted it to any money
 oriented journal.  You can submit your research
 papers to our online journals.
 We also consider paper from
 Statistics and Computer Science.

What is going on here? Possibilities:

1. The journals are fake. They are part of an April Fool's Day joke. Using BesselJournal and ArchimedesJournal, with no space in the obvious place, (not typos by me- this is what the email said) might have been a clue that they were jokes.
2. The Antarctica journal is real and is a reaction to the notion that we shouldn't hold conferences or workshops in places where there are human rights violations. (See here.)
3. The Antarctica journal is real and is a reaction to the notion that whenever you have a conference the locals get to go cheap; this conference will be equally expensive to all (or to most). (See here.)
4. The journals are real. The Antarctica Journal of Mathematics was founded because all continents except Antarctica had journals and the founders thought this was unfair.

The last option is the correct one. I am not surprised- the journals have to be real since the titles are not quite funny enough to be a joke. Antarctica Journal of Mathematics sounds fictional, like The University of Southern North Dakota at Hoople, but it is not. The Antarctica Journal's website has real articles on it and seems to have been publishing since 2004.

In some fields it is standard to pay-to-publish. Older faculty used to tell me about page-charges for journals in our field, in much older times, (and I think grants mostly paid for it) but I have never seen them in my academic lifetime (in math and TCS). (Exception: a few conferences, though not many.) Different fields evolve in different ways, and I do not claim to know what the best approach is. However, since in our field (Math, TCS) it is standard to NOT have page-charges (I do not know of any journal that does this, and I know of only a few conferences that do) it seems odd to ask you to compare their journal with other money oriented journals. Are there other ones in mathematics?

Penn State

Take the state of Pennsylvania and draw the two diagonals. Where they cross is the small town of State College, home of the Pennsylvania State University. I first traveled to Penn State in 1989 on an interview trip. We went to dinner at the only nice restaurant near campus. The conversation turned to Joe Paterno, Penn State football coach. The waitress, a Penn State undergrad, said "Oh, you mean God."

As many of you know, Paterno and Penn State president Graham Spanier were fired last week in the wake of the Jerry Sandusky child sexual abuse scandal.

I have a certain affinity for Penn State.I have worked with researchers there from experimental economics to pure logic and they have a number of people there connected to my NEC days. I have been back to that campus several times most recently in the spring of 2010. The changes in those two decades have been amazing.

Quite a bit of new building on campus and off. There are now a number of nice restaurants near campus. There are plenty of new buildings on campus too including a beautiful IST (Information Sciences and Technology) building that houses the IST and CSE departments. Just in theoretical computer science, Penn State made some recent strong hires and had a rare double PECASE win of Adam Smith and Sean Hallgren.

Paterno helped build the Penn State brand through football which he coached at Penn State since I was a toddler. Paterno also knew that Penn State meant academics as well, he had a large number of academic all-Americans on his team and donated money for a library on campus that bears his name. Spanier build on this brand to develop real growth in the university and the town it lives in.

Paterno and Spanier should have done more to protect the children but I hated to see them leave under these circumstances. They have both done much for Penn State and not just on the football field.

My response to the Gasarch P vs NP poll

A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers.

1. Does P=NP? I think P is NOT NP. However, I am not dogmatic on this. When I first saw the Graph Minor Theorem used to get Vertex Cover for fixed k into O(n³) times I thought that a different very-hard-math-thing-that-I-don't-understand might be able to get SAT in P. Also, I am more convinced that separating the two is hard then I am convinced that they are different. Litmus test: If someone told me that the problem had been solved, but not which direction, I would guess P=NP. SIDE NOTE: My wife thinks P is NOT NP since If P=NP then they would have proven it by now. This argument may become more compelling as time goes on.
2. When do you think it will be resolved? Between 200 and 400 years from now. Jon Katz told me: If its not solved within 200 years its not going to be solved..
3. What kinds of techniques will be used?
   1. Fermat didn't know about Elliptic Curves. Similarly, we do not know the techniques.
   2. I hope its Ramsey Theory and Logic so I might understand the proof.
   3. If it comes out of Geometric Complexity Theory I will not understand the proof.
   4. We will show that P ≠ NP by showing that FACTORING is not in P. SAT might not be a good candidate for separation. This kind of thing has happened before (once): The proof that AC₀ ≠ NC₁ was done by showing PARITY not in AC₀. PARITY is not complete for NC₁ under AC₀ reduction. The word problem for S₅ is, but was not useful for separation. Factoring may be a better candidate for separation since you can generate instances that seem hard, where for SAT this seems hard to do.
   5. Ryan Williams great result shows that there are still things we can do with what we know now. Is P vs NP one of them? NO.
4. Will the problem still be relevant given advances in SAT solvers? YES. Sat Solvers are GREAT and can solve lots of things- perhaps more than we had thought. But there are still lots that are not. The 17x17 problems has resisted attempts by SAT solvers to solve it (or so I've been told). The problem is a 4-CNF with 4 × 17² vars (not that many), and roughly 4 × 17⁴clauses (too many).
5. Feel Free to comment on other things:
   1. Graph Isomorphism: We will show P ≠ NP but still not know the status of GI. OR we could find that GI is in P tomorrow.
   2. As noted above, we will show Factoring is NOT in P.
   3. Quantum Computers will never be practical; however, see next note.
   4. Just as the Prob Method is now a STANDARD thing to know even if you are not working on probability, Quantum methods will be a standard thing to know even if you don't work on quantum computing.
   5. We will show L=RL before I do this poll again.
   6. Within 10 years all supermarkets will have self-checkouts that work nicely and that you are expected to use--- except in New Jersey which will outlaw them to create more jobs (as they do now for self-service gas).

Making Money the (Computationally) Hard Way

Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto class. Most of the material I find about Bitcoin is either very high level for a typical user or very low-level detail for the implementer. In this post I'll try to hit the middle ground.

Bitcoin tries a different approach to digital case. Their goal is not anonymity but more a cash system that works in a peer-to-peer network without a central authority.

The basics of Bitcoin come from a paper by the mysterious Satoshi Nakamoto. The Bitcoin systems doesn't use encryption but it does make strong use of secure hash functions and digital signatures. A user establishes an account by creating public and private keys for an elliptic-curve based signature scheme. A hash of the public key serves as the account number.

A transaction from person A to B roughly consists of the amount, a link to an earlier transaction where A received bitcoins, B's account number, A's public key and A's signature of all of the above. Transactions are transmitted to everyone. More general transactions are also possible.

Transactions aren't accepted until they appear in a block. A block consists of a hash-tree of transactions, an extra transaction giving 50 bitcoins to the block creator (this will decrease over time), a hash of the previous block, a time stamp and something called a nonce. The nonce is just an extra number chosen so that the hash of the block has a certain number of zeros in the right place.

You create money by creating blocks which requires finding the right nonce, a computationally difficult task. The number of zeros is set so that a new block is created on average every ten minutes. A transaction is accepted when there is a chain of six block starting with the one where the transaction occurs. This prevents double spending as that firmly establishes this chain as the "official" one.

There's a lot more details but the idea is a clever use of computation to mine money like one can mine gold with considerable effort. Or you can get money by trading goods or services (or real currency).

Not clear to me that it could scale for wide-spread use but still quite a clever and so far working system.

The Annual Fall Jobs Post

For these looking for an academic job in computer science next year, best to start on the jobs pages of the CRA and the ACM. Both lists seem long this year, perhaps the job market is finally beginning to pick up.
Also check out the postdoc opportunities on Theory Announcements.

Feel free to list other job opportunities in the comments.

My department has two faculty positions for next year. Neither one specifically in theoretical computer science but we do plan to treat the areas broadly.

My advice: Apply widely, the job market is quite unpredictable. Put real effort into your research statement and be sure your CV is informative yet concise. Most importantly: Choose your letter writers well.

Journals

What is the purpose of an academic journal? To provide a permanent vetted record of a specific research endeavor.

The ways we communicate scientific research has vastly improved, particularly with the advent of the Internet, but the need for that basic mission will never go away.

Noam Nisan laments that journals do not provide a quick form of dissemination or do the proper amount of vetting. He's correct on both points. Computer scientists need to take journals more seriously to improve the vetting process and the speed to publication. But also journals have never played the role of quick dissemination in computer science. That role has been taken by conferences, departmental technical reports and more recently on-line archives. Journals don't compete with sites like ArXiv, they play different roles.

Tim Gowers suggests a commenting/scoring system for reviewing papers. I'd love to see such a system built into ArXiv and ECCC. But it won't supplant the need for academic journals. Most papers won't get reviewed and most researchers won't review papers. Collaborative projects like Wikipedia, Polymath, Math Overflow (and the TCS descendant) are incredible resources but just a small number of researchers are significantly involved. If you reward people for reviewing papers (through reputation or otherwise) then people can decide not to review guilt free. 

We are moving to a world where we rank research papers not on where they appear but by how many citations they achieve, a statistic the Internet has made easier to measure. One can cite an ArXiv paper just as easily as a JACM paper. The incentives for an author to do more than throw up a paper on an on-line site are going away. We will no longer fulfill the mission of journals and future scientists will struggle understanding the how and why of what we did. Is this the gift we want to leave to the next generation?