Disproving the Myth that many early logicians were a few axioms short of a complete set

While I was working on this post another blogger posted on the same topic here and I found a book review of Logicomix that touched on some of the same issues here. (For MY review of Logicomix see here.) They are very good sources and I will refer to them in this post.

There is a notion that logicians who work in foundations early on in the field were crazy. I give examples of where this is said and then I look at the real evidence.

1. In Rudy Rucker's post about Turing he writes

   ... it really does seem possible that Turing killed himself. Like the other logicians Godel and Cantor, he seems to have been somewhat nuts. Funny how many logicians are crazy and irrational. A paradox.

2. In Logicomix, a great comic book about the foundations of logic, there is an allusion to Logicians being crazy.
3. In Gian-Carlo Rota Indiscrete Thoughts he writes: it cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some point in their lives: Cantor, Zermelo, Godel, and Post are some.

I've also seen an explanation for this alleged phenomena: Logicians were searching for absolute certainly and either it can drive you crazy or thinking you can find absolute certainly means you were crazy ahead of time.

So the people above, and others, give some examples of logicians being crazy and then claim that many logicians are crazy. I am reminded of people who say It was cold the other day, looks like Global warming is wrong.

Let us look at the actual record. I will look at all of the logicians in Wikipedia's list of logicians who

1. were born between 1845 and 1912. (1845 is when Cantor was born, 1912 is when Turing was born.)
2. I ruled out a few people who were really philosophers, and also Banach who I don't think would call himself a logician.

For each logician on the list who meets my criteria I say if I think they are sane or a few axioms short of a complete set. I am not a historian--- corrections are more than welcome. I also freely admit that crazy is not well defined.

You may well disagree with what years I pick and my opinions. The point is to get an intelligent discussion going.

1. Wilhelm Ackerman (1896-1962): He defined the function that bares his name. He also worked on the epsilon-calculus which formed the basis for Bourbaki's logic. Reading Bourbaki might drive one crazy; however, forming the basis for it does not. He was quite sane (Ackerman that is-- Bourbaki had multiple personality disorder.)
2. Alice Ambrose (1906-2001): She had the longest lifespan of anyone on this list. She studied with Moore and Wittgenstein and got two PhD's. (In those days a women had to do twice as much as a man to get a job.) She was more on the philosophy side of logic, but certainly had math training. She wrote a textbook with her husband, known as Ambrose and Lazerowitz. Sane!
3. Paul Bernays (1888-1977): He worked with Hilbert on alternative set theories. Sane!
4. Evert Willem Beth (1908-1964): He helped to establish Logic as a discipline. Sane!
5. L.E.J. Brouwer (1881-1966): He thought that all math should be constructive. This point of view lost the battle if ideas; however, that does not make him crazy. The Wikipedia article quotes Martin Davis as saying: he felt more and more isolated, and spend his last years under the spell of totally unfounded financial worries and a paranoid fear of bankruptcy, persecution, and illness. However, Dirk van Dal en wrote a scholarly two-volume biography of Brouwer that indicates that Brouwer was not crazy. And I agree. Sane!
6. Georg Cantor (1845-1918): He had a new way of looking at infinity that was brilliant and is now accepted. That does not make him crazy. He was also convinced that Bacon wrote the plays of Shakespeare and that Joseph of Arimathea was the father of Jesus Christ. That does not make him crazy. However, he was obsessed with these views and was in and out of sanitariums. A few axioms short of a complete set.
7. Rudolph Carnap (1891-1970): I originally thought he was more of a philosopher; however, he published in thermodynamics and the foundations of probability. He fled Hitler's regime and later refused to sign a loyalty oath in America (during the McCarthy Era). His second wife committed suicide. He led an interesting life but was sane.
8. Alonzo Church (1903-1995): He invented (discovered?) The Lambda Calculus, proved that Peano Arithmetic was undecidable, and articulated what is now called the Church-Turing Thesis. These are all sane things to do. (Bob Soare distinguishes Church's Thesis from Turing's Thesis here.)
9. Haskell Curry (1900-1982): He worked in combinatory logic. There is a programming logic named after his first name! (see here). Sane!
10. Adolf Fraenkel (1891-1965): The F in ZF-set-theory. Provably Sane!
11. Gottlob Frege (1848-1925) He hated Jews, Catholics, and the French. That might make him unpleasant to hang around, especially if you are a French Jew who converts to Catholicism. However, that does not make him crazy. He is often given as an example of someone who was crazy, though the links ( here and here) argues for Frege being sane. I defer to the two links. Sane!
12. Gerhard Gentzen (1909-1945): He made the cut- Sane!
13. Kurt Godel (1906-1978): He stopped eating because he thought people were trying to poison his food. They weren't. A few axioms short of a complete set.
14. Jean Van Heijenoort (1912-1986): Best known in Logic for writing From Frege to Godel, a history of Logic from ... Frege to Godel (duh). Best known outside of logic for being Trotsky's secretary and later a historian of that movement. He was killed by his estranged fourth spouse. An interesting life, an interesting death, but he was sane.
15. Jacques Herbrand (1908-1931) Has the shortest lifespan (died at 23 in a mountaineering accident) of anyone on this list. He worked in proof theory. Sane!
16. Arend Heyting (1898-1980) He continued Brouwer's work on intuitionism. Sane!
17. David Hilbert (1862-1943): In Logiccomix they claim that Hilbert's son Franz had a mental illness and Hilbert cut off all contact with him. However, this refutes this and claims that Hilbert's son was only put away for 3 years and then re-joined his family. One may question if David Hilbert deserves a World's Greatest Father mug, but one cannot question his sanity.
18. Clarence Irving (1883-1964): He took exception to Principia's use of material implication. I'm impressed that he read and understood Principia enough to have objections. Sane!
19. Stanislaw Jaskowski (1906-1965): He worked in Intuitionistic Logics. Since I can't prove that he was crazy I assume he was sane.
20. William Ernest Johnson (1858-1931): He wrote three volumes on logic which showed technical expertise but was superseded by Principia Mathematica. This did NOT drive him crazy. Sane!
21. Philip Jourdain (1879-1919): He was interested in paradoxes and formed the card version of the liar's paradox. He also worked on algebraic logic. Quite sane. His sister Eleanor Jourdain claimed to have traveled through time and seen ghosts, but was not a logician.
22. Stephen Kleene (1909-1994): Kleene hierarchy, Kleene star, Kleene algebras are all named after him. He also proved the recursion theorem. Did this go to his head and make him insane? NO- he was totally sane.
23. Christine Ladd-Franklin (1847-1930): Her PhD was on Algebra and Logic. She faced problems being a women in a man's field but kept her sanity.
24. Stanislaw Lesniewski (1886-1939): He rejected axiomatic set theory (because of Russell's paradox) and tried to obtain other formal systems to replace it. A noble effort that failed. Still, he kept his sanity.
25. Adolf Lindenbaum (1904-1941): He proved Lindenbaum's Lemma- every consistent theory of predicate logic can be extended to a complete consistent theory. Like many major advances, profound at the time, easy to prove now. Certainly sane.
26. Leopold Lowenheim (1878-1957): The Lowenheim of Lowenheim-Skolem. See Skolem for more on that. A model of sanity.
27. Jan Lukasiewicz (1978-1956) Wikipedia says He thought innovatively about traditional propositional logic. Is innovatively a word? My spell checker does not think so but whoever wrote his Wikipedia entry thinks so. Sane.
28. Saunders Mac Lane (1909-2005) (He preferred the space between Mac and Lane.) His PhD thesis was on Logic and he also worked in Category theory. But he also did lots of Algebra. Sane.
29. Carew Arthur Meredith (1904-1976): He worked on obtaining short axiom basis for logic systems. Sane.
30. John von Neumann (1903-1957): Calling him a logician seems odd since he contributed to so many fields. Sane.
31. Jean Nicod (1893-1924): Co-discovered the Sheffer Stroke from which you can do everything in prop logic. Sane.
32. Pyotr Novikov (1901-1975): He proved the word problem for groups undecidable. His son Sergei Novikov won a Fields Medal in 1970 and, more importantly, is a professor at The University of Maryland! Sane.
33. Giuseppe Peano (1858-1932): His Wikipedia entry calls him the founder of Mathematical Logic and Set Theory. That seems over-the-top, but not by much. His axiom system is still the standard. Sane.
34. Emil Post (1897-1954) He introduced Turing Degrees. In the mid 1940's he posed Post's Problem which is to find a r.e. set (now called c.e.) that is neither decidable nor complete. This was solved in 1956 by Friedberg and Munhnik independently. He suffered from mental illness. A few axioms short of a complete set.
35. Mojzesz Presburger (1904-1943): Presburger proved Presburger Arithmetic was decidable. What are the odds of that!? Sane!
36. William Quine (1908-2000): He was more of a philosopher; however he did do some math. At Harvard he taught Symbolic Logic every fall for 50 years. That might drive some crazy; however, he was quite sane.
37. Frank Ramsey (1903-1930): The paper where he proved what is now known as Ramsey Theory was titled A Problem in Formal Logic and solved a case of the Decision Problem. He regarded himself as a logician so we shall too. Speculation: He would be surprised at where his work lead to (combinatorics) and then pleased that it lead back to logic again : The Large Ramsey Theorem (see also here) and much work in the reverse mathematics of Ramsey's theorem".
38. Raphael Robinson (1911-1995): He worked in Logic and Number Theory. He is probably best known for his work on tiling the plane. He married Julia Bowman (who changed her name to Julia Robinson) who was also a logician but born in 1919--- a little too late to be on this list. Having two academics in the same area get married might drive some crazy, but not them. Sane!
39. J. Barkley Rosser (1907-1989): He strengthened Godel's incompleteness theorem. Sane!
40. Bertrand Russell (1872-1970): He was obsessed with the quest for certainty; however, that does not make him crazy. He had several wives (not at the same time) and believed in open marriage. He was not crazy, just ahead of his time. Sane.
41. Moses Schonfinkel (1889-1942): He worked in Combinatory Logic. By 1927 he was in a sanitarium. The only non-famous logician on my list who was a few axioms short of a complete set.
42. Thoralf Skolem (1887-1963): He is best known for the Lowenheim-Skolem theorem: The notion that any consistent set of axioms has a countable model is very interesting--- One corollary: there is a countable model of the reals. Thinking about that might drive some crazy, but not him. Sane!
43. Alfred Tarski (1901-1983): The Banach-Tarski paradox is crazy; however, Tarski was not. Sane.
44. Alan Turing (1912-1954): He defined Turing Machines, though he didn't call them that. The story I had assumed was true is that the British Government made him take hormones (or something) to cure him of his homosexuality, and this drove him to suicide. But the story doesn't quite work with the timeline. He committed suicide a few years after he was forced to take drugs. Delayed reaction? Suicide for some other reason? Really was an accident? In any case, since his possible suicide is the only evidence that he was crazy I say Sane!
45. Nicolai Vasilev (1880-1940): The originator of non-Aristotelian logics. Sane.
46. Alfred North Whitehead (1861-1947): In Russell-Whitehead's Principia Mathematica they spend 300 pages proving that 1+1=2. This might drive some insane but not him. Whitehead was stark raving sane.
47. Ludwig Wittgenstein (1889-1951): He gave away all his money and seemed to be a self-hating Jew. Odd yes, but he was sane. (NOTE- Scott Aaronson left a comment that argues that Wittgenstein should be classified as a few axioms short of a complete set. I believe his arguments (they are backed up by facts) and may later redo the stats at the end of this post.)
48. Ernest Zermelo (1871-1953): The Z in ZF set theory. He disapproved of Hitler's Regime. Hardly crazy. Rota says that Zermelo was crazy but neither I nor this post have been able to find any evidence of this. Zermelo did spend time in a hospital for lung problems, which may have confused Rota.

So what to make of all of this?

1. Cantor, Godel, Post and Schonfinkel were crazy. So we have 4 out of 48 were crazy. That's around 8%. This website claims that 6% of all people are crazy. So 8 seems high, but the sample space is pretty small. Conclusion: Same as the posts on the same topic referenced at the beginning: the notion that people in logic are crazy is not well founded. In addition, this post argues that the problems Cantor, Godel, and Post had were unrelated to their study of logic. (There was no comment on Schonfinkel.)
2. AH- but Rota said that so many outstanding logicians were crazy. Since three of the four who I say were crazy were outstanding there may be a point here. One could look at who on my list was outstanding and see what percent of them logicians were crazy. However, determining who was outstanding is even harder than determining who was crazy, so I leave it to others to continue this work.
3. There were some on the list that in my opinion were sane but others think were crazy: Brouwer, Frege, Turing, Zermelo. Perhaps more. If enough of them turn out to be crazy then there may be something to this logicians are crazy theme; however, I doubt this will happen.
4. Was it crazy to spend so much time and effort on this one post? I am not on the logic list, nor was I born between 1845 and 1912 so the answer is not relevant to the study.
5. This blog posting has a crazy number of links: 71. That breaks the record for this blog which was held by this entry which had around 37.

Math, the Universe, and Everything: Max Tegmark's Interpretation of reality (guest post)

(This is a guest post by Nadia Jones who blogs at online college about education, college, student, teacher, money saving, movie related topics. You can reach her at nadia.jones5@gmail.com. Why is she doing a guest blog? She asked me, pointed me to some of her work, and suggested some topics that seemed reasoanble. You can do that too!.)

Math, the Universe, and Everything: Max Tegmark's Interpretation of Reality

Despite how much mathematicians like to think that their work is the end-all, be-all, it can be sometimes quite complicated to explain to friends and family who are not familiar with the pleasures and perils of doing high-level math exactly why it is so important. At the same time, however, devout followers of math still realize that there is an element of get-your-head-out-of-the-clouds, especially when dealing with abstract mathematics that do not directly apply to career paths that are lucrative or have potential for advancing research in an academic setting.

But what if someone were to tell you that everything that we know, everything that we feel, is all a complex series of mathematical structures? Of course, many have theorized that math and disciplines that are heavily math-based like physics, are very accurate ways to describe the world as it exists, but cosmologist Max Tegmark takes things one step further.

In an absolutely fascinating article published in Discover Magazine, here Tegmark explains his theories that were almost impossible to publish or even be taken seriously a few years ago. Taking a leaf out of string theory's book, Tegmark has endeavored to explain what is known in popular science as "alternative" or "parallel" universes. In more serious academic circles, these universes are known as "multiverses." Tegmark notes that others have posited three multiverses, but he has added a fourthâthe mathematical multiverse. (Another article about Tegmark is here.)

Tegmark describes this particular multiverse as such in the Discover interview:

Galileo and Wigner and lots of other scientists would argue that abstract mathematics describes reality. Plato would say that mathematics exists somewhere out there as an ideal reality. I am working in between. I have this sort of crazy-sounding idea that the reason why mathematics is so effective at describing reality is that it is reality. That is the mathematical universe hypothesis: Mathematical things actually exist, and they are actually physical reality.

Although Tegmark's work has not received as much critical attention as other mathematician's work, it his is melding of physics, pure math, and cosmology that has helped his research be more seriously considered. For more information on Tegmark's theories, check out his MIT hosted website, The Universes of Max Tegmark

A slightly diff take on Lipton's use of Ramsey's Theorem

This post takes an idea of Dick Lipton's in a slightly different direction.

ω(G) is the size of max clique in G.

Recall that, for all 0 < δ₁ < δ₂ < 1, the following problem is NP-hard: Given a graph G with the PROMISE that either ω(G) ≤ n^δ₁ OR ω(G) ≥ n^δ₂, determine which one it is. Output NO in the first case and YES in the second case. (Reference: David Zuckerman proved the result here by derandomizing a result of Johan Hastad that had as its conclusion ZPP=NP rather than P=NP. See here for Hastad paper.)

Note the following,

If ω(G) ≥ n^δ₂ then, by Ramsey's Theorem and the current bounds known on the Ramsey numbers, for ANY 2-coloring of the edges of G there will be a mono clique of size (0.5)*(δ₂)log n. (Slightly larger values can also be obtained.)

This gives rise to the following POSSIBLE RTIME(n^{O(log n)}) algorithm for the promise problem.

1. Input G
2. Do the following n^{Alog n} times Or until you get a NO. (A is a constant that we pick later.)
   1. Randomly 2-color the edges of G
   2. Look for a mono clique of size (0.5)*(δ₂)log n. (This takes n^{O(log n)} time.)
   3. If you DO NOT find one then output NO and stop. (In this case you KNOW the answer is NO.)
   4. Otherwise try again.
3. (If you got here then every coloring you tried had a mono clique of size (0.5)*(δ₂)log n.) Output YES. (You are NOT SURE that this is correct.)

The algorithm clearly runs in time n^{O(log n)}. But does it work? And what should A be?

1. IF ω(G) ≥ n^δ₂ then the algorithm will correctly say YES.
2. IF ω(G) ≤ n^δ₁ then will the algorithm find a coloring that shows this? Or more precisely, will this happen with high prob?

In order to get NP in RTIME(n^{O(log n)}) we need the algorithm to work for SOME 0 < δ₁ < δ₂ < 1. Hence we need the following CONJECTURE to be true:

There exists 0 < δ₁ < δ₂ < 1, A, and a function p(n) = n^{Alog n} such that the following is true: For almost all graphs G with ω(G) ≤ n^δ₁ the prob that a rand 2-coloring of the edges will have a mono clique of size (0.5)*(δ₂)log n is LESS THAN (1-p(n)). (ADDED LATER: Almost All Graphs means for all but a FINITE number of graphs.)

So, what to make of this?

1. One MAY think the following; Since we DO NOT think that NP is in RTIME(n^{O(log n)}) the conjecture is false. Perhaps it can be PROVEN false (unconditionally) using the techniques of Zuckerman or Hastad, or other techniques in the area.
2. Is our confidence that NP is not in RTIME(n^{O(log n)}) SO STRONG? We could at least TRY to prove the conjecture.
3. One could put the correct Ramsey Number, and a good set of coin flips, into an advice string. This would yield an algorithm in DTIME(n^{log n})/poly. A slighly weaker conjecture would suffice to prove this algorithm works.

FOCS Accepts

This list of FOCS accepts are out, with abstracts, with PDF links (via Kintali) and in Algorithmic Game Theory (Nisan) and Algorithms (Eppstein). The FOCS Conference will be held October 23-25 in Palm Springs.

Looks like a strong collection of papers. Lots of tight bounds. I'm a sucker for tight bounds because it means you have the right answer and less chance of follow-up papers.

Here are a few of the papers that caught my eye.

Randomness buys depth for approximate counting by Emanuele Viola. Buys you exactly two layers of AND-OR gates. Viola has another nice paper Extractors for circuit sources.

A Small PRG for Polynomial Threshold Functions of Gaussians by Daniel Kane. I like Gaussians because you can look at them at any angle and the distribution doesn't change.

Optimal bounds for quantum bit commitment by André Chailloux and Iordanis Kerenidis. Perfect quantum bit commitment is impossible but you can do better than classical. This paper shows exactly how well you can do.

Information Equals Amortized Communication by Mark Braverman and Anup Rao. A nice connection between information theory and communication complexity. I wonder if this can be tied into Kolmogorov complexity.

Scooped by 400 years

This article claims that finding the area under a curve by dividing up the region into rectangles is helpful. Maybe they could take some sort of... limiting process where the rectangles get skinnier. Who knows- they may be able to get an EXACT formula for, say, the area under the curve y=x² from x=0 to a. (The Wikipedia entry on the article claims that it rediscovered the trapezoid rule. See here.)

I was going to begin an April fools day post with the above; however since the article (which is real) is already out there and being criticized here, here, here, here, and here, I decided to not go that direction. I have a different angle.

How often do you get a result and then find that someone else already had it? Is this MORE or LESS common in the internet age? There are several competing forces:

1. With Search tools its EASIER to find whats already out there.
2. With email or various websites like stack exchange it is EASIER to ASK if something is already known.
3. Some people are gathering up stuff and putting it on line making it EASIER to find- if you know where to look. (Examples: Website of all of Ronald Graham's papers, or Website of some number theory related to VDW stuff). I thought I found a website of secret sharing papers and when I tried to find it again I hit several sites about different kinds of secrets.) ADDED LATER: updated site for Ron Graham's papers: here, and list (but not links) of papers on secret sharing are here.)
4. Areas are getting more specialized and each use their own terminology making it HARDER to know if what you have done is original.
5. There is so much is out there that it is HARDER to see whats already been done.
6. NOT everything is online. The material that is not online might be HARDER to find then they used to be.

There are other issues. What if your proof is cleaner but essentially the same? What if it truly is independent? What if people come from completely different motivations? What if you read a result, forget that you read it, and later think its yours (its not). I've seen all of these things things happen and in all combinations.

The Quantum Tivo

Chuck Klosterman writes on watching sports on tape delay and Jeff Ely follows up. I take a quantum mechanics view: A sporting event saved on my Tivo is like Schrödinger's cat: Until I watch the game or otherwise learn the result, the outcome hasn't been determined. There are multiple worlds with different game outcomes and until observed we do not know which world we live in. There is no physical difference between watching an event live or delayed. If I get partial information on the outcome, like a half-time score, then the outcome is then just conditioned on this partial information.

We also have entanglement. Two people can be light-years apart watching the same gave on their Tivos. They will see the same outcome. The Tivo's are entangled. Even though in each person's view the outcome is random, they will be random in the same way.

That's where the analogy to quantum ends. Entangled Tivos can't explain Bell's inequalities.

Let me add a reason for watching on tape delay: The fast-forward button. If a game looks one-sided, I can speed up the game to see if it gets close again. And some sports (yes, soccer, I'm talking about you) are vastly improved with the entire game watched in double speed. 

The Sputnik Moment

Earlier this month the New York Times had a story Computer Studies Made Cool, on Film and Now on Campus followed-up on a series of short essays on Computer Science's 'Sputnik Moment'. No doubt computer science is a hot major again, the number of CS majors at Northwestern has doubled over the past few years and I hear similar stories elsewhere. My daughter's high school will offer computer science for the first time in years. Big companies are using real computer science ideas from IBM's Watson to Netflix's recommender systems to nearly everything Google does. Obama talks robots at Carnegie-Mellon.

Mehran Sahami called this Computer Science's Sputnik Moment, evoking the phrase used by the president in his State of the Union Speech.

 Half a century ago, when the Soviets beat us into space with the launch of a satellite called Sputnik, we had no idea how we would beat them to the moon.  The science wasn’t even there yet.  NASA didn’t exist.  But after investing in better research and education, we didn’t just surpass the Soviets; we unleashed a wave of innovation that created new industries and millions of new jobs.

This is our generation’s Sputnik moment.  Two years ago, I said that we needed to reach a level of research and development we haven’t seen since the height of the Space Race.  And in a few weeks, I will be sending a budget to Congress that helps us meet that goal.  We’ll invest in biomedical research, information technology, and especially clean energy technology -– (applause) -- an investment that will strengthen our security, protect our planet, and create countless new jobs for our people.

The fate of that budget remains unclear in the current congress.  But there's an excitement for CS and science in general that we haven't seen since the 60's.

Computer Science seems to run in cycles, we build up excitement (the spread of personal computers in the early 80's, the Internet in the 90's and social networks and machine learning today) and soon after people see these as commodities and the excitement wanes. We need to not squander the current good will, find a way to keep CS exciting. The computer science story has a long way to go. Computer science needs to be a front office profession leading the way and not just in the back office keeping it going.

Math on FUTURAMA and LAW AND ORDER:CI

MATH ON TV

FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-Shrinker which takes a blueprint of an object (like a sweater or Bender) and some matter and then produces two smaller but otherwise identical copies of the original. The real Banach Tarski Paradox takes one object and produces two of the exact same type. The writers might have felt that was just a little too weird. See here for a full description of the episode. The episode aired on thursday, and today, Tuesday, a full description is on Wikipedia. This surprised me (so fast!) but did not surprise my great nieces and nephews.

LAW AND ORDER: CRIMINAL INTENT had its last episode Sunday June 26, 2011, thus ending a rather long running show which was part of a rather long running (and still running) franchise. Here is the whole list: Law and Order (1990-2010, 456 episodes), Law and Order: Criminal Intent (2001-2011, 195 episodes), Law and Order: LA (2010-2011, 22 episodes), Law and Order: SVU (1999-2011, 272 episodes, and still going), Law and Order: Trial by Jury (2005-2006, 13 episodes), Law and Order: UK (2009-2011, 26 episodes, and still going). 456 episodes is HUGE! Check out this list of long running TV shows. The list is only updated once a year This surprised my great nieces and nephews (so slow!) but did not surprise me.

I recall three episode of Law and Order:Criminal Intent that mentioned math. I am sure there are more.

In the episode Bright Boy there was a school for gifted children in math that tried to get 10 year olds to work on the Riemann Hypothesis. It was not clear if they wanted them to solve it as children (which seems absurd) or as adults later in life (not absurd but a real long shot). The reason I find it absurd that a 10 year old could solve RH is that cleverness and brilliance is not enough- you have to actually have learned a great deal of math, perhaps too much for a 10 years old to have learned. Problems that need lots of KNOWLEDGE really can't be solved by bright 10 years olds or amateurs, no matter how brilliant they are. (See here for a post of Lipton's about of when amateurs helped solve math problems.) Getting kids interested in math by having them work on RH is the opposite of using Math competitions. Lance and I discussed math competitions as a way to interest kids in math here. Which is better? Even if you get bright pre-high school students working on problems, having them work on RH would just lead to frustration. Are there math programs that have student work on real open problems? How about phony open problems (the mentor knows the answer ahead of time). Some REU's do this for College students, but is there anything like this for High School Students?

The episode Inert Dwarf involved a brilliant physicist who, for medical reasons, was in a wheelchair (modeled vaguely after Stephen Hawking). One point of interest: he had a password that was based on hard physics and hence uncrackable. Gee, I thought that you just need to make sure your password is (1) not a word in any language (2) long enough, and (3) used Upper Case (easy for ME), lower case, numbers, and punctuation symbols. Unless it was some sort of quantum system (the episode did not indicate this) I can't see how hard physics can make a password uncrackable.

In some episode this season (I forget which one) Goren (the detective) was given the following riddle by his psychologist: There are two doors and two guards. One of the doors leads to heave, the other to hell. One of the guards always tells the truth and one always lies. You get to ask one guard one question and then you must pick a door. Goren is supposed to some sort of genius who also knows a great deal of stuff so I'm surprised he didn't know it. In the last episode of the entire series, To the boy in the blue knit cap, he answers it correctly. I think that was supposed to be symbolic or meaningful or something, but I didn't see why. (Bad writing? I'm being dense?) (ADDED LATER- ACTUALLY GOREN ASKED THE PSYCHOLOGIST THE QUESTION WHICH MAKES MORE SENSE IN TERMS OF WHO-KNOWS-WHAT.)

Bright Boy and Inert Dwarf had the same problem that many TV shows have: If the real world fact do not make the plot work, the writers change the real world facts. Numb3rs did this with Math quite a lot.

FCRC 2011. Part 2 of... probably 2.

(A workshop on Coding, Complexity and Sparsity will be held at Ann Arbor, August 1-4, 2011. See this website.)

More thoughts on FCRC.

1. Russell Impagliazzo is one of the Luddites (spellcheck made me use a capital L) in the field (I'm another, and I know of one more person in Complexity who could be called a Luddite) who famously uses transparencies at talks. BUT, he has entered the 1990's- he gave a talk on PowerPoint (or something like it). (Spellcheck made me use two capital P's). I asked him why he made the change. The ability to SCAN IN his old transparencies was one of the keys. (Of course, he probably could have done that 10 years ago...) The talk was on his world view. I don't mean how he feels about the debt ceiling or Libya or Global Warm ning or the problems in FILL IN ANY COUNTRY THAT HAS PROBLEMS. I mean his worlds:
   1. Algorithmica: P=NP
   2. Algorithmica: NP ⊆ BQP. This was in a talk he gave at a workshop. Its in a link below but was not in his CCC talk.
   3. Heristica: P ≠ NP but NP problems are tractable on average for any samplable distribution.
   4. Pessiland: There are NP problems hard an average AND there are no one-way functions.
   5. Minicrypt: P ≠ NP, one-way functions exist, but public key crypt is impossible.
   6. Cryptomania: P ≠ NP, public key crypto is possible.
   For the CONTENT of his talk see Lance's blog entry. Blogs on his world are here and here. There was a workshop in 2009 on the worlds. You can actually see Russell talk about it, with transparencies, as a link from this page Russell's paper on the worlds was hard for me to find since its title is A personal view of Average Case Complexity which you can find on his web page. A POLL on which of Russell's works we live in would be interesting, but I leave that for someone else to do.
2. Les Valiant made the cover of CACM! I hope that eases the pain of no longer being the best theorist who had not won a Turing award.
3. Alan Borodin was the only one at STOC who had been to the first STOC (1969). I asked him if, at the time, he thought there would be a STOC 2011. He said that as a grad student at his first conference he thought more of it as being HIS first conference than STOCs first conference.
4. Several of my lunches were with people NOT going to STOC or CCC. A bunch of PLDI grad students asked me what he hot area in Theory was. I told them (1) Quantum is still strong, which surprised me, and (2) Algorithmic Game Theory seems hot now. Any other candidates for a short answer to this question if asked? Be prepared with an answer before the next FCRC.
5. I heard that one of the logistic problems was that different conferences gave out different stuff (bags, pens, paperweights. Paperweights?). I also heard some sniping How come that conference got so much better pens than we got?.
6. Jin Yi Cai gave a great talk at CCC about dichotomy for #CSP. Certain counting problems are in P and other ones are #CSP complete. Cai has managed to classify exactly which are which. I asked him about the CSP problem- is there any hope of a dichotomy theorem there. He said This talk is on Counting CSP. I asked him How Narrow are you?. He challenged me to read a 300 page paper in the field before accusing him of being narrow. Over lunch he gave me a better answer: Counting problems are hard in general so they have to be rather special to be in P, so classifying is doable. By contrast, CSP problems can be easy so its much harder to tell which are which.
7. The only ones at CCC that were at the first CCC were probably Fortnow, Allender, Gasarch, Selman, Homer. The founders of the conference were Book, Hartmanis, Mahaney, Selman, and Young. Selman is the only one who is still doing theory. (Book and Mahaney are deceased, Hartmanis and Young are retired.)
8. I don't bring a laptop to conference (I don't have one); however, I borrowed Marius Zimand laptop to catch up on some websites during one of the breaks. Then a talk came that I wanted to see and I could not pull myself away from the laptop. It can be addictive. I will never do that again. Other distractions such as doing math on paper I can break away from, but web surfing was hard to break away from. What are your experiences with this?

Blog Redesign

We redesigned the blog to use the newest Blogger features. This lets me not have to maintain the 2002 html code we had before and lets us have some new features like adding comments directly on the post page.

We, of course, kept the signature background color.

Creating an Email System at Cornell

Email celebrates its fortieth anniversary so let me tell the story of my job for three summers, and part-time during the academic year, while an undergrad at Cornell University: Creating an email system from scratch.

In my sophomore year (1982) I took an computer structure course. I had a heavy set of final exams and papers so I did the final program for this course early and turned it in the last day of class to the instructor, Steve Worona. In that class you could scale assignments and tests from 0.75 to 1.5 to make them count more or less. When I turned it in, Worona asked me why, if I'm turning it in a week early, did I scale it at 0.75? "You never give me A+'s on the programs and I didn't want to lower my grade."

That was perhaps my most obnoxious moment but it got me noticed and Worona, who worked for computer services, offered me a programming job. We would create a new email system for Cornell. Cornell had an email system written in some scripting language, slow and clunky. We wouldn't use any fancy high-level language, we would code directly in IBM 370 assembly language. We would do it all ourselves, user interface, database for storing messages, interactions with SMTP servers, etc to maximize efficiency. No small task which is why it took me nearly three years.

IBM Assembly language was quite bloated with instructions. There was a command called "Edit and Mark" that went through a range data making modifications based on some other data. This was a single assembly language instruction. We used to joke that there was a single instruction to do your taxes.

Cornell at the time was a gateway between BITNET ("Because It's Time NETwork", connecting about 30 universities in US and Europe) and a fledgling ARPANET, the precursor to the Internet. BITNET worked with files, ARPANET one line at a time so there was a special file-based Batch SMTP to transmit email between the two. The fun I had working this all out.

As a test bed, my email system was used in only one building, Day Hall, which held the university administration: President, Provost etc. Great pressure to make sure there were no bugs.

One day a company that helps get people green cards sent an email to everyone on BITNET. My first piece of spam.

As a side project I helped write an ARPANET interface into CUINFO, an early electronic information system at Cornell. That was pretty simple, we just used the Telnet interface into a different port. This is basically what HTTP does now. I could have invented the Web!

In my senior year I told Steve Worona that I was planning to go to graduate school in theoretical computer science.

"You really want to spend your life shaving log n factors off algorithms?"

"Yes I do." (But I never did, since I went into computational complexity)

"Well the world just lost a great programmer."

As soon as I left Cornell my email system was scrapped for a commercial product. C'est la vie!

I am conducting a NEW POLL on P vs NP

In 2002 I did a poll that appeared as SIGACT News Complexity Theory Column 36 on what people thought of P vs NP. See here.

That article is now linked to on Wikipedia and (much to my surprise) has come to be the AUTHORITY on what people were thinking then.

TEN years have passed! It is time to take the pulse of the community again. Hence I will ONCE AGAIN (!) be conducting a poll to appear in a SIGACT News Complexity Column.

SO- I would like you to email gasarch@cs.umd.edu (in LaTeX or plaintext) the answers to the questions below. (Comments to the blog will not be counted as answering the poll.) I would like to get this poll written this summer, so I will give a deadline of October 31, 2011. (I may extend this if I do not have enough responses.)

1. Do you think P=NP or not? You may give other answers as well.
2. When do you think it will be resolved?
3. What kinds of techniques do you think will be used?
4. Will the problem still be relevant given advances in algorithms and in SAT Solvers?
5. Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
6. Do I have your permission to print your response? I will do this for some people--- how many depends on how many answer the poll.
7. What is your highest degree in and where is it from? This information will be used for statistics only.

Theory Jobs 2011

The computer science job market never comes to a complete close. CI Fellows are still being decided, Oxford is just starting its search for an algorithms professor. But many jobs have settled so it is time for our annual list of who is going where. Many of the strong theory groups have hired this year, surely spurred on the by the competition for the new Simons Institute but still we have way too many theoretical computer scientists doing multiple postdocs or taking industrial or financial jobs.

For optimal crowdsourcing I created a Google spreadsheet that everyone can edit and for all to view. Do not add or modify the sheet unless you are sure a job has been offered and accepted. It may take some time for the embedded sheet below to update to the latest changes.

FCRC 2011. Part I of... maybe I, maybe more.

I do not log on at conferences so I came back to 400 emails. Exactly 400- not sure how I managed that. TODAY I am posting about a few things from FCRC, I may post more next week as I remember them.

1. CCC finally no longer has proceedings. Most conferences at FCRC did not have proceedings. ISCA, the International Symposiusm on Computer Architecture, still has proceedings. I asked someone from ISCA why they still have proceedings. They gave an answer which boils down to That's the way we've always done it. Also, ISCA has MONEY so they don't need to save money as well.
2. The best student paper award at STOC went to Analyzing Network Coding Gossip made Easy by Bernard Haeupler. Great Talk!
3. The best paper award went to Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs by It also might be a contender for longest title. A better title might have been Electrical Flows and Networks Flows. Great talk. Looks like a paper I can actually read and understand. Network flows is a well studied problem- one slide had over 30 references on it. (ADDED LATER: A helpful commenter pointed out that The Best Paper award was actually shared by the FLOWS paper and also by Subexpontential lower bounds for randomized pivoting rules for the simplex algorithm by Friedmann, Dueholm, Hansen, and Zwick. This seems to be unknown to thiswebsite.) (ADDED EVEN LATER- The page I just pointed to now DOES know about the two awards and has been updated.)
4. I skipped the talk on The Computational Complexity of Linear Optics by Aaronson and Arkhipov since I saw some version of it a while back. My mistake- talks I see twice I actually understand, and I heard it was an excellent talk. Going to Scott's webpage to make this post I spotted a paper on using Linear optics to prove the PERM is #P complete. THATS the paper I really want to read! Serendipity is alive and well.
5. Proof Complexity means two different things: (1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z, and (2) proving that certain formulas need exponential number of steps to prove they are not satisfiable. This talk tried to use a theorem (the Paris Harrington Ramsey Theory) that is not provable in Peano Arithmetic requires a long proof in some systems. They end up saying that if a version of Paris Harrington (that CAN be proven in PA) has a short proof then Pigeon hole principle has a short proof. This is rather odd- the only thing they can prove DIRECTLY requires long proofs is PHP, so everything reduces to it. The talk is here, the paper is here, for a writeup of the version of Large Ramsey they were talking about see here
6. Ryan Williams won the Best Paper award at CCC for this paper. Lance did an excellent blog on the result a while back here. (NOTE- the link to the paper seems to be down now. Hopefully it will come back up soon.)
   1. On his website it has next to the paper Will receive Best Paper award. Did he put that there when he submitted ASSUMING that he would win it? That doesn't sound right. Did he put it there when he found out he would win it? That doesn't sound right either-- being notified that you won it is the same as receiving it.
   2. I would like to think that he was inspired by my April Fools Day post of 2011 which said we should all go out and PROVE things instead of whining about barriers and oracles. Actually its the other way around- Ryan inspired the post when, at some DAGSTUHL, we were all saying what we can't prove and he said When do you think we will separate NL from PSPACE? I fell for it and said Not for a while at which point he reminded me that its already known. That inspired the post.
   3. Whenever a new result appears the question arises Did it use new techniques or a clever combination of old techniques. Or more egocentric Could I have proven that? For example, if Wiles proof of FLT is really the only way to do it then Gauss could not have done it. Ryan's proof looks like a really really clever combination of older results. This is NOT to downgrade it. And NO, I could not have done it. A better question: will it lead to MORE results? IS P vs NP just around the corner? No.
7. CCC 2012 is in Portugal. CCC 2013 is at Stanford co-located with STOC. CCC 2014 MIGHT be in Koyoto Japan. Is that a good idea? If there exists N people who CAN go if its in Japan and NOT otherwise but M people who normally go but now can't then if N and M are roughly the same or even if N is a bit bigger, than I think we should do it. Not sure what the real values of N and M are.
8. Some grad students I talked to think that CCC and/or FCRC should have an after-conference Survey Form to fill out about the conference so that they can improve things for next time. I agree!

New Complexity Vidcasts

The newly renamed Computational Complexity Channel features two new vidcasts Bill and I hosted last Thursday from San Jose.

Bill's Enigma

Interview with Ryan Williams

Talks I Missed

The Complexity conference comes to a close today and I head back to Chicago. I tend to go to few talks, preferring hallway conversations, but occasionally I hear about a few great talks that in retrospect I wish I attended.

The first STOC talk, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup. Simple hashing scheme that takes a random function of pieces of an input and XORs them together. Surprisingly this simple scheme is close to looking like a fully random hash function for a variety of purposes.

The last of Thursday's Complexity talks, Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef. An easy reduction from communication complexity to property testing gives a large number of new lower bounds for property testing based on known bounds for communication complexity.

Another FCRC comes to an end. Next year in New York (STOC) and Porto (Complexity).

An Update on Impagliazzo's Worlds

Russell Impagliazzo gave a talk at Complexity about his five worlds. We didn't know whether Heuristica and Algorithmica were different, i.e., whether if NP is easy on average then its also easy in the worst case. Russell gave an oracle relative to which where NP is easy on average but P ≠ NP. There are now relativized separations of all his worlds.

Russell announced that it was his first talk ever using a computer instead of transparencies. We gave a round of applause welcoming him to 1998. His talk consisted of some PowerPoint slides with black text on a generic white background and some very cute hand-drawn cartoons that he scanned in to his talk. Someone asked for animation. Maybe next decade.

In less than an hour new Stanford professor Ryan Williams gives the Complexity talk on his great result that NEXP not in ACC⁰. With no surprise, Ryan won the Complexity best paper award, the second-highest honor his paper has received.

The Longest Day

Tuesday at FCRC.

7 AM: A grad student at Northwestern administers my final exam at 9 AM Chicago time. He has my mobile number just in case but luckily I never get a call.

7:30: Saw Sampath Kannan in lobby. Says he has a sister who is married to a finance professor at Northwestern. I say, wow that's a coincidence, Ravi Kannan's sister also has a husband who is a finance professor at Northwestern. Then it hits me.

8:30: First STOC best paper winner talk by Madry gives better algorithm for approximating undirected max flow.

8:55: Skip second best paper talk to go across the hall to see Northwestern student Nima Haghpanah give his EC talk.

9:20: Back at STOC for the best student paper by Bernhard Haeupler. My favorite FCRC talk so far, a simple method for spreading "gossip" through a network with an analysis that uses a clever union bound that cannot possibly give tight results, yet it does.

9:43: Email saying 10 exams are being FedEx'd to me for grading. There are 12 people registered for the course.

11:30: Ravi Kannan's Knuth Prize lecture. Working in high dimensions can often do wonders for algorithms.

12:30: Electronic Commerce exec committee lunch to talk about location of EC 2012.

2:04: Email from student who thought the final was on Wednesday.

4:00: Find out the SIGACT Treasure can't make it to San Jose. Sends me material for the business meeting.

4:25: My only FCRC talk, an EC paper with Michele Budinich, an Italian student who couldn't make it to FCRC.

6:00: EC Business Meeting. Starts late so they barely get through introductions when I have to leave for

6:30: SIGACT Exec Comm dinner

8:15: Stop in at Complexity Reception

8:30: Stop in at EC Reception

9:00: STOC Business Meeting where I serve as emcee. I put all the slides here. Some highlights

• A little over 300 registrants at STOC
• Accepted 84 out of 304
• Poster session considered highly successful
• Give out Knuth Prize (Ravi Kannan) and Gödel Prize (Johan Hastad)
• FOCS 2011 in Palm Springs October 23-25. 
• ITCS 2012, now sponsored by SIGACT, January 8-10. Submission deadline August 7.
• SODA 2012 in Kyoto, January 17-19. Submission deadline July 5.
• STOC 2012 in New York, May 19-22.
• STOC 2013 will be in Palo Alto.
• Not much love for Salil Vadhan's proposal to require on-line archive version of paper on submission.

10:30: Meeting Ends. Talk with Paul Beame about timing of next Knuth Prize (FOCS 2012) and off to bed.

Another busy day today as STOC, EC and Complexity all have talks at the same time. But at least my jobs are done.

A Valiant Weekend

In my role as SIGACT chair, I got to attend the ACM Awards Banquet held at the beginning of FCRC in San Jose. I shared a table with Mitzenmacher who posted on the banquet earlier. Theory did well among the award winners but none so notably as the Turing Award, the "Nobel Prize of Computer Science", awarded to Leslie Valiant. Valiant, in his acceptance speech, gave a wonderful shout out to the STOC conference for helping him shape his research, or at least the STOC conferences back in the 70's when the theory community were still figuring out the right questions and models. A nice contrast to the ACM Press Release that focused on the connections to AI.

Last night, Valiant gave the Turing Award lecture at FCRC. His main thesis is that evolution is just an example of computational learning and we need to understand the computational process that led to the development of us in a relatively short period of time. I heard a similar talk he gave at Berkeley caused some consternation among the biologists who don't want to give anyone fodder that evolution might not be possible because it is too complex.

My take: Evolution has a significant random element and we need to condition that randomness on the fact that we exist. The biologists and computer scientists on Mars aren't asking these same questions about why they never came to be.

Partioning Students

One last Molly post for the end of the school year. Tomorrow is her birthday and I enter that moment I have been dreading for the past thirteen years: Two teenage daughters.

Molly's 7th Grade Science teacher wanted to break her class into groups of three to work on a particular project. Each person in the class was asked to list three people they wanted to work with and one person they didn't. The teacher would partition the class so everyone wanted to work with someone else in their group and the person they didn't want to work with was not in their group.

The next day the teacher she thought the partitioning should be easy but took her many hours. One student said she should just ask a computer to find the partitioning. Molly said she needed the right algorithm. When Molly told me about it that night and asked if I could help her figure out the algorithm. I said the problem was likely "NP-complete" (since it is a variation of Exact Cover) and would have to search all the 190 million different partitions of her class of 18 into groups of 3. OK, I probably said this to get out of thinking about an algorithm but maybe Molly got just a little more understanding of P versus NP.

Bill and I are at FCRC next week. Hope to see you there.

RaTLoCC (Ramsey Theory in...)

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity. The idea was to bring in researchers for all three areas (actually its more than three) and have them learn about each others areas.

1. During Szemeredi's talk he said I am not an expert on Ramsey Theory. He meant to say I am not an expert on Ramsey Numbers, e.g., the current upper and lower bounds on R(5).
2. An anagram of Banach-Tarski is Banach-Tarski Banach-Tarski.
3. Bertinoro hosted both RaTLoCC and SUBLINEAR (a workshop on ... SUBLINEAR things) at the same time. We had some shared activities with them. They were a younger, hipper crowd. Ronitt Rubinfeld (who was there) told me they had LESS women than they thought they would have- only 4. We had MORE women then we thought we would have- 2 (we had 0 last time).
4. There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b
5. One measure of how much you get out of a workshop or conference is how many papers you are inspired to read when you get back home (or perhaps how many pages-of-papers or theorems, or some measure.) With that in mind, here is a list of some of the papers that inspired me. (Slides and abstracts are posted at the workshop's website.)
   1. Szemeredi talked on Arithmetic progressions in sumsets. Here is a sample theorem. Throughout A is a subset of {1,...,n} and n is large. A+A is the set of all sums of two elements of A. LA is A+A+...+A (L times). Sample theorem: For all C there exists c such that if |LA| > Cn then LA has a cn-AP (an arithmetic progression of length cn.) These theorems look HARD but it inspires me to read some papers on Alon's website on this topic, and also my own writeup of sum-product theorems (He used C and c in his talk- though some of them looked the same.)
   2. Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is L-List colorable if there is a way to assign each vertex L colors so that there IS a coloring of the graph where each vertex uses on of the colors assigned to it. Let G be the unit distance graph in the plane: vertices are points in the plane and two points are connected if they are distance one apart. This graph is known to be 7 colorable, known to NOT be 3-colorable. All else is open. Noga talked about his proof (co-author Kostochka) that G is NOT list-s-colorable for any s. The paper is on his website and I am INSPIRED to read it. (ADDED LATER- THE DEFINITION I GAVE ABOVE IS NOT CORRECT. SEE COMMENT BELOW.)
   3. Peter Cholak talked on Reverse Mathematics of Ramsey Theory. Reverse mathematics is a field where they have set up several axiom systems for mathematics (in a hierarchy) and, for MANY theorems of math, they know EXACTLY which system is needed. Infinite Ramsey Theory for PAIRS seems to be stubborn- it is not in any of the usual systems. (formally: RCA cannot prove it, but ACA is too much). It is provably DIFFERENT from Infinite Ramsey for TRIPLETS (which is equivalent to the theorem for 4-tuples, 5-tuples, etc, and for all of them ACA is exact.) My question: when I prove Ramsey for triples I do not feel the earth move or think MY GOODNESS- THAT STEP WAS NONCONSTRUCTIVE!!!! or anything else that is different from Ramsey for pairs. They told me that there IS a proof of Ramsey for pairs that, once you see it, you DO NOT know how to generalize to triples. I may try to look into this. I may not. The paper is at Peter Cholak's webpage and is titled On the strength of Ramsey's theorem for pairs. (co-authored by Jockusch and Slaman)
   4. David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is double-exp but the lower bound is single-exp. They made some progress on this, but the upper and lower bounds are still, pretty much, what they were. Still- proofs look very interesting. Progress here is unpredictable--- Conlon said that the problem could be solved next week or next month or not for one hundred years. Also, the proofs are clever- so Erdos COULD HAVE done them. (As opposed to results that use mathematics unknown to anyone in Math at the time.) I am INSPIRED to read this paper by Conlon, Fox, and Sudakov. The case of 3-hypergraph is interesting because, if the lower bound can be gotten up to double exp then for k-hypergraphs we will know that upper and lower bounds are roughly tower(k-1). (Uses the STEPPING UP Lemma.)
   5. Swastik Kopparty talked on The complexity of computing roots and residuosity in finite fields. Say you are in a ints mod p and you want to know whether x is a cube root or not by a constant depth circuit. This will take exp number of gates. Framework is the same as the Parity not in ACC_0 proof, but requires lots more math. MIGHT want to read it. MIGHT be too hard.
   6. Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in Rⁿ. IS it the case that, for all c there exists a finite set T in R^m. (m \ge n) such that, no matter how you c-color T there will be a CONGRUENT copy of S? The unit line has this property. If so then S is RAMSEY. It is known that if S is Ramsey then S lies on the surface of some (many dim) sphere. The Main conjecture is that the converse is true. NO says Imre! He has an alternative conjecture here. This paper I am INSPIRED to read.
   7. Jan-Christoph Schlage-Puchta (that is one person) gave an application of VDW's theorem to Completely Multiplicative Automatic Functions This one I NEED to read to put in my book on VDW's theorem. Its here
6. The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the no-specialist could at least here that and then TOLD YOU WHY THEY CARE (even if you don't care you should know why they care) and TOLD YOU SOMETHING ABOUT THE TECHNIQUES. Not all of the talks did this. Also, the best talks were on BLACKBOARD- it forces you to go slower. Not possible at STOC/FOCS etc since the audience is too big, but quite possible here. Only drawback- can't put blackboard talks on the web so easily (though you can if you videotape).
7. The youngest participant: James Pinkerton, my High School Student, gave his talk on Duplicator Spoiler Games that go on an ordinal number of moves. The talk was AWESOME! Before hand he was not scared. He said Whats the worst they can do? Throw red and blue tomatoes at me?
8. One of the people there wore a T-shirt that said Stand back, I'm doing SCIENCE! that had a picture (stick figure really) of a scientists with a test tube. He wore it two days in a row. I commented: Nonconstructive proof that you are a supernerd. Either (1) You wore the same T-shirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy T-shirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.

75 Years of Computer Science

As Lipton and Felten note, today is the 75th anniversary of Turing's On Computable Numbers, With an Application to The Entscheidungsproblem, the seminal paper of seminal papers in computer science.

If you read any part of it, read Section 9, his justification of why the Turing Machine model captures computation, an argument that still resonates today.

No attempt has yet been made to show that the “computable” numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is “What are the possible processes which can be carried out in computing a number?”

The arguments which I shall use are of three kinds.

1. A direct appeal to intuition.
2. A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).
3. Giving examples of large classes of numbers which are computable.

Once it is granted that computable numbers are all “computable” several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert function calculus is provable, then the determination can be carried out by a machine.

Cell Phones versus Drunk Driving

Most of you are familiar with the research that using a cell phone is just as dangerous as driving drunk.

Method: We used a high-fidelity driving simulator to compare the performance of cell phone drivers with drivers who were intoxicated from ethanol (i.e., blood alcohol concentration at 0.08% weight/volume). Results: When drivers were conversing on either a handheld or hands-free cell phone, their braking reactions were delayed and they were involved in more traffic accidents than when they were not conversing on a cell phone. By contrast, when drivers were intoxicated from ethanol they exhibited a more aggressive driving style, following closer to the vehicle immediately in front of them and applying more force while braking. Conclusion: When driving conditions and time on task were controlled for, the impairments associated with using a cell phone while driving can be as profound as those associated with driving while drunk

That and similar research has led to bans on hand-held (though usually not hands-free) cell phone use in many locations. Statistics are hard to come by but there are more alcohol-related accidents and many more alcohol-related deaths than those due to cell phones. Yet there are far more people talking on cell phones than driving drunk. This contradiction bugged me. What's going on?

Unlike using a cell phone, drunk driving is not a binary event. It's not that you are either drunk or you aren't. There are degrees based on the blood alcohol level. The real dangerous drivers are those way over the legal limit. Driving at the legal limit (0.08% in Illinois) isn't that dangerous or the limit would be lower.

When we hear that using cell phones are just as dangerous as driving drunk, we think, wow, cell phones are very dangerous. But our thoughts of the dangers of drunk driving is not at the level of drunkedness that are compared to cell phones.

Driving at the legal limit and on your cell phone are only mildly more dangerous than driving sober and distraction free. I'm not recommending that you drink or use your cell phones while you drive, you are certainly safer without doing so. But you should also be careful about reports about the dangers of activities and be sure the comparisons are correct. 

Is Computer Science Cool Again?

Back in 2005 I worried about loss of excitement about computer science among America's youth.

Today computers have become almost as commonplace as televisions and teens use them for a variety of tasks, including researching on the web, communication via email, instant messaging and blogging, and writing papers, all without an inkling of how to program. Computers have become a commodity and they don't see an additional value in knowing how and why they work any more than they need to know physics to drive their cars.

Yesterday IBM's David Ferrucci gave a talk at Northwestern on the challenges of creating Watson to play Jeopardy. The large lecture room was packed mostly with undergrads. Ferrucci didn't disappoint showing the challenges of Watson with lots of examples keeping the talk not too technical. Ferrucci will give a similar talk as an FCRC plenary speaker or you can watch a short version here.

My 12-year old daughter Molly came and enjoyed the talk and insisted on meeting Ferrucci afterwards just to tell him how cool Watson was.

The number of CS majors has grown dramatically in recent years at Northwestern and other universities. Bank of America runs ads on their ATMs that understands peoples checks ("How do they do that?") and Ford on how its Focus parks itself. And our local high school next year is teaching computer science again.

Håstad to receive the 2011 Gödel Prize

The 2011 Gödel Prize is awarded to Johan T. Håstad for his paper:

Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001.

Håstad is the fourth person to win the prize twice (after Shafi Goldwasser, Mario Szegedy and Sanjeev Arora). He won the 1994 Gödel Prize for his switching lemma and tight bounds on parity for low-depth circuits.

The official citation:

This is a landmark paper in computational complexity, specifically, the study of approximation properties of NP-hard problems. It improves on the PCP Theorem (recognized in a previous prize in 2001) to give novel probabilistic verifiers that can check membership proofs for NP languages while reading very few bits in them — as little as 3 bits. The existence of such verifiers implies that existing approximation algorithms for several problems such as MAX-3SAT cannot be improved if P is different from NP. In other words, there is a "threshold" approximation ratio which is possible to achieve in polynomial time, but improving upon which is NP-hard. Before this paper such "optimal" inapproximability results seemed beyond reach. The Fourier analytic techniques introduced in this paper have been adapted in dozens of other works, and are now taught in graduate courses in computational complexity. They also directly influenced subsequent work, such as the formulation of the unique games conjecture for proving further optimal inapproximability results, and lower bounds for geometric embeddings of metric spaces.

On demand Publishing (guest post)

Cambridge Press (and others) offers PRINT-ON-DEMAND for some books. This is a guest post by Lauren Cowles from Cambridge Books about this, and then my comments on her comments, and then her comments on my comments. We stop there or else this could go on forever (OR we could make each block half the size of the prior block...)

LAUREN:

Print on demand is expanding rapidly all over the publishing industry. It's a way to keep books available if not forever at least much longer than they otherwise would be. This benefits people who want the books and the publishers who want to sell them.

The main factors are: Printing technology is now generally computer-driven, like everything else. There is no longer any need to set up film (or plates) to print from; many printing presses work from something that's essentially a fast and very high resolution laser printer. Therefore there is less economy of scale because there is much less in the way of set-up cost.

It is still cheaper to print several hundred books than to print them one at a time, but not nearly as much cheaper as you might think. So for many books there is now a tradeoff between the cost of the warehouse space and the unit cost. Also, of course, publishers are not spending money on books they might not sell. When sales drop below the point at which this tradeoff favors a conventional printing, we can often switch a book to being printed on demand simply by emailing the printer -- most of the printers we use now do both "conventional" printing and print on demand.

To get a print on demand book, all a customer has to do is order it in the normal way. The process is also so fast now that the customer normally has to wait only a few days more than if the book were in stock on the shelves.

BILL:

1. Will there be a time when there is NO cost diff between ordering one book and ordering in bulk? Will book companies only print on-demand?
2. Will Kindle and similar devices make print-on-demand a short-lived technology?
3. What does print-on-demand and kindle mean for the future of book publishers?
4. If these are cheap enough will they undercut the used-book market? If Kindle is the future will there no longer be such a think as a used book? (Molly Fortnow's daughter will ask Whats a used book mommy?.)
5. For academic books I am very happy that they will live on forever via either on-demand or kindle. Sometimes out-of-print math books are either impossible to find or are too expensive.
6. Will the notion of a rare book be obsolete?

LAUREN:

1. I doubt that the unit costs for print-on-demand will ever be cheaper than the unit costs for 500+ copies. But the PoD cost is low enough now that companies can make the choice for every book, and change that choice later in the book's lifetime. There already exist companies that only do print on demand (Lulu, for example).
2. Again, I doubt it.
3. Print on demand means we can keep things in print longer. What Kindle means is anybody's guess. Here in the publishing industry we are living in interesting times.
4. If fewer new books get printed, there may be a vogue for the old printed object... The used textbook market may be affected. I think the big textbook publishers have been trying for ages to find an electronic textbook model that will catch on, so that they can sell the electronic thing over and over at some similar-to-used-book price rather than sell the big expensive textbook once (effectively, directly into the used book market). I like to think people are keeping their Cambridge books so the used book question doesn't arise. (NOTE FROM BILL: I tell my students that they can buy ANY edition of the book for the course, they do not need to get the latest one. NOTE FROM BILL: Cambridge Press mostly does high level monographs which people are less likely to sell used.)
5. Cambridge Press has brought hundreds of books back into print now that we can afford to reprint them (eg Beck and Chen, Irregularities of Distribution).
6. In the sense of hard-to-find, yes. Google books has been scanning a lot of out-of-copyright books and making them available electronically. Cambridge U Press is doing something similar: we have been scanning classic books in the University Library and offering them as print-on-demand (eg Gibbs, Elementary Principles of Statistical Mechanics). The original of this from 1902 is still rare.

President Regan (not Reagan)

Whose name (in firstname lastname form) appeared most often in the pages of Newsweek in the 1970's? Is it---?

1. Richard Nixon
2. Gerald Ford
3. Jimmy Carter
4. Ken Regan.

The answer could well be... Ken Regan. Ken Regan is a photographer. Many pictures in Newsweek had Photo credit Ken Regan in tiny letters up the side.

I was emailed an invitation to an event titled Ken Regan Presents Bob Dylan, and I wondered if I was emailed this because

1. I have the largest collection of Bob Dylan satires in the world .
2. I am friends with Ken Regan who, for all I know, in addition to being a computer scientist, chess player, language expert, blogger, choir singer, and would-be composer and writer, could also be a photographer.
3. This email went to EVERYONE,
4. This email was spam (not clear how this differs from the last choice).

I emailed Complexity-Ken who told me (1) there is a photographer Ken Regan, and (2) Complexity-Ken-Regan does not equal Photographer-Ken-Regan. Sharing a name with a photographer seems okay. Its better than sharing a name with a vicious murderer, or worse, a Congressman.

Photographer-Ken has one thing going for him: he registered the domain www.kenregan.com. Thus Complexity-Ken has forever lost the chance to emulate www.fortnow.com or www.scottaaronson.com. Still, Complexity-Ken often pushes the domain into second place in Google searches, and simply Google Regan without any firstname at all turns him up on the first page of hits. Why is that? It may be a prerogative of being both a computer scientist and a blogger who tends to make a lot of comments under his real name, with his name (or handle KWRegan) linking back to his site. Perhaps Google regards this as legitimate self-citation, ticking up his page's "authority" score for each one?

Complexity-Ken's wife Debbie Howe is shares a name with the originator of the popular children's book series Bunnicula. However, Complexity-Ken-Wife-Debbie took Complexty-Ken's surname as her middle name and has used the resulting full name in some publications, which Google Deborah Regan Howe finds. More generally, preserving the Google trail has become a factor in wives' keeping their maiden names after marriage. I suspect its a bigger factor than feminism or being-your-own-person or other very good reasons. (I posted on this already here.)

FCRC Early Registration May 16

One final reminder for the FCRC Conference. Early registration deadline is this Monday, May 16.

There are a number of events at FCRC of interest to our readers: STOC, Complexity, Electronic Commerce, SPAA, PODC and Foundations of Mobile Computing. Plenary talks include Leslie Valiant's Turing Award lecture, Ravi Kannan's Knuth Prize lecture and David Ferrucci (the guy who led the Watson Jeopardy project).

No STOC tutorials this year, but EC has some interesting tutorials and workshops on topics including Bayesian Mechanism Design, Social Computing, Network Economics, Implementation Theory and measuring advertising effectiveness. You can still apply for one of four free student registrations for EC.

And last and definitely least: Bill and I will both be there. Maybe we'll do another Complexity Vidcast. Maybe you'll be on it.

Those Happy Samoans

Below is a post I wrote in 2009 but for some reason never made it to this blog. But I had better post it now because, as I found out via Tony Wirth, Samoa is moving across the international date line, 24 hours into the future. That should make Hawaii the last place on Earth to end the day, making conference deadlines an hour earlier.

So are the Samoans losing a hour to submit their papers or are they gaining twenty-three?

Update 12/28/11: Western Samoa is skipping this Friday to make the switch. American Samoa is not making the switch and will be the last place on Earth to end the day, an hour after Hawaii.

---

The deadline for ICALP 2009 was February 10th at 12:30 PM in Greece where the conference will be held. Did you sleep late and miss it? Why not have the deadline in late afternoon so people can keep working on their papers?

But in fact the deadline was Tuesday. At least while it was Tuesday anywhere in the world. So ICALP waits until the small country of Samoa approaches midnight before making its papers due. So the Greeks get all morning Wednesday. The New Zealanders have all day Wednesday until 11:30 PM. With Daylight Savings Time, the Kiwis are a full day ahead of the Samoans.

Nothing against the fine citizens of Samoa but it is not a hotbed of theoretical computer science. So it still seems strange to list the submission deadline as "February 10, 2009, (23:30 GMT-11)" in a time zone from which they will likely get no submissions instead of just giving the deadline as February 11, 2009 (10:30 GMT).

Not all conferences follow the Samoan rule. Complexity deadline is midnight Eastern on Friday. At EC we used Midnight GMT on Monday and we received a few complaints from people in the US. I just didn't want to have to be up at 4:30 AM Chicago time making sure the submission server wasn't crashing.

The NSF has a policy of submission of 5 PM in the submitter's time zone. So perhaps conferences could have a deadline of midnight in the place the submitter lives. This would give those Samoans the extra time they so richly deserve.

How has the STRUCTURES, OH- I mean CCC Conference changed: Lets look at the Call For Papers

Complexity theory has changed over the years. How to really track these things? One way is to look at the list of topics on the Call For papers for the CCC conference (called STRUCTURES until the name changed, another sign of change). Below I include pointers to the call for papers from 1986, 1997, and 2008. I also include the list of topics and I comment on them.

1. The 1986 CCC (then called STRUCTURES) call for papers (third page is best view) had this list:
   1. Structure of Complexity Classes. (What does this even mean?)
   2. Properties of NP-complete sets.
   3. Relations between Complexity Classes. (I wish we had more.)
   4. Resource-bounded Reducibilities.
   5. Theory of Relativizations. (I think this means oracles.)
   6. Recursion Theoretic Aspects. (To general.)
   7. Kolmogorov complexity and randomness.
   8. Crypto-complexity.
   9. Applications of Finite Model Theory.
   10. Independence Results. (I wish we had more.)
2. The 1997 CCC call for papers had this list:
   1. Structure of Complexity Classes. (I still do not know what this means.)
   2. Resource-bounded Reducibilities.
   3. Interactive Proof Systems.
   4. Computational Randomness.
   5. Circuits and other Concrete Computational Models.
   6. Proof Complexity
   7. Communication Complexity.
   8. Theory of Relativizations. (I'm surprised this is still here.)
   9. Complexity and Logic. (To general.)
   10. Kolmogorov complexity.
   11. Cryptographic complexity. (Is this different from Crypto-complexity?)
   12. Complexity and Learning. (Has there ever been a paper on this at CCC?) (ADDED LATER- Rocco found quite a few and then I generated a list which I am sure is incomplete here.
3. The 2008 call for papers had this list:
   1. Structure of Complexity Classes (Do they keep this topic for traditions sake?)
   2. Reducibilities and Completeness.
   3. Proof Complexity.
   4. Interactive and Probabilistic Proof Systems.
   5. Inapproximability. (I'm surprised this wasn't on the 1997 list.)
   6. Complexity in other Concrete Computational Models. (Other than what?)
   7. Kolmogorov complexity.
   8. Quantum Complexity. (Not sure when it first entered the list, though it was on the 2002 CFP.)
   9. Circuits Complexity.
   10. Communication Complexity.
   11. Complexity and Logic. (Too general.)
   12. Pseudorandomness and derandomization. (How does this differ from Computational Randomness?)
   13. Average case complexity. (I'm surprised it was not on the 1997 list.)
   14. Complexity and Learning. (What is this still doing on the list?)
   15. Cryptographic complexity.

NOTES:

1. The only topics on all three lists: Reducibilities, Kolmogorov Complexity, Cryptographic complexity. Maybe randomness. Depending on how you count `Logic and Complexity' maybe finite model theory.
2. I was surprised there was NOTHING on concrete models of complexity in 1986. Furst-Saxe-Sipser was already known (1981 FOCS, 1984 MST) so I would think Circuits would be of interest. Realize that FSS was first presented as an attempt to get an oracle that separates PH from PSPACE (which later succeeded- Yao and Hastad). You can feel the paradigm shifting and circuits becoming important unto themselves as opposed to servicing recursion-theoretic complexity.
3. Perhaps I shouldn't be surprised- the list of topics may lag behind the reality. It takes a few years to catch up.
4. The number-of-topics has grown from 10 to 12 to 15. At this rate...
5. The change to the topics seems to have come WITHOUT an old guard resisting the change. Why was this? TCS is young enough that people could change fields? TCS is young enough to not have an old guard?

Forty Years of P v NP

In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard.

The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory. 

And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history.

Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today.

How important is Teaching Experience on the job market (guest post)

( Annoucements: New York Theory day May 13 and UMCP Theory Postdoc opening. )

This is an anon guest blogger. Even we don't know who this is! He or she emailed us about the topic and we invited him or her to do a guest blog on it. I have added my comments on it as well.

I'm a PhD from a Tier-I research university (about to start a postdoc at an institution of similar caliber). Outside of begin a TA (i.e., grading), I have never taught a course, and I have received conflicting advice about the importance of teaching experience on the academic job market. From some people I have heard that having plenty of teaching experience is a plus on the job market. From others I have heard that teaching can only take away from time better spent doing research. I have even heard that teaching more than a couple of courses on one's own is potentially harmful to a CV. The job market being what it is, I am planning on applying to jobs at universities and colleges all across the spectrum. Would your readers be kind enough to share their thoughts on this issue?

How much teaching experience should one have when applying for: TT jobs at Tier-I research universities; TT jobs at Tier-II research universities (please interpret "Tiers" liberally; I don't mean for this question to spark any debates about specific places); teaching posts at research universities; teaching posts at liberal arts colleges. (For instance, does someone with an excellent research background, but no teaching experience not stand a chance of getting a job at a liberal arts college? Thoughts?

Here are Bill's comments:

1. I find the notion that having lots of teaching on your CV as a negative to be absurd. When looking at your research they will look at How many papers have you published? (and conferences, etc.) For a job at a research university there are four possibilities that collapse to two possibilities (This is an exaggeration, see next point.)
   1. If you teach a lot and do not have a lot of papers they will say Not enough papers, without caring why.
   2. If you teach a lot and have lots of papers they will say Enough papers, without caring why.
   3. If you teach very little do not have enough papers they will say Not Enough papers, without caring why.
   4. If you teach very little and have lots of papers they will say Enough papers, without caring why.
2. If there is evidence that you are a good teacher this will be seen positively. How much they care will may vary tremendously, not just from school to school, but even within a school, from person to person. But to get a job at a research university you have to have done lots of research. Other things- teaching, service, patents, blogs, willingness to give faculty who can't drive rides home, are all secondary. Still, they can be important as tie breakers.
3. Liberal arts colleges I am less familiar with so I welcome comments on this. You raise a good hypothetical question- if a BRILLIANT researcher who was a TERRIBLE teacher (there are such people!) were to apply to liberals arts college, would they get a job?

Those are just my opinions. What do you think?

Don't Blame the Tech

Short Announcements: STOC Poster Submission Deadline is Monday. Jaime Morgenstern set up a google groups page for students to find roommates for STOC, FCRC and other theory conferences, "particularly useful for women and students at smaller departments."

---

I usually agree with Moshe Vardi when he writes about conferences but not so much on his latest CACM editorial Technology Has Social Consequences. Moshe blames electronic program committee software for declining ethics of program committee members, increased PC service and more farming out papers to junior reviewers.

Moshe has a rosy memory of the past. I knew more than one PC member back in the day that would work on a paper submitted to a conference. The slowness of paper dissemination back then hid it better. Junior people and students always served as subreviewers, one professor even tried to run a course on reviewing FOCS papers.

What's changed is that computer science has grown and specialized. We have more conferences and each conference needs an ever larger PC to cover all the specialized subfields. Program committees have become unwieldy with ethics and quality reviews harder to enforce. These problems won't be avoided whether having an electronic or physical meeting. A strong PC chair makes more of a difference than the venue of a meeting.

Ravi Kannan wins the Knuth Prize

Ravi Kannan will receive the 2011 Knuth Prize for his algorithmic work, including approximating volumes of high-dimensional convex objects, computing the Frobenius number and finding low-rank approximations to matrices. The techniques Kannan helped develop, including sampling via random walks and the weak regularity lemma, have applications across the algorithmic spectrum.

Kannan will receive his award at the STOC conference at this year's FCRC meeting the week of June 5th. He will give the Knuth Prize lecture as an FCRC plenary speaker. With Les Valiant's Turing Award lecture on Sunday and Ravi Kannan's Knuth Prize lecture Tuesday, not to mention STOC (with the first STOC poster session), Complexity, EC and many other conferences, San Jose is the place to be in June. Early registration deadline is May 16.