Possibly Recruits for the Polymath Primes Project

In the book The Man who Mistook his Wife for a Hat and other Clinical Tales by Oliver Sacks there is a true story about two twin brothers (John and Michael), both autistic, who have the following properties (Sentences in italics are direct quotes from the books.)

1. They cannot do simple addition or subtraction with any accuracy, and cannot even comprehend what multiplication and division mean. (page 197)
2. John would say a number--- a six figure number. Michael would catch the number, nod, smile and savour it. (page 201). Oliver Sacks wrote down their numbers and, following a hunch, found out they were all primes.
3. Oliver Sacks joined them and spoke an 8-digit prime. There was a long pause--- it was the longest I had ever known them to make, it must have lasted half a minute or more---- and then suddenly, simultaneously, they both broke into smiles.... An hour later they were swapping 20 figure primes, at least I assume this was so as I had no way of checking. (Page 203. Note that this happened in 1966.)

This raises several questions.

1. How are they doing it? These brothers were unable to tell Oliver Sacks. However, in other essays in books when Oliver Sacks gets to talk to savants that are not autistic they also can't explain how they do it.
2. Since these twins do not know basic arithmetic they are not using the Sieve of Eratosthenes. Nor are they using the AKS Primality algorithm to test their primes. I speculate that they are using a different model of computation then we work with. One is tempted to say Neural Nets! or Analog Computers, but I suspect it is something completely unfamiliar to us.
3. If we could figure out what they are doing could it lead to a solution to the polymath problem on finding primes? Alas no, since I doubt what they are doing would fit into what we are doing.
4. Prediction:
   1. Someone will devise a model of Savant Computing. The Polymath problem referred to above will be in SAVANT-P, giving the field a push (not as big a push as FACTORING IN QP gave Quantum).
   2. People will come up with 1 or 2 more real problems in SAVANT-P, and dozens of complexity classes and theorems about SAVANT computing.
   3. There will be some results in lower bounds on classical models (which my then may include quantum) that are claimed to be easy to prove with SAVANT concepts but not otherwise. People will argue about is it really easier?.
   4. I will write a blog Is Savant the next Quantum?.
5. Could the twins get a job at the NSA? Today no, since they need primes far bigger than 20 digits. But back in 1966...

Announcing a New Blog: Silent Glen Speaks

There is another Theory Blogger: Silent Glen. How can a blogger by silent? Sounds like a contradiction in terms! Hope its not a contradiction since she is already on our blogroll.

I emailed her the offer to annouce her blog (already annouced by ***SORELLE*** and Jeff Erikson and Livejournal) and to email me a statement about why she blogs, that I would post. She ended up emailing me and then posting her WHY I BLOG note on her own blog. Rather than waste electrons reproducing what she said, just go HERE.

In her first blog she asked for advice on being the lone theorists at a University (she just started). I gave her some advice and so did others. It was all good advice, though some of it was contradictory. Rather than restate it, I'll just point you HERE.

This entry is mostly two pointers to other blogs. This raises a question in a different context: In this age of easy access is it worth reprinting something? I have sometimes in my SIGACT NEWS book review column had a review that was Reprinted with permission. If the source I am reprinting from is online, and if the reader is reading SIGACT NEWS online, I could just point to it. We are not quite there yet, but there will come a time when Reprinted with permission will be silly. ~ ~

Fashionable Research

A student asks "How do you survive in the academic world if what you want to do is not fashionable?"

You shouldn't necessarily focus your research on the currently hot topic. Many people will flock to this area so you'll have considerable competition. And while today maybe you'll see many papers in area X being accepted to the big conferences this year, topics can get cold quickly and so will you.

But what about the other extreme, where you do research in an area of very small interest because you have a strong passion for it. Unless you get very lucky and this area goes hot in the future, you'll be giving up any chance of larger fame or fortune. But if you do good work in this area, you can use your passion to sell this area in a job talk and get strong letters from those few senior researchers in the field happy to promote people in their field. So often you can get a job at a reasonable university and spend your life working on what you love. Is that so bad?

Research always comes to passion and ability and you have love what you do and be good at it, no matter the topic. If you don't enjoy your research, you can usually make much more money doing something else you don't enjoy.

Ambiguity

I recently heard or read the following phrases.

1. former cop killer
2. ideal compromiser
3. even prime numbers have their uses

In each case it was ambiguous. The first two intentionally and the last one by accident.

1. On the TV show MONK the main character, Adrian Monk, is a former cop. There was an episode where someone tried to shoot him. The shooter was called A former cop killer. The show played the ambiguity for laughs- did they mean someone who used to shoot cops or someone who shoots former cops? What would be the proper way to write that? former-cop killer would work, though I am not sure the English language allows hyphens.
2. On the TV show BETTER OFF TED a character was asked to compromise her ideals. Her friend Ted said (I may be paraphrasing) Don't make her into an ideal compromiser!. This was also played for laughs--- did he mean that she should not compromise her ideals, or did she mean she should not get really good at compromising? I do not know how to disambiguate that.
3. In the book PRIME OBSESSION (about the Riemann Hypothesis- both the math and the history) they make the point that pure math can have surprising applications. I was reading this book to my darling (I often read her math books to help her fall asleep) and I read Even prime numbers have their uses. She perked up and said Are they saying that 2 is useful? Well, I suppose it is since you can't get from 1 to 3 without it. I think she was sleep talking. The author should have just said Prime numbers have their uses, but is there some way to keep the phrase as he has it and disambiguate it? Perhaps Even the prime numbers have their uses; however, that still sounds odd since it sounds like you are saying of course the composites are useful but who would have thought the primes were! which is not what he is trying to convey. Better to just say Even Number Theory has its uses. Hmmm- that might be interpreted as the theory of even numbers...

The Mystique of the Open Problem

The story goes that Andrew Wiles dreamt of proving Fermat's last theorem when he was a kid. No surprise since all of us math-loving kids dreamed of solving this famous problem. We certainly talked about it much longer than the more important Fermat's Little Theorem which already had a proof. Now my kids have never heard of Fermat's last theorem. Why should they? Nothing there left to dream there.

It is the challenges that inspire. It was much more interesting to go to the moon in the 60's than it is today. Computational complexity is blessed with such a great challenge, one of extreme theoretical and practical importance, that brings needed attention to our small domain. 

My CACM article on P v. NP has proven very popular in great part because of the excitement of the unknown. In that article I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." For much as I'd like to see a proof that P ≠ NP, I would also hate to lose that mystique. Who would read an article on the status of P v. NP if the status was "proven 15 years ago"?

Let me note one correction in the article pointed out by Andrew Appel: It was Armin Haken, and not his father Wolfgang, that showed that there are no short resolutions proofs for the pigeon hole principle.

Update: Eric Allender has his own A Status Report on the P versus NP Question appearing in the Advances in Computing series. We should have coordinated titles.

Models versus Proofs

The STOC Call for Papers (deadline November 5th) and FOCS Program including the 50th Celebration are now available (FOCS registration info coming soon). Also a reminder that the Beijing Innovations in Computer Science conference submission deadline is Tuesday. 

On a not entirely unrelated note, even if you have no interest in economics, be sure and read Noam Nisan's post on the differences in the theoretical CS and Econ communities.

Economists and game theorists take their models much more seriously and literally than computer scientists do. While an economists’ model should correspond to some real phenomena, a CS model should correspond to a host of unknown future situations. A CS reader is more willing to take the leap of imagination between the model as stated and various unknown future scenarios. In compensation, the CS reader expects a take-away that transcends the model, often found in the form of mathematical depth. An economics reader is much more skeptical of a model and demands specific justification, but on the other hand, mathematical depth is not seen as a feature but rather as a nuisance to be buried in the appendix.

I made a similar point in a question during the panel session at the Cornell Workshop last week, that proofs dominate most CS theory talks but Econ theory talks rarely mention them. The micro-economists quickly claimed they care just as much about proofs but Noam does capture a major difference of emphasis between our communities. But I disagree with Noam on the importance of the proof over the model.

Our focus on proofs is not inherent in theoretical computer science. CS theory grew initially out of the logic community and initially focused more on models and results than deeper mathematical proofs in the first couple of decades of the field. As the field started drawing more diverse mathematicians (particularly with the combinatorialists in the 80's) we slowly started to see a trend towards using proofs as a major yardstick in measuring the quality of a paper. Our conference systems exacerbates this process: With so many strong submissions to major conferences, it's easier to find faults in new models than in deep mathematical proofs.

We have more sophisticated mathematical techniques in TCS because we reward these techniques causing a feed-back loop. Doesn't make us any more forward looking just less relevant. 

My talk at the workshop described a new model for handling complexity in games, and described a theorem without giving a proof. The actual proof (with Rahul Santhanam, write-up in progress) is messy but not technically deep. Muthu called the presentation a "quintessential" theory talk, a code-word for "old-fashioned".  I'll take that as a compliment.

Panos Ipeirotis and Rakesh Vohra also have takes on the difference between econ and CS.

An apology for Turing may be in the works

Recall that Alan Turing

1. helped Britain win WW II with his breaking the enigma,
2. was a brilliant mathematician who was one of the founders of our field
3. was prosecuted for being a homosexual by the British Government,
4. was forced to take chemicals to cure him of it,
5. committed suicide (almost surely because of the drugs and prosecution),

There is now a movement in England to have posthumous apology to Alan Turing (see here) by the British Government. I suspect that most of the readers of this blog would agree with such. I do also. But see next paragraph.

Does one need to help the war effort and be a brilliant mathematician to get the apology? I think they should lower the standard to the following: you need to have either helped the war effort or be a brilliant mathematician to get the apology. Or how about anyone who was persecuted under those laws? Should Britain offer a blanket apology? Would that weaken the impact? I don't know? Perhaps the question is also- what are they trying to achieve?

Whatever apology they end up giving I would like to see it accompanied by legislation that Turing would have approved of (Marriage Equality? Anti-Discrimination? Hate crime legislation? More Grant money in Recursion Theory? AI?) Or maybe an award in his name.

Hiring at Univ of MD at College Park

As Jon Katz blogged about here and as Lance Fortnow Twittered about, yes indeed, Univ of Maryland at College Park is hiring. (I delayed posting on it until it was official, hence Jon Scooped me!) See here for details. One thing to note: the deadline for applications is October 15, which is rather early. So if you want to apply, get your resume updated, your letter writers writing letters, and your webpage in order. ~ ~ ~

Interface Between Computer Science and Economics

I'm at Cornell for the NSF-sponsored workshop on Research Issues at the Interface of Computer Science and Economics which has brought together a great collection of CS and Econ people interested in questions of common interest. Economist Larry Blume mentioned how CS helps understand the "inadequacies of the Bayesian paradigm" generally used by economist. Computer Scientist Jon Kleinberg talks how econ helps "broad the range of algorithms" and how computation can be both a resource and constraint in economic models.

NSF CCF director and CS theorist Sampath Kannan talked about similarities between CS and econ: Both deal with human-created artifacts and both talk about understanding the possible and the impossible. I would argue that while computers are a human-created artifact, computation itself is a natural process. I suppose an economists might make a similar argument.

Most importantly Sampath talked about the strong support of the NSF in both CS and Econ to focus more on these communities. The NSF Econ program office Nancy Lutz also promoted this view talking about the fondness of math in both fields.

Much of my research in the last couple of years has been looking at ways to apply tools of computational complexity to economic models which is what I'll be talking about later today. Can we harness the computational powers of "the market"? How does agents of limited computational ability change the outcomes of economic situations? Can we use computation to help explain economics phenomenon? Somehow I need to talk more complexity theorists to work on these problems. Why should algorithms people have all the fun?

On that note the accepted papers for SODA is out and Noam picks out the ones related to CS/Econ issues. 

Is P=?NP ind of ZFC a respectable viewpoint?

I recently got an email that told me there is a debate going on about whether the the position P=?NP is independent of an axiom system such as ZFC deserves its own section on the Wikipedia P=?NP page. This raises several questions:

1. Math Question: Is P=?NP ind of ZFC? I tend to think that P=?NP can be resolved in ZFC. My (possibly naive) reasoning is that P=?NP is a question about rather concrete objects, as opposed to CH which deals with the reals. This is not a strong believe on my part and I would like to see more serious arguments for and against.
2. Sociology Question: Are there any serious CS theorists who believe that P=?NP is ind of ZFC? Of course this question depends on your definition of serious, theorist, and believe. Also it might not be the right question since, if (say) Terry Tao or Saharon Shelah thought that P=?NP was ind of ZFC then that is to be taken seriously, even though they are not CS theorists.
3. An Infinite Number of Sociology Questions: For all i what is the strongest theory T_i such that there exists a set of i serious CS theorists, each one of them believing that P vs NP is ind of T_i?
4. Wikipedia Question: How does Wikipedia decide these things? I do not know. However, if there was a credible paper saying why it is plausible that P=?NP might be ind of set theory, then I think it should be included. I do not know of any.

The End of Summer Classes (Guest Post)

(Guest post by Sorelle Friedler. Companion post at her blog

This summer I taught the 400-level Algorithms class at the University of Maryland. Two summers ago I taught a 300-level programming languages class, and promised myself that I'd never teach another summer class. Apparently the lure of getting to teach Algorithms was just too much for me. I love teaching, and enjoyed teaching this summer, but summer classes are exhausting for students and teachers. I also believe that they're ill-advised for the students and think it's a problem that students are not warned against them. This, of course, is the true problem; I knew what I was getting into - they didn't.

While summer classes have the same amount of in-class time as regular semester classes, the out of class time is significantly less (the regular semester class takes 15 weeks, while the summer version takes 6). This satisfies the accountants, but doesn't give the students enough time to actually absorb the material. In addition, as Bill notes in the dual to this post, the students who take summer classes do not represent the standard distribution of ability. Specifically, there are more weak students - the students who could most use the extra time. In Computer Science, especially in programming classes, having enough time is critical.

And what about the strong students? They certainly still learned the material and did a great job on the homework. I decided to assign a somewhat open-ended programming project (a topic for a different post), and the strong students challenged themselves and did an amazing job. Yet with more time there would have been more opportunity for challenging problems and more advanced topics.

I admit, of course, that having summer classes makes logistical sense. It's a good chance for students to get ahead or just manage to graduate on time. Despite the problems, students learn something, pass, and get to move on. But if the goal is a deep understanding of the material or even an understanding equivalent to that achieved in a regular semester course, the summer just isn't good enough.

Musing from the Barriers Workshop

Rahul Santhanam guest posts with thoughts from last week's Barriers in Computational Complexity workshop in Princeton.

1. What's a complexity theorist's definition of an algorithm? A failed attempt to prove a lower bound. One of the more famous examples of this is Arora's approximation algorithm for Euclidean TSP. At the workshop, I heard about a couple more. Chris Umans mentioned that the new algorithms for matrix multiplication in his paper with Henry Cohn came about in part because of a failed attempt to prove their approach was unviable. While chatting with Dave Barrington about his counter-intuitive characterization of NC¹ by bounded-width branching programs, I learned that this too resulted from an "obstruction" to proving a lower bound (By the way, Dave's result was voted the most surprising result in complexity theory by an eminent panel on the first day). It struck me that this ability to toggle freely between "hard" (reductions from complete problems, oracle & black-box results) and "easy" (algorithms) viewpoints is a very productive component of our way of thinking. Of course this is formalized in results such as Razborov-Rudich and Kabanets-Impagliazzo, but it's also an indication that Nature is far from adversarial. It could have been that interesting problems are not just hard but also that we could say nothing interesting about their hardness... Instead, we have an extensive theory, a rich web of implications. Sure, lower bound proofs are difficult, but then there are the chance flowerings of failed attempts.

2. The highlight of the workshop for me was talking with Ketan Mulmuley about his approach to P vs NP using geometric invariant theory. Ketan has been working on this approach for more than a decade now. Given his seminal work on semantics of programming languages, parallel algorithms and computational geometry, and his reputation as a brilliant problem solver, he was always going to be taken seriously. But there was also an element of mystification - was all this high-powered mathematics really necessary to attack P vs NP? Why spend time learning about this approach when it might not pay any dividends for the next half a century? And how could Ketan claim that this was in a sense the only possible approach to P vs NP? The fact that Ketan wasn't comfortable evangelizing about his approach didn't help matters.

It seems to me that now there's a qualitative shift. There seem to be two factors in the shift - one is that Ketan is more confident in the viability of his program than he was in the formative stages, and the second is that he is more aware now of the importance of communicating both with mathematicians and with complexity theorists about his approach. Indeed, the scale of the project is so immense that collaborations across the board are necessary to its success.

To his credit, Ketan has realized this. Earlier, when the possibility was suggested to him that his approach might lead to weaker but still interesting lower bounds along the way, or to connections with other problems, he didn't seem very interested, possibly because he was focused on the ultimate goal of separating P and NP. Now, he is more actively encouraging of the search for such connections. Also, he doesn't claim that his approach is the only one for separating NP vs P - such a claim is hardly tenable. Instead, he makes a much more nuanced argument in terms of the barriers that other approaches run up against and which his own program avoids, as well as for the mathematical naturalness and aesthetic value of his approach. As for the time scale of the project, it's true that carrying it out in its present form would involve solving mathematical conjectures that algebraic geometers consider far beyond the reach of present techniques. But there is always the possibility of short cuts arising from unexpected connections and new ideas. For this reason, estimates of time scales are speculative, and perhaps not all that relevant.

The P vs NP question is the most important in our area, and as of now there seems to be exactly one program (in the mathematical sense) for solving it, and that's Ketan's program. Simply for that reason, it deserves serious study. At the very least, the decade of mathematical labour that has gone into developing the approach, together with the current efforts to explicate the approach and its relation to barriers complexity-theoretic and mathematical, have raised the standards for any future approach to be taken seriously.

The best sources for learning about the approach are his Complexity Theoretic Overview of GCT and Mathematical Overview of GCT.

3. A few people at the workshop questioned the focus on barriers. Ran Raz gave a great talk in which the "barrier" slide merely had a picture of the human brain (but then, isn't it even more unlikely that a computer could prove P != NP?). Why are we so obsessed with barriers? Perhaps it's because we are computer scientists rather than mathematicians. Mathematicians don't care about constructivity - they believe that proofs exist, however long it takes to find them. It was a question of when Fermat's last theorem would be proved, not whether. We, however are used to doing things efficiently (at least in theory). So if we fail to find a proof quickly, the fault surely "lies not in ourselves but in our stars". Walls tend to spring up around us just as we're on the verge of something extraordinary. Oracles give us gloomy portents. We're forced to be unnatural. ZFC shrugs and turns away from the question...

Yet there is something uncanny about the whole thing. Lower bound questions can be formulated (and have been formulated) in many different ways mathematically - there hasn't been any real progress with any of these formulations. Just as an algorithm for SAT would also solve every other NP-complete problem, a lower bound proof would say something about all these formulations at once, which seems odd since they pertain to apparently unrelated areas of mathematics.

Just another barrier with which to amuse ourselves.

4. The very last talk of the workshop was given by Luca Trevisan, on the advantages of being a polyglot. Historically, complexity theory is rooted in logic and combinatorics. As it matures as a discipline, theorists are able to ply their skills in other mathematical provinces. Pseudorandomness is an especially "extroverted" part of complexity theory. Theorists have made important contributions to problems such as explicit constructions of Ramsey graphs (Barak-Rao-Shaltiel-Wigderson) and the Kakeya conjecture (Dvir) using the language and techniques of pseudorandomness.

Luca's talk was about connections between pseudorandomness and additive number theory, with an emphasis on the result by Green and Tao that the primes contain arbitrarily long arithmetic progressions. He made the point that the techniques that go towards proving this result can be phrased in a couple of different languages, the language of functional analysis (functions, norms) and the language of pseudorandomness (distributions, distinguishability, statistical tests). It's useful to construct a "dictionary" between these two languages, since concepts that are transparent when phrased in one language become less so when translated into the other. For example, the functional analysis viewpoint implies that distributions and adversaries are the same kind of object, which seems strange from the other viewpoint. Not only is this dictionary useful in learning the new language, but also because it exposes new concepts that our native language is not well equipped to handle. Indeed, there have already been many fruitful applications of the Gowers uniformity concept to theoretical computer science, including the Samorodnitsky-Trevisan work on low-error PCPs, the work by Bogdanov, Viola and Lovett on PRGs for low-degree polynomials, and the recent beautiful work by Kolaitis and Kopparty on modular convergence laws for first-order logic with the Mod p operator. It seems likely that there are many fruitful connections still unexplored. Luca's survey in the SIGACT News complexity column (PDF) is well worth checking out.

5. There were also several cool talks at the workshop where I learned about new results. Ben Rossman talked about average-case monotone lower bounds for Clique under natural distributions - this is a problem that has been open for a while. He shows that there are two values of the edge probability for Erdos-Renyi graphs, p₁ and p₂, such that no monotone circuit of size less than n^k/4 can solve k-Clique well on average on both of the corresponding graph distributions. This result complements Ben's other recent result showing that k-Clique does not have constant-depth circuits of size less than n^k/4, and uses some of the same techniques, inspired by intuitions from finite model theory. Toni Pitassi spoke about work with Paul Beame and Trinh Huynh on "lifting" proof complexity lower bounds from rank lower bounds for Resolution to lower bounds for stronger systems such as Cutting Planes and Lovasz-Schrijver. This builds on the "pattern matrix" method of Sherstov, which Toni discovered was also implicit in the Raz-McKenzie separation of the monotone NC hierarchy from more than a decade back (see correction below). Of course it would be very interesting to "lift" circuit lower bounds in this fashion, but few results of that kind are known. Adam Kalai talked about work with Shang-Hua Teng on learning decision trees and DNFs under smoothed distributions - product distributions where every co-ordinate probability is chosen uniformly in random from some small range. These learning algorithms do not use membership queries - corresponding results for the uniform distribution would solve longstanding open problems. Adam made the point that his result can be thought of as modelling Nature in a way that is not fully adversarial. At least for "most" reasonable distributions, we can in fact learn efficiently in these cases.

6. The workshop was a great success, in part because it brought together more complexity theorists than any current conference does. It was also very smoothly organized. Thanks to Avi, Russell, the session organizers, the admin staff and the student volunteers for making it such a valuable experience.

Correction from Sherstov (10/5/09): What Toni meant is that the two works study related communication problems (just like there are many papers on the disjointness problem); the two differ fundamentally as to the techniques used and results achieved. This point is clarified in the revised version of Toni's paper on ECCC (page 3, line -15).

My last post on steretypes (I hope)

I was not going to post on stereotypes anymore (my last two posts were on the topic) but three events that span 100 years have inspired me to do to.

Event ONE: I found a blog that I posted in Aug 1909 which asked if the Americans might catch up to Europe in Mathematics someday. One of the comments on it was

Look at the German Mathematics Tradition!. Look at the American one. The Americans are so weak my comparison that it must be something about their culture. It is clear that the Germans have always been better than the Americans in Mathematics, and always will be. Will there ever be a American Hilbert? I think not.

EVENT TWO: I found a blog entry from Aug 1960 which asked if Japan might catch up to American in Engineering and Car Building. One of the comments on it was

Don't be ridiculous. The fact that the phrase Made in Japan has come to mean that it is of bad quality shows that the Americans are better Manufacturers than the Japanese and always will be.

EVENT THREE: In Aug 2009 I co-ran a TA orientation with ***SORELLE*** and another grad student ***MAH***. As part of it, everyone was to give me their name, what course they are TAing, what field of CS they want to study, and their favorite TV show. For the TV shows I got the following (probably more that I forget)

1. So you think you can dance dance dance dance dance.
2. Friends
3. The Big Bang Theory
4. ST-TNG and Babylon 5
5. Daria and Burn Notice (that was me)
6. Numb3rs (that was ***SORELLE*** who I respect in everything except taste in TV shows.)
7. Daily Show and the Colbert Report
8. I don't' watch TV since its just a mechanism to deliver commercials. (Gee- he could get NETFLIX and get commercial free DVDs.)
9. I don't watch TV.

There may have been a few more. However, the person who picked ST-TNG noted that I can't believe in a room full of CS Grad Students I'm the only one who mentioned a Science Fiction Show (READERS: picture this person in your mind.) The stereotype of CS people being Star Trek Fans is out of date. When the recent Star Trek Movie came out Lance posted an Obligatory Star Trek Post. I don't think it is obligatory.

Why has the link between Star Trek and CS been weakened? I think that both CS and Science Fiction have become more mainstream. Hence CS can overlap with non-Science Fiction and Science Fiction can overlap with NON-CS (actually it probably always did).

Back to stereotypes. The person who was the only CS Grad Student who mentioned a Science Fiction Show was a female. I suspect that is not the picture you had in your mind.

CS and the Web of Knowledge

Often the best papers from a particular conference are collected into special issues of a journal where they go through a traditional journal review process. Having a paper in a special issue is a bit more prestigious than a regular journal paper.

Recently I co-authored a paper invited to a special issue and we had to turn them down. Why? For that we have to talk about the Web of Knowledge.

I have generally ignored the ISI Web of Knowledge, an subscription-only index of academic literature by Thomson Reuters. The web of knowledge didn't index CS proceedings or tech reports, so sites like Citeseer, DBLP and Google Scholar were much more useful.

Unfortunately, I can't ignore ISI as easily as I'd like to. Both Northwestern and the National Science Foundation use the database to pre-populate the publications in my on-line annual reports. I'd have to manually add my conference papers. Finally over the summer ISI has added most CS conference proceedings papers so this process ought to be easier in the future.

But that's all minor compared to what I have seen happening in some European countries where the ISI is taken way too seriously. ISI has different paper types: Articles, Proceedings and a few others. Some countries, which use these numbers for hiring, promotion and grants, are just counting Articles which puts computer science at a comparative disadvantage where say STOC papers don't count.

Now to answer the question about special issues: The ISI labels special issue papers as "Proceedings" so they don't get labeled as true articles and wouldn't help my co-author, who needs more "Article" papers. So we turned down the special issue for rather technical reasons.

The Status of the P versus NP Problem

Another month, another CACM article about another important and seemingly impossible to solve problem.

None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question. Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not. The P versus NP problem continues to inspire and boggle the mind and continued exploration of this problem will lead us to yet even new complexities in that truly mysterious process we call computation. 

Also a pre-publication version. Pure coincidence of having two CACM articles in a row, I don't have any more in the pipeline. If you missed it last month I told CS to grow up.

Why are the French Fair Game for ...

In my last post one of the comments asserted without justification that The French will never be as good at Engineering as the Germans. Rather than ponder if this is racist or bigoted, I would challenge the poster to either give HARD EVIDENCE that this has been true in the past, and a REASON to think it will continue. I still stand by the notion that globalization will make all of these local factors go away. Mainly because locality is not longer as important as it once was.

However, that is not the topic of my post. My topic is the French and bigotry against them.

1. Upon coming back from CCC 2009 several people said It was in France. Were they rude to you as the French are apt to be? Several of the people who said this never met a French person.
2. There was a line on the ST-VOY along the lines of No wonder he is arrogant- he is half-French and half-Romulan (note- this is from memory so it may be off but something close to it is true)

Can you imagine someone saying to me When you go to the Jewish Deli do they try to rip you off? or when you teach in that summer program for students from HBCU's (historically black colleges and Universities) are many of the students lazy? on crack? or When you go to Dagstuhl Complexity (Workshop in Germany, I"ll be there in October) make sure they don't know you have Jewish ancestry. We would all find such statements distasteful and bigoted. Yet a remark about the French being rude or arrogant seems commonplace. Not even the forces of Political Correctness (be they real or imagined) seem to object to bigotry against the French.

Star Trek already stereotypes entire races, though they are fictional and of their own creation, so I suppose that's okay. However, the show seemed to be against bigotry, most glaring in Let this be your last battlefield from ST-TOS (more commonly known as The one with the half-black, half-white guys). The other shows had much less on this topic. (Side Note--- the later Star Trek series were undercut by the fact that you no longer needed to be a Science Fiction show to talk about controversial issues. For example, there was an episode of ST-VOY that was a metaphor for AIDS. It seemed silly since other TV shows talk about it explicitly.)

I may be wrong about all of this, so let me rephrase it as several questions: (1) Is stereotyping the French acceptable in modern American society? (2) If so why is that given that stereotyping other groups is largely unacceptable (at least in the circles most of us travel in). (3) Am I a Trekker or a Trekkie?

A Busy Week

I used to just stay off the Internet completely during a vacation week. But the net has just become so useful that one cannot ignore it, for example using my iPhone and the free WiFi at a Norwegian café to track down the Munch in Bergen. I use Skype to call home and download the New York Times on my Kindle. But I avoid all CS stuff: No email, blogs or Twitter. I just don't want to read anything that gets me upset or makes me feel I need to accomplish even a small task.

This week we have many end-of-summer conferences and workshops. A sampling.

• In Princeton, the Barriers in Computational Complexity workshop. Each day they take a different research area and discuss the problems we don't know how to solve starting today with Boolean complexity and P v. NP. Hopefully Scott will post about the workshop but if someone would like to guest post for this blog let me know.
• The Mathematical Foundations of Computer Science Symposium, the Eastern European theory conference, in the Northern mountains of Slovakia. Muthu is an invited speaker and blogging about the experience.
• In Lyon the Conference on Very Large Data Bases (sic). Suresh is Twittering the conference as I write this.
• Right here in Chicago, the International Symposium on Mathematical Programming, the triennial OR meeting. Tallys Yunes is blogging. On Sunday they gave several major awards:
• Dantzig Prize: Gérard Cornuéjols
• Tucker Prize: Mohit Singh. Tobias Achterberg and Jiawang Nie were the other finalists.
• Lagrange Prize in Continuous Optimization: Jean Bernard Lasserre
• Beale-Orchard-Hays Prize: Tobias Achterberg
• Fulkerson Prize (awarded to three research groups):
  • Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas (for proving the Strong Perfect Graph conjecture)
  • Daniel Spielman and Shang-Hua Teng (smoothed analysis)
  • Thomas Hales and Samuel Ferguson (for proving the Kepler conjecture)

I'm not attending any of the above, though I'm a bit sorry I'm missing Princeton. My older daughter starts high school this week, the younger one middle school. Both are joining schools much larger than the previous one and both are a bit nervous so I'm here for moral and other support. And besides it gives me a chance to catch up on the mountain of email I ignored on vacation.

The Hungarian Reputation foR Combinatorics

I met and talked with two Israeli Graduate Students Working on Derandomization (if you are them please email me- I seem to have lost your names and email addresses, and I want to acknowledge you in a paper I am working on and send you a first draft).

Is Israel known for work in derandomization? I do not know. Is Hungary known for combinatorics? Of course. This raises some questions.

1. Is the notion that Hungary is strong in combinatorics true? I would think so; however, I would like to see some hard data: Do they have the most combinatorists per capita? (probably yes). Do they teach Ramsey Theory in Kindergarden? (probably not).
2. Assuming that Hungary is strong in combinatorics, what caused it? One answer is Erdos. Certainly Erdos encouraged and amplified the trend, but it was already there. In particular there were already Math Competitions in Hungary way back in 1884. See here for a short history of The Eotvos Compeition and see here for the problems.
3. What other countries have reputations for certain areas? Are these reputations accurate? How does one measure such things? One problem with measuring such things is how much do you count one superstar? Is Israel strong in Logic because of Shelah? (I tried to see if he was the best logician in the world by typing Best Logician in the world into Google; however, it returned Did you mean Best Magician in the world?.) Do you count where someone was born? where they went to High School? College? Grad School? Where they are now?
4. With Globalization will these differences fade away? (probably Yes). Have they already? (probably yes).

An application of VDW theorem to Number Theory- is there a better proof?

I present what may have been the first Application of van der Waerden's Theorem. I also ask the question: Is there an alternative proof? This would be interesting since the hope is that an alternative proof would have better bounds.

Notation: [W] is the set {1,...,W}, QR means Quadratic Residue (square root mod p, where p will be understood), QNR means NOT a Quadratic Residue.

VDW Theorem: For all k, for all c, there exists W such that for all c-colorings of [W] there exists a,d (d &ge 1) such that a, a+d, ..., a+(k-1)d are all the same color.

One might wonder- can we also have d be that color? How about a multiple of d? OKAY, you might not wonder that, but the answer is YES and we need this extension of VDW for our application:

Extension of VDW Theorem: For all k, for all s, for all c, there exists W such that for all c-colorings of [W] there exists a,d (d &ge 1) such that a, a+d, ..., a+(k-1)d, sd are all the same color.

See this excerpt from my book for a proof. (We only need the s=1 case, but this version with general s is no harder and is used in a proof of Rado's theorem.)

Before presenting the theorem duh jour and its proof we quote Karen Johannson's excellent Masters Thesis Variations on a theorem by van der Waerden (2007 from The University of Manitoba, Dept of Mathematics)

Historically, the first application of van der Waerden's theorem may be due to Brauer who proved a conjecture of Schur about quadratic residues. Brauer used a generalization of van der Waerden's theorem, which he attributed to Schur. The following theorem is a further generalization of Brauer's result. The proof is now folklore and I have been unable to locate the original source. The details appear, for example, in (she gives ref to TO GRS book on RAMSEY THEORY, page 70). (She then gives the statement and proof of what I called above Extension of VDW. I suspect that Brauer only proved the s=1 case since that is all he needed.)

We won't restate or prove Extension of VDW, but we give the theorem on QR's that uses it.

Theorem: For all k there exists p₀ such that, for all primes p > p₀ there are k consecutive QR in Z_p (the integers mod p).

Proof: Let p₀=W(2k+1,2). Let p > p₀. Color [p] as follows:

COL(x) = 1 if x is a QR mod p, 0 otherwise.

By The Extended VDW theorem, with s=1, there is a, d such that

a, a+d, a+2d, ..., a+2kd, d

are either all QR or all QNR. Let d^-1 be the inverse of d mod p. Since the product of two QR'is a a QR and the product of two QNR's is a QR (that is not a typo- it really is true) we have that

ad^-1, ad^-1+dd^-1, ad^-1+2dd^-1,..., ad^-1+2kdd^-1 = ad^-1, ad^-1+1, ad^-1+2, ..., ad^-1+2k

are all QR. Note that the addition is mod p so it may be the case that we have something like

p-4, p-3, p-2, p-1, 0, 1, 2, 3, ...

Since there are 2k of these elements, there must be k truly consecutive.

END OF PROOF

Note that the bound, W(2k+1,2) is quite large. A proof that avoids VDW would hopefully yield a better bound. Is there one?

The same theorem for QNR's is also true with a proof that uses VDW's theorem. I leave that for you to figure out.

Request insights on future of the job market (guest post)

(Guest Post from Dave Doty on the Fall 2009 Hiring Season.)

The CS academic hiring season for Fall 2009 was, to understate the point, a bit sparse, as predicted by Lance Fortnow last year. Sixty lucky, and as yet unnamed, CIFellows, as well as some others able to tread water as TAs, RAs, or postdocs, can wait out the storm, but at some point in the next year, those without a tenure-track job need to make a decision about what to do with their Ph.D.: try for academic jobs, or dust off the programming textbooks (a thick coating of dust for some of us in theory) and start preparing for industry interviews. Our choice depends, of course, on the level of recovery of the academic job market in the next year.

I have no insight of my own into this, but I hope to use the far reach of this blog to sample the opinions of the community about how the Fall 2010 CS academic job market will look. Hopefully, the opinions will be informed by actual information, although secondhand anecdotal information, as well as rampantly speculative conjecture by faculty, will nonetheless exceed my level of insight and is welcome. I can imagine these possibilities:

• Recovery to "normal" levels
• Recovery to substandard levels, but more than the paltry offerings this year
• Recovery to better-than-average levels as universities try to make up for the low hiring level this year
• Normal demand for assistant professors, but a larger supply since many who would have applied this year are waiting until next, and then the 2009 and 2010 graduates will be competing together
• The complete implosion of civilization
• Some scenario laid out completely in a Communications of the ACM article that I simply failed to read

Disclaimer: I am a graduating student who, like many readers, is investing time getting a Ph.D. because I want a tenure-track academic position, and I understand the temptation to complain about perceived flaws in the way some universities are handling the financial crisis. But what I mainly hope to obtain in the comments is field intelligence about next year's job market from anyone "in the know", and it's probable that such people are more likely to post their thoughts if they don't perceive their posting to be within a sea of anger.

Dave Doty

What is the most interesting number ?

What are the most interesting numbers- I allow reals and complex numbers this time. To avoid having too many numbers I have restricted it to numbers that have had entire books written about them (there is one exception that I note below), and to be of mathematical interest (e.g., the speed of light is not included and the square root of 2, which I did include, perhaps shouldn't have been).

Review of books on 0,1,pi, e: here, Review of a book on i: here. Review of a book on square root of 2: here. Review of a book on phi: here. Review of a book on gamma (whats gamma?): here. If there is some mathematical constant that has had a book on it that I have not included, please comment.

Here is my choice ranked in order of how important they are.

1. 0. Addition is more basic then multiplication so the additive identity comes before the multiplicative identity.
2. 1. Multiplicative identity.
3. -1. Negative numbers--- what would we do without them? One could even argue that subtraction is more important than multiplication and make this number 2 on the list. There is no book on -1 that I know of, but it is still too important to not put on this list.
4. pi. Without pi we wouldn't have circles!
5. e. Ah-ha- the pi vs. e debate. You can read about it here or even listen to a real debate here. I would go with pi since the level of math it is on is more basic then the level of math that e is on.
6. gamma. What is this constant? It is the difference in the limit between natural log of n and 1 + 1/2 + ... + 1/n. How important is it? I read the book on it pointed to above. The book is pretty good but it mostly talks about related topics- logs, Zeta functions, pi. So I still don't see why gamma is worth a book. I suspect that there are more math constants that are more important that just happened to not have books written about them. Or they have and I don't know about them.
7. phi. There is the notion that the Golden Ratio pops up in math and in nature all the time. And there are those who disagree.
8. square root of 2. This is interesting historically as the first irrational number, but I don't think it has much mathematical significance.

What is the least boring number (NOT the usual paradox)

What is the first boring natural number? I am NOT going to present that the first boring natural number is interesting crap, which may qualify as the most boring paradox.

The question is, of course, ill defined. I will define it a little better by only considering mathematical properties of numbers. (e.g., 7 is interesting because there are 7 days of the week will not work.) Here are my opinions, and my opinions of my opinions. I will write WEAK if I think the justification for calling that number interesting is weak. In those cases if you know a better one, then comment on it.

1. 1 is interesting as it is the multplicative identity.
2. 2 is interesting because it is the only even prime. Also the first prime.
3. 3 is interesting because it is the first odd prime. Also the first Mersenne prime.
4. 4 is interesting because it is the first non-trivial square. Also it is the first number that is the sum of two primes.
5. 5 is interesting because it is the first number that is the sum of two distinct squares and the first number that is the sum of two distinct primes. (WEAK)
6. 6 is the first perfect number (though there are so few perfect numbers that ALL of them are interesting.)
7. 7 is the first number such that the number of squares needed to add up to it is 4 (All numbers are the sum of 4 or less squares. There are an infinite number of numbers that require 4 squares: all of the numbers congruent to 7 mod 8.)
8. 8 is the first non-trivial cube.
9. 9 is the first non-trivial odd square. (weak)
10. 10 is the first number that is the sum of two distinct odd squares. First triangular number that is the sum of 3 squares. (weak)

have not been able to come up with anything interesting about 11. I could say that 11 is the first number that is the sum of 2 distinct numbers in 5 different ways. But that seems very weak: every number of the form 2n+1 is the first number that is the sum of 2 distinct numbers in n ways. Also, every number of the form 2n is the first number that is the sum of 2 numbers in n different ways. If we allowed that definition of interesting then all numbers would be interesting.

Imre Simon Passed Away Recently

(Janos Simon emailed me this information that should interest readers of this Blog.)

Imre Simon, a distinguished Hungarian-born Brazilian Theoretical Computer Scientist passed away August 12.

Most of his scientific accomplishments were in "European" Theoretical Computer Science--his main research area was combinatorics of words: he was responsible for the introduction of the formal study in Theoretical Computer Science, of the algebraic structure that is now known at "Tropical Semiring". [The structure is the abstraction of the Kleene operation on languages: sum, product (without inverses, but with the usual distributive properties), and star. The name "tropical" is an allusion to Brazil.]

Still, his first result in Theory, initially published as a University of Waterloo Technical Report, is a study of the compexity of the Davis-Putnam procedure for proving tautologies (I. Simon, On the time required by the Davis-Putnam tautology recognition algorithm. Notices Amer. Math. Soc. 18 (1971) 970.) He shows that the naive impementation runs in exponential time. I believe that this was the first formal result in proof complexity in the West.

Another result, that may be known to our community is his 1978 FOCS paper (I. Simon, Limited subsets of a free monoid, in Proceedings of the 19th Annual Symposium on Foundations of Computer Science, IEEE 19 (1978).) He considers the following problem on finite automata: Given a regular expression R, consider the language R^*= I + R + .... + Rⁱ + .... It is easy to get a procedure that tests whether R=R*. (Exercise for the interested reader!) Now ask the "next" question: is R^* = I + R + .... + Rⁱ (instead of an infinite union, just the union of the first i terms). This is also easy, for any fixed i (Exercise for the reader who is still interested.) The question that Imre solved was: Is it decidable whether there is an i, such that R^* = I + R + .... + Rⁱ ?

The answer is Yes. Of course, another question is "why does anyone care?" The answer to that is that the proof is very nice--actually Imre gave two proofs, one combinatorial, and one algebraic. More importantly, this is a case where algebraic techniques can be imported to reveal hidden structure, and help attack questions of decidability and compexity. The strategy has proven to be quite important and successful in other contexts.)

A relatively recent biographical sketch and bibliography can be found in the Festchrift for his 60th birthday that appeared as a RAIRO special here

Imre also had an important role in the development of the Theoretical Computer Science community, and, more generally, academic Computer Science in Brazil--in particular the CS Departments at USP (Sao Paulo University) and UNICAMP (University of Campinas) have benefited from his energy, organization and dedication. He was a coauthor of the first monograph on Theoretical Computer Science [T. Kowaltowski, C. Lucchesi, I. Simon and J. Simon, Aspectos Teoricos da ComputaCao. Projeto Euclides. Livros Tecnicos e Cient B1ficos Editora Rio de Janeiro (1979). Prepublished at the occasion of 11o Coloquio Brasileiro de Matematica, IMPA, Rio de Janeiro (1977)], was an advisor and mentor to numerous young Brazilian scientists, helped launch the LATIN series of Theory Conferences, was instrumental in bringing to Brazil visitors like Schutzenberger, Bollobas, Adi Shamir, Lessig, and Benkler, and was an effective booster of the Brazilian Computer Science community both in the Brazilian science establishment and in the Brazilian government.

He was also a generous and unselfish person, and a personal friend. He will be missed.

How much credit should the conjecturer get? Is Conjecturer a word?

Theorems are often named after who proved it. The ones who conjectured it are often forgotten.

1. Mordell's conjecture was solved by Falting. It is now called Faltings' Theorem.
2. Vazsonyi's conjecture was solved by Joseph Kruskal. It is now called The Kruskal Tree Theorem.
3. Baudet's conjecture was solved by van der Waerden. It is now called van der Waerden's theorem . Even though van der Waerden's original paper has as its title (roughly translated) On a conjecture of Baudet, Baudet is not well known.
4. Fermat's last theorem was solved by Wiles. If you type Wiles into Wikipedia you get as options Wiles Theorem which goes to a page whose web address is http://en.wikipedia.org/wiki/Wiles_theorem but whose title on the page is Fermat's Last Theorem. This one may still be in transition from being someones conjecture to someones theorem. It may be for a while. This one is so tied to Fermat that it might always have his name on it somehow.

If you know of other examples please comment. Is it unfair that the original conjecturers are forgotten? Alexander Soifer thinks so. In his book The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators (reviewed in my latest SIGACT NEWS Book Review Column) he suggests that we should name a theorem after both who conjectures it and who solves it. So what I call

Van der Waerden's Theorem

Soifer calls

The Baudet-Schur-Van der Waerden Theorem.

(Baudet is known to have conjectured it. Soifer argues convincingly that Schur also conjectured it.) Reading over van der Waerden's own account of how the theorem was discovered (included in Soifer's book) it seems to me that Artin contributed some to the solution of Baudet's conjecture. If standards for co-authorship were weaker then he may have been a co-author. In this alternative universe what I would call

The Artin-Van der Waerden Theorem

Soifer would call

The Artin-Baudet-Schur-Van der Waerden Theorem.

This is odd since you have prover-conjecturer-conjecturer-prover in the ordering. Perhaps another convention would arise. Perhaps it would be called the ABSV-theorem or ABSW-theorem. Perhaps we are better off, just for the sake of simplicity, using just the prover's name. There have been some fierce battles over who PROVED what. Do we really want to have fierce battles over who CONJECTURED what? I conjecture that we do not.

Live from Russia

This week I am giving some lectures at the NoNA Summer School on Complexity Theory in St. Petersburg. 

This is my first time in Russia, a country I never expected to visit when I grew up during the cold war. One has to go a few generations back, but most of my ancestors came from Russia (think Fiddler on the Roof) or one of the former Soviet republics. Fortnow is derived from a Russian name. My father was born Fortunow but dropped the silent "u" because no one knew it was silent. 

In almost every European country I usually pass as a native of that country (until I open my mouth). Less so in St. Petersburg, a bit strange since I got most of my genes from this country.

Summer schools are interesting affairs. Usually a week long where speakers give several lectures introducing usually local students to a specific topic. This is my third such school: I gave lectures on Kolmogorov complexity in the small town of Kaikoura in New Zealand and in Marseilles. This time the topic is "Structural Complexity," basically I'm shrinking a semester-long complexity class into six hours with very few proofs. A bit challenging because the students have very different academic backgrounds but it seemed to go reasonably well. I broke the four lectures into themes:

1. Deterministic and Nondeterministic time and space including the polynomial-time hierarchy
2. Probabilistic Computation with a whiff of quantum.
3. Circuit Complexity
4. Counting and Interactive proofs/PCPs.

Next week I'm on vacation in Europe and off the net. Bill is on his own. See you when I get back.

Is Quantum the new Random ?

(This blog is an extension of a short conversation I had with Scott A at CCC09.)

Consider the following two statements that nobody would argue with or find controversial:

1. Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers.
2. Even if all you care about are deterministic models of computation you still need to learn probability.

I think that the following is now true:

(Q) Even if all you care about are deterministic models of computation you still need to learn quantum techniques.

There are lower bounds on classical Private Info Ret that use quantum techniques. (See Exponential Lower Bounds for 2-Query Locally Decodable Codes via a Quantum Argument by Kerenidis and de Wolf here.) The papers of Gentry and Peikert used quantum techniques in Crypto. (Disclaimer: Browsing through Peikert's paper I spotted the Quantum, but for Gentry's I didn't see it.) At CCC09 Scott told me a proof that PP is closed under intersection using Quantum techniques.

1. When will statement Q above be as noncontroverial as the two statements (1) and (2)?
2. When will we be teaching Quantum techniques in the standard Grad Complexity Course?
3. When will we be teaching Quantum techniques in the standard Undergrad Complexity Course?

Rump Sessions at Conferences

The Complexity Conference has almost always had a Rump Session which is where people sign up to give a 10 minute talk on what they are working on. (They didn't have one in 2009 to make room for more talks since there were more submissions.) It can be at any level of development--- open problems, partial results, finished results.

Some conferences usually have rump sessions and some usually do not. By asking around (not always reliable) I have found that STOC, FOCS, SoCG usually do not have rump sessions but that CCC, Crypto, Eurocrypt, AsiaCrypt, AfricaCrypt, TCC (Theory of Cryptography Conference), FSE (Fast Software Encryption) usually do have rump sessions. (A different question, dealt with in Jon Katz's Aug 7 blog is are there too many crypto conferences. That post and the comments on it also list more crypto conferences.) I would like commenters to correct and add to this list.

1. I do not know where the term Rump Session comes from. I first heard it from Alan Selman at the first CCC business meeting, though he used it as though it was a common term. If you Google the term you get around 19,000 hits, mostly things like 2007 Crypto Rump Session
2. At a big conference a Rump Session might be harder to organize. That may explain why STOC, FOCS don't have them, but CRYPTO is pretty big and does, while SoCG is small and doesn't.
3. Early on Rump sessions were on a blackboard. Now many of the Rump sessions are prepared polished presentations. I am tempted to say that this means they are planned ahead of time and can't be things worked on at the conference, but actually people can now whip up polished presentations pretty fast.
4. Rump sessions are a good way to communicate informal unpolished ideas and ask for help on formalizing or polishing them. And for help on the hard math as well. I think that conferences should have them, though I realize that there may be logisiticaly problems.
5. Should you share your open problems with others so openly? If you want them solved and don't care if you are the one who solves them then YES. Frank Stephan and Martin Kummer solved an open problem that I proposed at a COLT Rump Session. They got a paper out at the next COLT where I was acknowledged. I was happy that my problem got solved.
6. Why do some conferences have it and others do not? My guess is the usual one Because we've always had (not had) them. Also, I suspect that the XXX-CRYPTO conferences have them because the first one, CRYPTO, had it.
7. What do non-theory Comp Sci Conferences do? How about outside of theory? In fields where they do not have prestige conferences perhaps many talks are what we call rump sessions.

Computer Go

While we have computer programs that have solved Checkers (it's a tie) and beat the world's best chess players, but until recently Go programs played a very mediocre game.

Computers playing these kinds of games have a rough similar structure: Do a search through the game tree for some number of levels, evaluate the resulting game boards and do mini-max through the game tree to pick the best move for the player. There are many tricks to speed up the search (allowing a larger depth) such as alpha-beta pruning, selectively extending the tree search and various other tools but the basics run the same.

The problem in Go is two fold: A very large number of moves at every turn forcing a very shallow tree and game boards that are very hard to evaluate. Much faster computers has helped in a getting at least a reasonable depth in the search. But what about evaluation?

Consider the following seemingly crazy way to evaluate a game board: Have each player play randomly and see who wins. Repeat a few hundred times and score the position by the percent of time that White won.

Imagine that strategy for chess: Each player would often put their pieces in jeopardy and the opponent would fail to take them. Most randomly simulated games would end in a draw because no one would execute the checkmate.

But for Go the random process to evaluate positions works. Combined with a very fast machine, a well-designed tree search and lots of fine tuning this process had led to Computer Go programs that can play good games against strong amateurs. 

We're a long way from having Computer Go programs as the top Go players in the world but when a simple idea takes the power of Go programs from lousy to not bad in a relatively short time one can hope.

What To Do With the Little Theorems?

Last week Shahar Dobzinski asked the following question on Noam's blog:

Suppose you have an interesting result that has an easy, almost trivial proof. What is the best way to publish it? Writing a full, formal paper takes too much energy. Besides, a travel to a conference just to give a 5 minutes presentation is an overkill, and journals are just too slow (who reads them anyways?)

Let me understand: You only travel to conferences to give presentations, journals are worthless and you are just too lazy in any case to write up results with short proofs. Luckily Noam managed to talk Shahar into writing up the result for Arxiv. Here's my advice.

Suppose you have proven a new result. It is a good result but not earth shattering. The proof has a cute trick but not particularly deep. However this result will not on its own get accepted into a conference you want to attend. What do you with it?

First write it up. Make sure your proof is correct and your exposition clear. Show it to a a few friends. Then try to see if there is an interesting new extension or ways your new proof technique could be applied to other questions. Don't extend for extensions sake. Nothing worse than taking a cute little result and turning it into an ugly messy but still little result.

So you've decided that the little result stands alone. Next claim the result for yourself. Send your paper to one of the on-line archives. This will also let others see your result.

But you still need to publish your result? What to do next. It depends.

Sometimes I sneak little results into other papers I am working on. In the back with only a brief mention in the introduction. If the paper gets into a conference so does my little result. But I usually feel a bit guilty about this.

Some people take small results, dress them up as far more important than they really are, make the proof needlessly detailed and submit these papers, sometimes successfully, to major conferences. Congratulations you got another FOCS paper. But do you feel good about yourself?

Not every theorem has to show up in a conference. If only theoretical computer science had a journal for little results. We do, it is called Information Processing Letters which limits submissions to nine pages. Many of you are wary of submitting papers to an Elsevier journal like IPL, but many other journals accept short papers. Theory of Computing has a short communications section for example.

But at the very least don't leave a little result unwritten. Some little results turn out to be incredibly important parts of other work but only if people know about it. And someday someone will reprove your result and claim credit for it if you never did.

Statistics for Fun and Profit

On the front page of the New York Times today along side a picture of a nerd shirt comes an article proclaiming the great need for people doing statistics in this age of limitless data. By "statistics" I think they mean "machine learning," that mathematical side of AI that seems to be where statistics is heading anyway.

“I keep saying that the sexy job in the next 10 years will be statisticians,” said Hal Varian, chief economist at Google. “And I’m not kidding.”

And my three favorite fields get mentioned in the same sentence.

Though at the fore, statisticians are only a small part of an army of experts using modern statistical techniques for data analysis. Computing and numerical skills, experts say, matter far more than degrees. So the new data sleuths come from backgrounds like economics, computer science and mathematics.

Theory's own data hunter Jon Kleinberg gets quoted in the article searching for pig lipstick.

Using the web you may run into self-reference

While the web is a wonderful to find things out there are times when it doesn't quite work.

1. An old blog of Scott Aaronson's had as part of its title a Woitian Link. Wanting to find out what a Woitian Link is but not wanting to bother Scott (he's busy enough making comments on Shtetl-Optimized) I went to Google and typed in "Woitian Link". The ONLY hits I got back were to Scott's blog. I finally had to email Scott. He told me that it was referring to the blog not even wrong by Peter Woit which often has links that... Well, Scott never told me quite what it was but I'll go there myself and try to figure it out.
2. An old blog of mine was the man who loved algorithms. Part of my blog said that I thought the man would be Knuth but it was not. (It was Thomas Kailath) One of the commenters said that it couldn't be Knuth since he was still alive. This made me want to check the original article to see if Thomas Kailath, is also still alive (he is). I didn't have the issue with me at the time so I typed "the man who loved algorithms" into Google. The first page of hits all referred to my posting. Eventually I found one to verify that yes, indeed, he was still alive.
3. Donald Knuth VOLUME FOUR is actually OUT in a series of fascicle's. Whats a fascicle? Here the web was helpful- Wikipedia said it was a book that comes out in short pieces, the pieces of which are called `fascicle'. They gave only one example: Donald Knuth's Volume 4 will be coming out in Fascicle. Still, they DID tell me what I want to know. (Note- this was a while back, they have since removed that comment.)

For most things the web is great. But for some more obscure things, better off asking someone who knows stuff. ~ ~

Finding Primes

The newest polymath project Finding Primes asks a question that ties together number theory and computation: Given a number n find any prime p>n deterministically in time polynomial in the length of the binary representation of n (about log n).

This problem came into vogue shortly after the AKS Primality algorithm put checking primes in deterministic polynomial time. A deterministic algorithm exists if you either believe in full derandomization or in conjectures on distributions of primes. The following algorithm will likely run in polynomial time.

while(not prime(n)) {n++}
output n

Many cryptographic protocols require finding prime numbers to multiply together to get hard-to-factor composites. By the prime number theorem, picking numbers of k bits at random will find a prime in O(k) tries with high probability and one could then run the Solovay-Strassen or Miller-Rabin primality tests.

Those tests would never give you absolute evidence that you found a prime. Goldwasser and Kilian gave a procedure for finding primes with a certificate of primality. The AKS algorithm eliminates the need for a certificate.

Oddly enough we would usually prefer a probabilistic over the deterministic method to find primes. Otherwise the adversary can use the same deterministic procedure and factor your number as easily as you put it together.

Find the Number- again

I was (once again) playing FIND THE NUMBER with a 10-year old. (For the first time see here.)

BILL: I am thinking of a number between 1 and 1000 (I wasn't but I said I was- in reality I would give the answers that maximize how many questions.) You can ask questions about it to try to see what it is.

ALEX: Is it &ge 500?

BILL: Yes (my thoughts: GOOD, Alex knows how to do this!)

ALEX: Is it &ge 750

BILL: Yes (my thoughts: GOOD, he should get it in 10 or so)

ALEX: Is it even?

BILL: Yes (yikes! How am I going to keep track of this? Why did he go to evens?)

ALEX: Is it a square?

BILL: No (hmmm- need to remember all the even square over 750).

Eventually he got it in 14 questions. He then thought of a number that I was trying to figure out. My first three questions were of the type is it bigger than.... He complained: You're a math guy- ask things that are more mathematical! You know, primes, squares, cubes, things like that! I asked about even-ness and also (in our language) its congruence class mod various numbers. I was tempted to ask Does the number have any square factors? since this is pretty good for cutting the search space nearly in half (for 1,...,1000) but decided not to. I did get it in about 12 questions, but note that he really did have a number in mind and was not trying to maximize how many questions it would take me.

This leads to the following questions. The first one is easy to get matching upper and lower bounds. The second one I have an upper bound but no non-trivial lower bound. In all cases the number is between 1 and n and you want to minimize how many questions it takes to find the number.

1. If the game is restricted to questions of the form is x &equiv a mod b then how many questions do you need?
2. If the game is restricted to questions of the form is x &equiv a mod p where p is a prime then how many questions do you need?

The Singularity

Last Sunday the New York Times ran a front-page article Scientists Worry Machines May Outsmart Man that read a bit like a bad science fiction story about the dangers of computers that get too smart. The article reported on the AAAI Presidential Panel on Long-Term AI Futures that took place at Asilomar in February with many reasonable AI folks including a few that I know well, EC regulars Michael Wellman and David Parkes, my old NEC boss David Waltz and TTI-Chicago chief David McAllester.

McAllester chatted with me about the upcoming "Sigularity", the event where computers out think humans. He wouldn't commit to a date for the singularity but said it could happen in the next couple of decades and will definitely happen eventually. Here are some of McAllester's  views on the Sigularity.

There will be two milestones.

1. Operational Sentience: We can easily converse with computers.
2. The AI Chain Reaction: A computer that boot straps itself to a better self. Repeat.

We'll notice the first milestone in automated help systems that will genuinely be helpful. Later on computers will actually be fun to talk to. The point where computer can do anything humans can do will require the second milestone.

McAllester's arguments assume that humans are just fancy computers. Personally I believe we think in ways computers never can, in particular having a self-awareness and reasoning beyond the capability of machines and we'll never see a Singularity.

We are more than Turing machines.

Are you a firstblocker or a lastblocker?

A type of advertisement I think is very odd is the following:

Be the first on your block to have NAME OF PRODUCT!

It might be more honest to say

Be the first on your block to have NAME OF PRODUCT! Be our beta testers! A year from now you can have a better version at a cheaper price!

What are the PROS and CONS of being a a firstblocker (candidate for word-of-the-year) as opposed to being a lastblocker (another candidate)?

1. Advantages of being a lastblocker: you get a cheaper better version of the product. Or in some cases you realize that you don't want the product (e.g., Betamax, which were actually called that.)
2. Disadvantage of being a lastblocker: when do you finally buy the product? When I was a kid the first Polaroid Cameras came out. The innovation then was that they gave you the picture right away. It was in black and white, poor quality, and you had to shake it while it was developing. At the time I said I will wait until this is in Color. Once that happened I said I will wait until it is better quality. Once that happened I said I will wait until you don't have to shake it.. Once that happened I said I will wait until the price goes down. Once that happened I said I will wait until you can preview your shots before printing them out. Once that happened I said I will wait until you can do all of this on the computer. This has happened. Now I am waiting for the price to go down. Or the next innovation. Meanwhile, I have never owned a camera.
3. Advantage of being a firstblocker: you get to tell your friends about it and advice them. Lance has done that with Kindle, KindleDX, and the ultimate wallet. This is what the advertisement had in mind.
4. Advantage of being a firstblocker: There are times when the first model has some feature (or bug according to the manufacturer) that you want. One example: An older VCR can tape off on-demand, newer ones and DVD recorders have a problem with this.
5. Some of this applies to seeing movies their first weekend--- you get to tell your friends about it, but you may see some really bad movies. I'm a lastlastblocker: I tape movies off TV, watch the the first 15 minutes, and then decide if I want to finish it. (Ebert's Rule for Comedies: If you don't laugh in the first 15 minutes, you're not going to laugh in the last hour and 45 minutes.) If not I might go to Wikipedia to see how it ends.

Are you a firstblocker or a lastblocker? Of course, it may depend on the product.

QIP = PSPACE

A great new result in quantum complexity, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous have shown that QIP is contained in PSPACE solving a decade-old open problem. The Pontiff has already blessed this result but as someone who has studied both quantum and interactive proofs, let me give you my take. Steve Fenner gives a mostly non-technical outline of the proof below.

QIP stands for Quantum interactive proofs. That PSPACE sits in QIP follows from IP=PSPACE and the fact that quantum interactive proofs can easily simulate classical ones. QIP=PSPACE implies IP=QIP so classical interactive proofs can also simulate quantum ones. Amazing.

Old papers by Watrous and Kitaev and Watrous, and showed two already amazing results:

1. QIP can be simulated by 3-round quantum interactive proofs.
2. 3-round quantum interactive proofs can be simulated in exponential time.

The second result proven by creating an exponential-sized semi-definite program to capture the acceptance probability of these proof systems. 

In classical interactive proofs, if we could simulate unbounded rounds with bounded rounds than PSPACE would collapse through the polynomial-time hierarchy (highly unlikely). So while we now know classical interactive proofs can simulate quantum proofs they will need many more rounds to do it.

In an upcoming FOCS paper, Jain, Upadhyay and Watrous show that two-round quantum interactive proof systems can be simulated in PSPACE. QIP in PSPACE uses techniques from all these papers.

Still open: The power of multi-prover quantum interactive proofs where the provers share prior entanglement but otherwise can't communicate. Classically we have MIP=NEXP (nondeterministic exponential time). Does QMIP=MIP? Neither containment is known.

---

Here is Steve Fenner's outline of the proof. 

The proof that QIP is in PSPACE is in three distinct parts:

1. Reduce a given QIP protocol P to an equivalent semidefinite programming problem S. In other words, find a semidefinite programming problem S where the Verifier's optimal acceptance probability is the optimal solution to S.
2. Describe a high-level decision procedure for P based on computing a solution to S that is close to optimal.
3. Show that this numerical solution can be approximated to sufficient accuracy in PSPACE.

The proof relies in a crucial way on an earlier result of Marriott and Watrous (building on Kitaev and Watrous) that any QIP protocol can be simulated by a much simpler QMAM (quantum Merlin-Arthur-Merlin) protocol. In this protocol, which is a three-round quantum version of a standard Arthur-Merlin protocol, Merlin is an all-powerful quantum process and Arthur is a polynomial-size quantum circuit. It runs as follows:

• Merlin gives Arthur some quantum state r.
• Arthur flips a *single* coin and sends the result to Merlin.
• Merlin gives Arther another quantum state s in a different register.
• Arthur performs one of two possible measurements, based on the value of his previous coin flip. He accepts if the result of the measurement is 1 and rejects otherwise.

The proof actually starts with this equivalent QMAM protocol and turns it into a semidefinite programming problem in Part 1, above.

Every semidefinite program has a primal and a dual formulation. The primal is a maximization problem, and the dual is a minimization problem. In Part 2, the authors give an iterative process that finds better and better feasible solutions to both formulations simultaneously. Each solution approaches the optimal one, the primal from below and the dual from above, giving better and better bounds in both directions. The optimal value is Arthur's maximum acceptance probability over all possible behaviors of Merlin. They show that after a certain bounded number of iterations, the solutions are close enough to the optimal to correctly determine the outcome of the QMAM protocol.

Finally, in Part 3, the authors argue that the iterative process in Part 2 can be implemented efficiently to reasonable accuracy in parallel, using polynomial space. This follows from the fact that basic matrix operations (especially exponentiation and spectral decomposition) can be done in the class NC of polynomial-size log-depth circuits. Here the circuits work on exponential-size data (in the number of qubits), yet everything can still be executed using polynomial space.

One last comment: The proof improves upon and uses some techniques from a recent result of Jain, Upadhyay, and Watrous that two-message quantum interactive proofs are in PSPACE (to appear in FOCS 2009). The same basic technique was also used in a paper by Jain and Watrous in the most recent CCC conference, showing that another quantum class is contained in PSPACE.

Whither to Post, Tweet or Facebook?

On the blog we have a straightforward post policy, Bill and I try to make one post on nearly every work day. Occasionally we'll have extra posts for breaking news, mostly deaths and truly major new theorems. But occasionally we'd have short announcements or pointers. Sometimes we would pad a short item with an extra observation or I would sometimes just have a post with a long list of short items.

Right after STOC I started experimenting with Twitter and quickly got hooked. With no fixed schedule I can give quick tweets on anything that interests me or I think important for the community to know. Sometimes I can get what would have been a post down under Twitter's 140 character limit. So now I use the blog for longer posts and tweet the shorter stuff, using Twitter as an extension to the blog. 

Sounds ideal but there's a catch. Only a small fraction of you blog readers also follow me on Twitter. Some of what I Tweet would have been in the blog. So sometimes I need to repeat a tweet as a longer post or occasionally post a list of the more important and/or interesting tweets. What an excuse to do that now. 

• The new and improved ECCC 
• Just told that for recent stimulus-based grants: If it is determined that you are not spending quickly enough the funds can be revoked.
• Scan (11MB PDF) of shirt design from old Complexity conference (then Structures). Don't ask about the dog.
• Netflix contest over but no winner for a few weeks. Exciting conclusion (via:@ipeirotis)
• RT @statpumpkin: Bellkor's Pragmatic Chaos first place in Netflix Prize - contacted by Netflix and in validation phase. (thx @piggymurph)
• Tron returns and NYT worries about computers taking over. Coincidence?
• Iran has stopped issuing visas for US citizens including academics. The world got a little smaller.
• Rare CS article in Science Times: Destroying data with cryptography. 
• Faded lines on Beamer slides only draw attention to themselves (e.g. pg 2 of this)
• Congrats to Rafael Pass and Nothwestern's Nicole Immorlica new Microsoft Research Faculty Fellows.
• Comic Sans: Yes it looks handwritten. Cute the first 100 times I've seen it. Now go use a grown up font. (See also bancomicsans.com)
• Awesome EC Keynote by Michael Moritz on innovation. "Companies whither when scientists and engineers move further away from the helm"
• Moritz: Many best and brightest mathematicians and scientists waste their lives working for private equity houses.
• And from June 3rd: Taught Moser's proof in my intro theory course today! (A comment worthy to be my first twitter post).

Maybe I can talk Bill into Tweeting too. Imagine non-stop van der Waerden numbers. 

Now what about Facebook? In Facebook I can break my friends into roughly three groups.

1. Academics
2. Friends and Family
3. People I haven't seen in 25 years.

Problem is I have little to say to all three groups so I don't change my Facebook status often. Basically a few status updates about where I am traveling or some photos of the family. Facebook allows you to create groups of friends and show updates only within those groups. I need the opposite operation, creating status updates that only go out to a select group or groups. I'll likely use Facebook for my personal stuff, if you are in groups 1 or 3 and hide or unfriend me I won't be insulted.