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?