Resubmitting Rejected FOCS paper to STOC

(Guest post by Kamal Jain Resubmitting the rejected papers from FOCS to STOC?

If your paper was rejected by FOCS and you're submitting it to STOC, here are my thoughts on how you can increase your chances of acceptance. Given the low acceptance rate for FOCS, I am sure many of us will be resubmitting our rejected papers to STOC. Many of us will be incorporating the FOCS PC comments. And there's also a realistic chance that FOCS PC misunderstood our papers. So what should we do so that STOC committee does not repeat the misunderstanding?

Let me first describe the general methods to contain the chances of misunderstanding. I will then describe why the chance of misunderstanding has increased for STOC PC on resubmitted papers by giving you an insider view of FOCS 2007 PC. We can then discuss what we could do to minimize that.

Contain the chances of misunderstanding

Well of course removing the items from the paper which gave rise to misunderstanding could be beneficial. These items could arise either due to lack of explanation, positioning of clarification, or overselling the results. Lack of explanation happens because we fail to realize as authors that our mind is pre-conditioned while researching on the paper and the reviewer's mind won't be pre-conditioned in the same way. Therefore things which look clear to us may be confusing to a reviewer. Positioning of clarification is very important because not every paper is read word to word. So it is very important to put the clarification or a pointer to it as close as possible to the place where confusion could potentially arise. Overselling does not improve the chances of a paper getting accepted. Overselling of results typically puts the reviewer in a defensive position. A reviewer could look at other existing papers that have introduced similar techniques and be at a loss for what is new, unique, and real about what this paper promises.

So how do you address these problems? One thing is to prepare the paper early and seek feedback. Do not expect somebody, who is not genuinely interested in your work, to provide you good quality feedback for free. You would need to pay. How? Offer the same high quality service on their papers as you expect on your own papers. Posting your papers online, e.g., as a technical report in some archive could also bring some early readership, which may provide you feedback and opportunities to exchange feedback.

If you really need to sell your paper, what's the best way? Give talks -- as many as possible. Try to accept every invitation and try to get yourself invited by marketing the results. In order to market the paper be open to discussing your results in small chats without pen and paper, e.g., over a lunch table. Acknowledge all pre-publication discussions, including those which were not explicitly used in the paper. Mentioning the names of the people is very important, and in case of explicit usefulness, mentioning it explicitly is equally important too. This is so that your colleagues feel acknowledged and positively reinforced to collaborate with you in the future. In the short term, these colleagues are also likely to see the papers more positively vs the case if they find their assistance is not fully acknowledged.

What else can you do if you do not yet have enough opportunities to talk about your paper? We have not done so, but there are cheap as well as free software using which we can easily make a high quality screencast. For me personally, a high quality screencast provides 80% of the benefit of watching the talk in person. Much of the benefit of the remaining 20% can also be obtained if there is an open forum associated with the screencast to ask questions which can either be answered by the authors or other viewers in a relatively short time. Readers do not have the patience unless they are genuinely interested in your result. And expect to count the number of the latter on your fingers.:)

An insider's view of FOCS:

What's specific about paper reviewing these days? As part of the FOCS committee we had access to reviews submitted by the previous STOC committee. We paid a great deal of attention to whether the version we had had responded to the STOC PC's reasons of rejecting the papers. Similarly expect STOC 2008 PC to have FOCS 2007 PC's reviews available. The intersection between STOC 2008 PC and FOCS 2007 PC is non-empty. Even if you think FOCS PC misunderstood your paper, and responding to those misunderstandings would make the paper less readable, you should still try to respond to those misunderstandings instead of ignoring them. In such cases you can respond to those misunderstandings either in appropriate footnotes or in a one page appendix in the end. If your footnotes and appendix are just for STOC PC, do mention "for the reviewers only, will be removed from the published version."

What about the feedback that FOCS PC kept confidential and did not transmit to the authors? This part of the feedback must not be used by STOC committee for three reasons. First, it was understood that only FOCS PC share that feedback. Second, this part of the feedback was a part of the process and not the net outcome. The net outcome ideally must be included in the "send to author" part of the feedback. Third, since this part of the feedback was not transmitted to the authors, they can't be expected to respond. If this part of the feedback did contain a reason why the paper should be rejected then authors must be sent the reason. If this was not done in some cases, then STOC PC must work hard to rediscover the same reason for rejection.

This is my view from both having submitted (and received rejections) papers as well as been part of various PCs. I hope these give you additional practical tical tips on how to best position your papers. I welcome other ideas so that we could continue to improve the quality of our submissions.

Thanks,

Kamal Jain.

Note: FOCS means FOCS 2007. STOC means STOC 2008. Previous STOC means STOC = 2007.

It was a stupid question!!!!!!!!!! or...

On my last blog I asked the following: TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same color such that x+y=z+w.

And I pointed out that when I asked this in seminar I got 5 thought it was TRUE, 4 thought it was FALSE, 5 thought it was a STUPID QUESTION.

The answer is: ITS A STUPID QUESTION. More rigorously the following is true and was proven by Erdos:

The statment above is true iff the Continuum Hypothesis is false. (See this (pdf) or this (ps). for an exposition of the proof.

SO, what to make of this? This is a natural question that is ind of ZFC. How Natural is it? Erdos worked on it, not some logician looking around for a problem to be ind of ZFC.

Does this make us think CH is true or false? Actually, more is known:

Let L(x₁,..., x_n) be a linear form over the reals (but not x₁-x₂). If CH is true then there is a coloring of the reals with a countable number of colors such that there is no e₁,..., e_n which are all the same color such that L(e₁,..., e_n)=0. (Exposition of proof in same document linked to above.)

If CH is true then the entire theory of countable colorings and linear forms is known. And boring. If CH is false then much more interesting things happen. Jacob Fox proved the following:

Let STAT(s) be the statement

For every coloring of R with a countable number of colors there exists x₁, x₂, ..., x_{s+3} such that they are all the same color, and x₁ + sx₂ = x₃ + x₄ + ... + x_{s+3}

THEN STAT(s) is true iff 2^ℵ₀ > ℵ_s

Jacob Fox is also (judging from his resume) not a logician. He is a combinatorist. Actually he's a graduate student so it may be too early to say what he is.

To determine CH should we use its consequences as reasons for or against assuming it? Even if we do, do you want the entire theory to be known and boring? I ask this non-rhetorically. See Opinion 68 of Zeilberg's blog or The papers of Penelope Maddy: believing the axioms I. and believing the axioms II.

Equations and Colorings: Rado's theorem

Is the following TRUE or FALSE?

For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x-6z = 0

It turns out that this is FALSE. We'll call a set b₁,...,b_n REGULAR if

for every c, for every c-coloring of N, there exists x₁,....,x_n such that x₁,....,x_n are all the same color, and b₁x₁ + ... + b_nx_n = 0

The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.

(b₁,...,b_n) is regular iff some nonempty subset of the b_i's sum to 0.

For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW- here is a question to which the answer is known, and I'll tell you the answer in my next post.

TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,w x,y,z,w same color x+y=z+w.

When I asked this in seminar I got

1. 5 thought it was TRUE
2. 4 thought it was FALSE
3. 5 thought it was a STUPID QUESTION.

Do we root for how a problem will go?

When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:

A 3-free set is a set with no arithmetic progressions of length 3. Large 3-free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n^1-o(1) but there cannot be such sets of size &Omega(n) (slight tighter results are known).

I was finishing up a paper on large 3-free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3-free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):

The known algorithm uses that there are 3-free sets of {1,...,n} of size n^{1-o(1)}. Improvements to the current constructions of large 3-free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to be

Actually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on- some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?

I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.

Stoc seeking papers that...

STOC deadline is coming up and the organizers have asked me to publicize a particular aspect of it. Note that in the call for papers it says: Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged

Since I was explicitly asked to publicize this, I assume they really mean it.

Submision Deadline: 7:59PM, EST, Nov 19.

THANKS to Nicole's FOCS blogs and her positive outlook

I want to extend a warm thanks to Nicole Immorlica for Guest blogging from FOCS. So I will:

THANK YOU NICOLE!

(Would have done this yesterday but if I had delayed getting the WOLFRAM PRIZE information out there I would have gotten at least 10 more emails telling me to post it.)

The one thing that struck me the most about Nicoles FOCS blogs is the positive outlook usually missing from discussions about theory. If you look at this blog, other blogs, or just talk to people in theory, you usually read or hear negative comments like these:

1. FOCS is biased
2. STOC is too expensive
3. Theory is underfunded
4. Australian actresses are plagiarizing my quantum mechanics lectures to sell printers.
5. Back in the good old days people worked on important problems. Now they just get incremental results.
6. Bring back Lance!

Some of these complaints are certainly valid. But hearing or reading such negativism can be monotonous, and blind us to some positive developments. Hence I appreciate Nicole's positive outlook on FOCS and Theory in general. I hope it lasts her entire career.

Wolfram Prize won!- There IS a (2,3)-UTM

Recall that the Wolfram Prize which I blogged about here, was given to anyone who can determine if a certain Turing Machine was universal. It is now known that YES that machine IS universal.

Congrads to Stuart Kurtz, Lance Fortnow, and Kathryn Cramer, Jon Katz, and Katrina LaCurts- NOT for winning the prize but for being the first ones to tell me who won the prize so I could post it. For that they win... a mention in this blog.

Here are some websites about it, most of them emailed to me by Kathryn Cramer.

1. write up in nature
2. Stephen Wolfram's blog!
3. Smith's 44 page proof!
4. New Scientist Story
5. Alex Smith's Photo!
6. Geomblog scooped me here
7. Live Journal

BACK TO BILL:

How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important.

FOCS VIII

Nicole's final FOCS post.

And it's over! The 48th FOCS ended at 6.10pm with a talk on "The Computational Hardness of Estimating Edit Distance". About 50 brave souls lasted the whole three days.

Overall it was a really great FOCS. The results were good. The company was good. I have to admit, even the food was generally pretty good!

See you all next spring at STOC in Victoria.

FOCS VII : Funding? NSF? whats it all about?

(Another Guest post from Nicole!) More from the Business Meeting

Funding status report: I'm not really the right person to blog about funding since I have never yet applied for a grant. From the business meeting, it seems like a lot of people are doing a lot of hard work to funnel more of the NSF budget into our hands. They seem to have had some success. There are two new initiatives -- CDI, Expeditions -- and several old ones which now have more money than before -- ToC, SING. Funding rates seem to be around 25% (33% for CAREER). (An aside, maybe we should also try in an organized way to funnel more of the federal budget into the NSF by, e.g., writing our representatives in congress -- you don't have to be a citizen to do this -- or through PR campaigns.)

But you can find all this info on the NSF website. What you can't find on the NSF website is how it affects us young academics. I am about to start my first faculty job, and funding has suddenly become a very real issue for me. I see these numbers, I hear about these politics, and I am totally in the dark. I have never written a proposal, never even read a proposal. I don't know how to play the game. I know my senior colleagues will help me through this process, but that does not reduce the anxiety. I suppose every career path has rites of passage like these. The thing is some rites of passage are fun. I could be wrong, but I'm not looking forward to this one. ~

FOCS VI- Local Arrangements AND the future of FOCS!

(Another Guest post from Nicole!)

The business meeting was fun thanks to Mihai!

Local arrangements: First, let me say how wonderful the local arrangements were this year, a sentiment I've heard from many others here. Thanks so much for making this FOCS happen.

Claire gave a very detailed account of the local arrangements. The general message seemed to be that things are expensive. Expenditures this year reached $100K. The usual culprits were at fault -- food ($265 per person, total of $66,000), paper proceedings ($32 per person, total of $11,700), PC meeting/registration fees ($12,000), room/equipment rental ($4,200). Everything sunk in when it was announced that we're looking at a $525 registration fee for STOC 2008 in Victoria, admittedly thanks in part to the falling dollar.

The usual debates ensued -- paper vs CD vs online proceedings, catered lunch vs on-your-own, alternate conference venues. Let me capitalize on my journalistic duties to further my personal opinion on these matters: online proceedings (and ideally someday online PC meetings) are much more environmentally friendly. For me, this is enough. But, besides environmental and monetary costs, online proceedings are also easier to access after the meeting and can include media beyond print, e.g. slide presentations, videos of talks, etc. (see, for example, the excellent wiki of FOCS 06 built by Amin Saberi). People who really want paper proceedings can go to Kinko's with a printout of all the papers and pay $50 to bind them.

But honestly, I'm getting tired of this annual debate. Let's just do it my way. ;)

FOCS V- Report from Prog Comm.

Another great guest post from Nicole Nicole Immorlica, from FOCS

(Note from Bill G: This is one of several posts Nicole will be making from the Business meeting.)

Program committee report: Another congrats is in order. No matter what you think about the distribution of topics (see below), you can't deny that the PC did a great job this year. I was especially impressed by the extensive feedback, both internal and external, on submissions; the comments were thorough and explicitly stated the PCs reasons for their decision. Now for the statistics, well, here's the list that was presented at the business meeting: The number of submissions: 302. The number of accepts: 66. Below is a topic that there were papers submitted on, followed by how many submitted,and how many accepted.

1. Algebraic/Numerical Computation (14, 1)
2. Algorithmic Game Theory (27, 5)
3. Algorithms 85
   1. Approximation (35, 9)
   2. Geometric (8, 2)
   3. Graph (17, 1)
   4. Randomized (14, 4)
   5. Streaming (6, 2)
   6. Misc. (15, 0)
4. Combinatorics (2, 0)
5. Computational Biology (2, 0)
6. Computational Complexity (30, 14)
7. Cryptography (20, 7)
8. Data Structures (6, 2)
9. Geometry (13, 3)
10. Learning (7, 0)
11. Logic/Proof Complexity (11, 2)
12. Parallel/Distributed Computation (15, 1)
13. Property Testing (10, 5)
14. Quantum Computing/Crypto (25, 6)
15. Random Structures (7, 2)
16. Misc. (11, 0)
17. Out of Scope (6, 0)
18. P = NP (1, 0)

I think I'll leave it up to the commentators to interpret this.

FOCS IV

(Even More from Nicole Immorlica, guest-posting from FOCS. This post is from Oct 22, 7:00PM)

I remember taking writing classes in high school. We had a series of assignments emphasizing different writing techniques and topics. But each assignment started with the same question, the question which set the tone for the entire piece of work. Who is your audience? The importance of this question was the most valuable lesson I learned in those classes.

I've now attended about a quarter of the FOCS talks -- all the ones close to my area and a smattering of those completely outside my area -- and it seems to me that there are two types of audiences in every talk. There are the locals, those that are intimately familiar with the research area of the talk; and there are the tourists, those that want to explore something new.

How do you speak to such an audience? Most speakers seem to split the talk into two parts: accessible introduction/overview/problem statement and area-specific implications/proof techniques. And then they have to pack it all into 20 minutes. The result? Minds wander. What can be done about this? Longer talks to allow for a smoother ramp-up to the technical details (and hence fewer papers overall)? Parallel sessions (something FOCS has toyed with in the past)? Or maybe nothing? As my grandmother used to say, "you can please all of the people some of the time and some of the people all of the time but never all of the people all of the time."

FOCS III

More from Nicole Immorlica from FOCS.

The first day of FOCS is over. The highlight of the afternoon was the talk by Nancy Lynch, winner of the Knuth Prize. She began with, as one attendee put it, a nostalgic synopsis of FOCS/STOC from her first Denver 1972 conference in a cheap hotel across from a dirty movie theater on through the splintering of theory and distributed computing in the 80s. She then launched into a very accessible description of her famous paper on the impossibility of distributed consensus. The talk ended with an overview of current and future work in the field.

I think everyone in the audience was pretty satisfied with her outlined research agenda involving models of distributed computing on mobile networks until the air traffic controller example. She primed us by suggesting that her research could replace traffic lights with virtual traffic lights, which made me tense up slightly. Then she suggested we could even replace human air traffic controllers with virtual ones. While we all understand the benefits (e.g., you can have controllers over the ocean, machines don't get tired, etc.), I think we all had a sort of collective gasp. I guess at the end of the day, I just want to know there's a human behind it all, attentive and directly in charge.

One more thing I think is worth mentioning – this is the first Knuth prize (out of 8) awarded to a woman. This same year was the first year (out of 41) that a woman, Fran Allen, won the Turing award. This trend is both alarming (it took 41 years?) and encouraging (ample research and personal experience demonstrates the significance of female role models for professional women). Congratulations and my sincere gratitude to you both for paving the way.

FOCS II

Nicole Immorlica continues to blog from FOCS.

Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog about are those I happened to attend and should not be interpreted as the "best" or even my personal "favorite" results, etc. etc. etc.

So about the sessions. Session one started at 8.30 AM and I'm embarrassed to admit that despite being the "guest blogger" of FOCS I missed the first talk. Somehow research before 9.00 AM is akin to hard liquor before breakfast for me. I just can't stomach it. I caught the end of the talk though, and was shocked that the room was packed! I took a picture, try and see who isn't there. :)

The second session was much closer to my research area – algorithmic game theory – and hence I got much more from those talks. One particular nice result was that from the paper Mechanism Design via Differential Privacy. The authors introduce a new solution concept for mechanism design which resolves many of our frustrations with dominant strategy mechanism design, and they do so through a creative connection to a seemingly unrelated field – privacy.

FOCS I

Nicole Immorlica guest posts from FOCS.

I wake up bleary-eyed and jet-lagged at 6 AM begging of myself WHY? Why do I subject my body to such torturous trans-atlantic flight for three days of, of what? Of talks of which I will attend at most a quarter? Of hotel banquet food? Of aching back muscles from lugging around massive proceedings and laptops bundled together in free canvas tote bags that I don't really want anyway?

For me, the answer is the people, my friends, my colleagues, their quirky interests and insightful comments. It's the research in the corridors, the animated technical arguments over the lunch tables, the great stories that get told by a diverse set of people from a diverse set of backgrounds.

Basically, it's like a big family reunion. But families you are born into. How do you get born into the FOCS family? I remember my first FOCS – Las Vegas 2001 – feeling alone, isolated, shy. Now I feel a part of the family, accepted into this community due in part to my papers, yes, but also labels that were really a matter of luck. What becomes of all those people that didn't have my luck?

Why do I find this result interesting- MOD 17 SAT

I find the following result to be really interesting but can't quite say why: (For this exposition ≤_m means poly-m-reduction)

Let SAT₁₇ be the set of formulas such that the number of satisfying assignments is a multiple of 17.

If SAT₁₇ ≤_m S, S sparse, then SAT₁₇ ∈ P.

This is one of those results where the proof in the literature is hard because they prove something far more powerful (btt reductions- and more). Hence I have my own exposition that I made for my class here.

I presented it in class recently and the students questioned why it was interesting. I can usually answer questions like this (even about such things as the Polynomial VDW theorem) but this one is harder to say. I DO find it interesting (not just the proof, but the result) but can't quite say why.

SO, here is my challenge: either tell me a reason the result is interesting OR tell me a result that YOU find interesting but can't quite say why.

A more intelligent SPAM discussion

I wish to start a more intelligent discussion of spam then my last post lead to (my fault). And YES, the story I pointed to was a hoax.

Is Spam a big problem? I contend that it is and that it is going to get worse. Some random thoughts, some of which are what to do about it.

1. Make it illegal or make the penalties tougher. I don't know what the current legal status is, but even with tough laws this is hard to enforce because (1) What is spam? and (2) it would require international cooperation.
2. We could try just making spam that is trying to rip you off illegal. I'm sure it is. But sometimes its hard to tell what is a rip off and what is not. The ``Nigerian Billionaire'' scam is clearly a ripoff (does anyone still fall for that?) but the ``you can get viagra at a cheap price'' might not be. The ``we can get you out of debt'' is much harder to judge since (from what I understand) they pay your debts, charge you an enormous interest, but let you pay it off over a much longer period of time. It may well be legal but unethical. It may even be legal and ethical.
3. Keep designing better software to block spam. This is the current solution, and it works pretty well, but its getting harder, and too much real email is being blocked. Also, this is more of why I think its a big problem- we (as a society) spend an awful lot of time and effort on this.
4. As more people know that these are scams and less people fall for them, will the scam-spams stop? Can we educate people so they know better?
5. Fighting back- there was an article in the Atlantic Monthly about people who scam the scammers- with success. But there are not enough of them, and they are not that effective, to be a real deterrent.

So there are essentially legal, technical, and educational solutions. Are there others? (NOT including assasination.) Can they work? Who is winning this war? How can we tell?

Spam Assassin

In Russia a notorious spammer was assassinated

Is this a crime? Should it be? Consider the contrast:

1. Killing one person. How many people suffer and how much? The victim of course. Maybe his family and friends. But not that many people. So this is High Impact on a Few People.
2. Spamming 100,000,000 people. How many people suffer and how much? Far more than 100,000,000 suffer. Why so many? The following suffer:
   1. Software is more expensive because you need to put in spamassassin's.
   2. People who send legit email that is blocked. This has caused confusion not worthy of a bad sitcom.
   3. The people who fall for these spam-scams.
   4. The Nigerian billionaires who really do want to give me $5,800,000 dollars. Its hard to tell the real ones from the fake ones.

So, how to measure the cost-benefit of killing this spammer?

{ s₁, s₂, ..., s_n } is the people that suffer by the spammers death. Person s_i suffers a_i.

{ t₁, t₂, ..., t_N } is the people that suffer by the spammers action. Person t_i suffers b_i.

Its safe to assume that n is MUCH LESS THAN N and that b_i is MUCH LESS THAN a_i. If

a₁ + a₂ + a₃ + ... + a_n < b₁ + b₂ + b₃ + ... + b_N

then the spam assassin should not be charged with a crime.

The more serious question here is how to deal with spammers who transcend boundaries and seem outside of the law. The Russians may be onto a solution...

Is Computer Science a Science?

Is Mathematics a Science? Is Computer Science a Science (hmmm- it has to be, its in the name :-) )? Is Richard Stallman a computer scientist? How about Bill Gates? How about my wife who has a job programming? For a serious discussion of some of these issues see an blog of Lance's For a less serious discussion, I offer the following thoughts.

1. Calling something science, engineering, art, or business is not an insult or a compliment.
2. A topic is a science if it has a lab where there is the potential for danger. Physics has radiation, Chemistry has explotions, Biology has germs. So they are sciences. Neither Math nor Computer Science has those.
3. Hence, asking if Richard Stallman is a computer scientist is not really a question. So perhaps we need a different term. `Computer Programmer' is a fine term and we know what it means. How about if we call ourselves `Computer non-programmers'? Depends if you consider LaTeX a programming language (it is Turing-Complete).

The Free Software Foundation and Richard Stallman

Richard Stallman gave a talk at University of Maryland at College Park. He is the head of the free software foundation. The terminology `free software' does not mean that software should be given out for free. It means that once you buy software you should have the right to use, study, copy, modify, and redistribute it as much as you like. EMACS, which he wrote, has this kind of license. So does GNU which is an FSF project. The talk was pretty good. He made some valid points about the evils of the current system. I think he has some good points to make.

1. He talked for 1 hour 45 minutes. This is probably 45 minutes too long.
2. When I say he talked for 1 hour 45 minutes I am being literal- no slides, no blackboard presentation, just talking. This may be because to use technology he would have had to use Software from a company that he does not approve of.
3. He speaks of free software as a human right. He speaks of it as the worst evil in the world. There are worse evils in the world; however, all good causes need true believers, and he is one.

I've heard all this before and further ago than most people. In 1982 he was my housemate in Graduate School. He had some of these ideas then, but they are better develped now. I sortof wish I had gotten involved with Free-Software early on since its a good cause and it would be nice to be able to contribute to society in this way.

P.S. Richard Stallman is not the most famous computer scientist who knows me. Serge Brin, co-founder of Google, had two courses from me as an Undergraduate. I definitly wish I had gotten involved with Google early early on since its a good product and it would be nice to be able to contribute to my bank account in this way.

If pigs could fly then bacon would be cheaper

Pretend you didn't know the Karp-Lipton theorem. Consider the following two statements

SAT has poly size circuits.

The Poly Hierarchy collapses.

You probably think both are false. Which statements truth would surprise you more? Personally I think SAT has poly size circuits would surprise me more.

Karp-Lipton Theorem:

If SAT has poly size circuits then Poly Hierarchy Collapses.

Does this really make your belief that SAT does not have poly sized circuits stronger? You already believed that. I know of one theorists who tells me that she believes SAT does not have poly sized circuits MUCH MORE than she believes that PH does not collapse. Hence this theorem does not tell her anything.

If you have

(unbelievable statement A) --> (unbelievable statement B)

what do we then know that we didn't know before? We know that A is MORE unbelievable than B, I suppose. We seem to have taken

BLAH --> P=NP

as the gold standard in showing that we believe BLAH is false and

BLAH --> PH=\Sigma_2^p

BLAH --> PH=\Sigma_2^p

etc. as forming a hierarchy of non-belief.

This is a nice picture, but it may be that BLAH is just not that believable in its own right and does not need to imply something like $\PH = \Sigma_3^p$ to give NOT(BLAH) street cred.

Deal-No Deal: MORE $ = LESS Interesting

I caught an episode of DEAL-NO DEAL recently (see this for a description). The math behind this game has been described in blog postings of Lance (see this as well as the above link)

The episode I saw showed something wrong (at least in my opinion) with the way they are promoting the show during premiere week. They have upped the amount of money to be a max of $4,000,000 (instead of $1,000,000). I saw the following (this might not be quite accurate but makes the point) There were 6 numbers left:

1. $5,000
2. $10,000
3. $20,000
4. $100,000
5. $1,000,000
6. $4,000,000

and the bankers offer was $700,000. $700,000 is so large and so life changing that the decision to take it (which she did) is rather obvious. Even the audience WAS NOT yelling `NO DEAL! NO DEAL!' like they usually do. To exaggerate this, imagine if the top amount was $40,000,000 and your dilemma was whether to take $7,000,000 or risk it to maybe do alot better but maybe do alot worse. YOU WOULD TAKE THE $7,000,000. (or at least I would).

A question like `would you take $70,000 or take the chance that you get $400,000' is mildly interesting. But the $700,000 is to large to not take. Hence the game gets less interesting mathemtatically.

Given a persons utility function (or something like it) what would be the optimal max amount (and optimal set of amounts) to maximize the games INTEREST? This question might be interesting.

WHERE to apply to grad school?

Its the time of year when Seniors who want to go to Graduate School should be pondering WHERE to go. There are other issues which I will address in later posts, but

Today's topic is WHERE TO APPLY?

I would like YOU (the readers, and time magazines MAN OF THE YEAR for 2006) to comment on:

1. IF a student wants to do COMPLEXITY THEORY where should she go?
2. IF a student wants to do COMBINATORICS (in a math dept) where should he go?
3. IF a student wants to do XXX (in a YYY dept) where should ZZZ go?

Note that there may be lesser-well known schools (e.g., not on someone's arbitrary top 10 ranking) that are really good in these topics, and they should not be overlooked.

Andrej (Andrey) Muchnik-a late memorial

(Guest Post by Alexander Shen. Thanks to Lance for Suggesting it.)

Andrej (Andrey) Muchnik died unexpectly last March, but the news didn't spread out, so I am thankful to Lance Fortnow and Bill Gasarch who give me the opportunity to write a few words about him. His death was a sudden blow not only for his family (his parents, Albert A. Muchnik, of Muchnik - Friedberg solution of Post problem, and Nadezhda M. Ermolaeva; both were students of Petr S. Novikov; and his brother Ilya) but also for all his colleagues.

Andrej, whom I knew since our undergraduate studies, was not only the brilliant mathematician, but a deep thinker. He lived in his own world -- a very rich one that was not completely unrelated to a "real life" (i.e., the mess around us), but still clearly separated from it, and the interactions between these two worlds were quite difficult and often painful. His mathematical interests were driven by internal logic of the subject, not the current "fashion"; sometimes he rediscovered an old result not knowing about it; at some other times his results (being not published or published only in a short note) were rediscovered later by others. Probably his most known result is an elementary proof of Rabin's theorem (decidability of second-order monadic theory of two successors), invented while Andrej was a fourth-year student, and its generalizations; my personal favourite is one of his last results saying that for any strings A and B there is a string C such that |C| [length] is about K (A|B) [conditional Kolmogorov complexity]; K(C|A) is negligible and K (A|B,C) is negligible (all up to logarithmic terms).

a seminar in Moscow that was started by Kolmogorov himself; the work of this seminar and its participants was deeply influenced by Andrej, and I think that all we agree that most non-trivial ideas discussed in this seminar and most interesting results obtained by the participants of the seminar were due to Andrej (or at least inspired by him). Personally I am extremely grateful to him for all his support and encouragement and very sorry that I didn't tell this to him explicitly and didn't help him enough while he was alive.

See the seminar site note (both Russian and English) (written mostly by Andrej's teacher and friend, how helped him a lot, Alexey Semenov)

some papers of Andrej (not all -- we are still trying to prepare some unfinished papers for publication) can be found here

The Amish and Cell Phones

As most people know the Amish avoid using certain technologies. They think that some technologies are disruptive to the community. In the past the Bishops would meet and decide if a certain technology is okay to use. They do not use electricity over wires, but batteries are okay. However note that with electric wires or phone wires or cars (which need roads) the Amish Bishops can enforce their decisions. Not so anymore.

A long time ago they banned phones. They later made some allowances for having a phone booth for emergencies, but no phones in the house, for it would disrupt family time (the ultimate DO-NOT-CALL list). But more and more Amish are doing business with the outside world and as such phones are needed. More and more of them are using Cell phones (see Look whose talking).

I do not think Cell Phones are the real issue here. The real issue is that we now have technologies that an individual can use without the permision of the community. We also have dual-use technologies, so rules like `you can use it for business but not for entertainment or gossip' may be hard to control.

I was told by an Amish Man that the Bishops have ruled against Cell Phones and computers. But as batteries get better (and most of them have contacts on the outside who can recharge for them) I'll be curious how well this holds up. Will the authority of the bishops and the desire to hold the community together be enough to make the rules self-enforcing?

Math on TV

There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned  the kruskal count. This is a card trick invented by Martin Kruskal. His son Clyde Kruskal is in my dept. Martin passed away in late December of 2006 and it is likely they put that reference in as a tribute. (See this and this for comments on the memorial service.) I watched the episode with Clyde. The good news is that YES, they did indeed mention The Kruskal Count and thats kind of cool seeing someone you know mentioned on NUMB3RS. The bad news is that the reference made no sense whatsoever. Here are two items that make as much sense as what they said.

1. The list of suspects looks random but we know that its not. To solve the case we use the Nisan-Wigderson derandomization technique.
2. We know the murder took place within this 5 block by 5 block area. We know that there were 10 people interacting to plan it. We can solve the case by looking at both the space and the interactions and then applying the Lund-Fortnow-Karloff-Nisan theorem that changes space into interactions.

If math you did was on a TV show, would you mind if they got it completely wrong? Personally, I would not mind that, I would be delighted (and surprised) to find my name on TV. A bigger issue- if it was a bad episode I really would not like that since I would probably want to show it to friends and family, and I would not want to subject them to bad TV. (The episode of NUMB3RS with Kruskal Counts was a terrible episode.) SUGGESTION: Take some math that you have done and see if you can find a way to make it fit into an episode of NUMB3RS It does not have to make sense, but it should sound like it does. (As I did above.)

Is Immunity Interesting?

In my graduate complexity class I proved

For all computable T there exists a decidable set A such that A ¬in DTIME(T(n)).

I then had on the homework

For all computable T there exists a decidable set A such that, for all Turing Machines M that run in T(n) time there exists an infinite number of strings x such that A(x) &ne M(x)

I then had extra credit

For all computable T there exists a decidable set A such that, for all Turing Machines M that decide A, for almost all inputs x, M(x) takes more than T(|x|) steps.

Katrina LaCurts, one of my students (who is thrilled to be mentioned by name in this blog!) asked the following: Is the HW and Extra Credit just to reinforce knowledge OR is the notion of differing infinitly often an important topic within complexity theory?

How important is the notion of sets differing infinitly often? A quick-and-dirty measure is to find the number of papers on this topic. A quick-and-ditry way to do that is to grep `immunity' in Joel Seifras's Theory Database and then edit. Once done I get the following list

So I could answer Katrina, there are at least 21 papers on this topic That shows people have worked on it (and some quite recently) but does not quite answer the question. Hence I ask my readers:

Once we have that, for all time bounds T, there is a computable set A ¬in DTIME(T(n)), why do we care about getting an A that differ infinitely often, or other variants? More generally, why is the notion of having two sets differ infinitely often important. I ask non-rhetorically and politely. Note that, no matter how you answer, Katrina still has to do the HW.

Question and Metaquestion about Students emailing you problems

I recently got an email that said roughly the following:

Hi Bill,
I am a grad student in combinatorial optimization, and I have a question that I was hoping you could answer: does "FOO is APX-complete" imply "FOO is MAX SNP-complete", vice-versa, or neither?
To be honest this might be very simple... but given that this is essentially the domain of computational complexity I was hoping that either you would know the answer, or otherwise that your blog's readers might have some suggestions. (Basically your blog is currently the main source of computational complexity to my brain, so it seemed natural to ask you when I became confused.)
My impressions from reading up are the following:

1. APX is the subset of NP optimization problems with constant-factor polytime approximations
2. MAX SNP has a much more complicated definition
3. APX contains MAX SNP but I don't know if the containment is known to be strict

To motivate my question, many papers say "the FOO problem is MAX SNP-hard and also APX-hard" but is there currently a point in stating both? As I researched the topic, I found that the reductions allowed in the definition of "APX-hard" and "MAX SNP-hard" are apparently slightly different... and around here my confusion set in.
One compendium, at least, uses simply "APX-hard" by convention: here
I hope this is up your alley, but if not then no worries.

Sincerely,

NAME DELETED FOR THIS BLOG POSTING

This email raises several questions and metaquestions

1. The question on APX might be interesting.
2. Is this a HW question? Is she cheating on it by asking me? Should I answer it? My inclination on this one is that its NOT a HW, it is legit. However, I don't know the answer, but if one of you does, by all means post (she knows I am posting this to the blog). By contrast, someone once posted to a readnews group (remember those?)
   Someone out there please help me with this problem: why is {a^n | n prime} not regular? I'm not a student asking for the solution to HW 4, problem 2. Honest I'm not!!
   Looks like a student doing a HW problem.
   
3. ``your blog is my main source for complexity theory'' A scary thought. She needs to get more sources- like Luca and Scott's blog. Or maybe books (remember those?).

SODA papers are out. Plus...

Request: If you want me to post a CALL FOR PAPERS or LIST OF ACCEPTED PAPERS or whatnot for a theory conference or some other conference, please email me and I will almost certainly do it. Not so good to make the request in a comment to another posting since some people do not read the comments (gee, I wonder why :-) ) For those who did not read the comments from yesterdays blog, SODA paper list is out and is here

This raises the questions of which conferences have the most complexity theory in them (say by percent). Here is my rough guess.

1. COMPLEXITY
2. MFCS
3. ICALP
4. FOCS/STOC
5. LICS has an occasional article on descriptive complexity)
6. SODA has an occasional lower bound. The few SODA papers I've been asked to subreferee have all ended up being rejected. The very fact that I am being asked to subreferee is an indicator that they are out of scope.
7. COLT/ALT and the other Learning Theory Conferences.

If I left out your favorite conference, sorry about that.

Search Engines gone wild!

I was curious if my monograph Bounded Queries in Recursion Theory was still available so I went to amazon.com and typed in `William Gasarch'. It had 40 hits. (Move over Stephen King!) I have only written one book, so how is this possible. Here are some of the hits.

1. Bounded Queries in Recursion Theory by Gasarch and Martin. This hit makes sense.
2. Handbook of Discrete and Combinatorial Mathematics edited by I have a 4-page chapter on computability. Does this hit make sense? If I say NO then I have to say say how long a book chapter has to be before it makes sense to have a hit. So I'll say YES.
3. The Complexity Theory Companion by Hemaspaandra and Ogiwara. I was acknowledged in the acknowledgments. Is this hit deserved? NO! (I got quite a few more of these types of hits, some for proceedings where one article acknolwedged me.)
4. An Introduction to Quantum Computing by Pittenger. This book is in the same series as my Bounded Queries books, so the back of the book has a list of all the books in this series. Hence I got a hit. This is nuts!

amazon needs to fix its search engines to be LESS good. ~

Quantum Computing and Quantum Phy.

I have been told quite often that

You don't have to understand Quantum Mechanics to work in Quantum Computing.

Thats a good thing since I've also been told

Nobody really understands Quantum Mechanics.

I've also been told

You don't have to have studied Quantum Mechanics to work in Quantum Computing.

I am skeptical of that. However, I was wondering about the other end- if you do have a background in Physics does it help? So I asked Fred Green (of Green's Conjecture) about this since he has a PhD in Physics, works in a computer science department, and works on Quantum Computing. Here is what he said.

Learning quantum computing helped me understand quantum mechanics better. As a physicist I never thought about measurement theory or entanglement, which were foundational issues, irrelevant to what I was doing. In quantum computing, we reason directly about these things all the time.

He didn't quite answer my question, but he raised a more interesting question. Should quantum physicists learn quantum computing?

In an earlier post I noted that Jerry Seinfeld said Comedians should do lots of proofs. Not for their actual routines, but to better practice their craft. Perhaps its also good advice for people who want to be quantum mechanics (like auto mechanics, but on smaller cars) to learn some Quantum Computing. Not for their actual research, but to better practice their craft.

Social Process and Proofs of Theorems and Programs

How does a theorem get to be believed to be true? There was a paper on this in 1979, Social Processes and Proofs of Theorems and Programs by DeMillo, Lipton, and Perlis. The paper had several points to make:

1. When a theorem in math is proven that is just the start of the process. If it is important enough it will be passed around the community and checked and rechecked. At some point if it survives scrutiny it will be accepted. (Makes you wonder about proofs in the literature that nobody reads- could they be false?)
2. The people working in Program Verification want to give program-correctness the same confidence that we have in Math Theorems.
3. This is not a good idea since Programs cannot be passed around the same way Math Theorem proofs can. (Makes you wonder about the Classification of Finite Simple Groups, or the Four Color Theorem which also cannot be passed around that easily.)

The comments on Program Verification do not really apply anymore since those people seem to have scaled down their claims to building tools to find bugs, and to automatic verification of Protocols written in a SPEC language, which seems far more plausible. (I'm not in the Program Verification Field so if someone wants to tell me I'm wrong, leave an intelligent comment.)

When I first read this article as a young grad students I was very impressed with what it said about math. YES, the proof is just the beginning, but constant checks and rechecks are needed.

The Koblitz Controversy: A reaction

(Guest Blog by Jonathan Katz on the Koblitz Controversy)

Like many others, I was very upset by a recent article by Neal Koblitz that appears in the Notices of the AMS. I'll say at the outset that I actually think the earlier papers by Koblitz (and Menezes) contained some valid points --- I don't agree with their conclusions, and I find their tone objectionable, but I still think they raise some issues worthy of further thought.

What really bugs me, however, is how much publicity Koblitz has managed to get out of this. I see him invited to give talks at many venues, but never see anyone invited to present a counter-argument. (For that matter, I don't see invited speakers at cryptography conferences poking fun at the cryptographic work that mathematicians do.) This does not matter so much when Koblitz speaks at a TCS-venue (any intelligent cryptographer knows that his arguments are overblown), but I think it matters greatly when he speaks in front of an "outside" audience.

For this reason, I thought publication of his article in the Notices of the AMS was inexcusable. Even worse, this latest incarnation of his essay goes beyond being a mere "academic" argument and degenerates to name-calling and belittlement of an entire field and all the people who work in it. (And it seems pretty clear that his feelings extend beyond crypto to CS at large.)

As promised, I have written a letter of complaint to the editors of the Notices. I don't know if it will get published (it is also a bit long), but it is available here (pdf) or here (ps)

P.S. After sending this post to Bill I noticed that Oded also wrote a letter to the Notices of the AMS.

Theory Starts Here! (Informatics Olympiad)

(Guest post by Mihai Patrascu)
A while ago, I promised the community around the International Olympiad in Informatics that I would bring them into the conscience of the theory community, and now I am trying to fulfil this promise. I have written a short " practical guide " of what we, as the theory community, should know and why we should care. Below is your executive summary:

Understand. What happens when you cross homo ludens with scientists? Imagine the Olympic Games, where you throw Computer Science into the arena. In short, you ask each country to send their best 4 high school students, who then compete in solving algorithmic questions.

Appreciate. The problems given in the contest are meant to challenge the brightest young minds in Computer Science. For a quick reference, problems in [CLRS] are "easy". Many questions asked are truly original, and thus can be fun even for a mature audience. Many questions can also make excellent assignments in algorithms courses (with or without a programming component).

Care. Informatics Olympiads are part of our intellectual tradition, and a part that should make us proud. The parallel olympiad in Mathematics is highly regarded in that community. A theory community that embraces the Olympiad is a stronger theory community.

More practically, the Olympiad gives us outreach to the high school level for free. We need a healthy flow of new talent, and the olympiad is already motivating hundreds of the smartest kids to learn theory. Our awareness can tell them that they are on the right path.

Most practically, we should be paying attention to it in the admissions process. The International Mathematics Olympiad, which has been running since 1959, has had a very significant impact on theory.

Our very own Informatics Olympiad is much younger (1989) and the contestant are only now coming of age. However, check out this list for notable theorists coming straight out of the Olympiad. If you want to know how well people are doing on average (and be impressed!), check this out. It is a statistic about the career paths of all Romanians who ever participated in the Olympiad.

RANT about Electronic Refereeing

When you are asked to referee a paper, should you accept the job? That is not todays topic. Today's posting is a rant!
I got a request to referee a paper that I really could not turn down since I'm one of the few people who is qualified This may be reason enough to reject--- if very few people could referee it then perhaps the topic is too obscure. However, obsurity of research is not todays topic. Today's posting is a rant!!
BEGIN RANT
The request to referee was an automatic email. I then had to do the following:

1. Goto a website to accept.
2. Receive an email telling me how to access the paper.
3. Goto another website, click on something to receive another email telling me my password and login.
4. Change my password to one that I could remember. This took a while since they didn't state their rules for passwords, nor did there error messages tell me what the rules were.
5. Goto another website with that password and login and register by giving my name (gee, I think they would already have that), email (ditto), school address, areas of interest, key words of interest (that was really hard- it was a long list and nothing quite fit), my right thumb print, and my left eye retina scan.
6. To get the paper itself the website kept on doing odd things. I called them (by telephone!) and the editor said that I was not being an idiot, the website had problems that day, and they would try to send me the paper, but they were not sure they could access it. I told them that if they did not get me the paper within 24 hours I would not referee it. They got it to me 23 hours 45 minutes later.
7. I am looking forward to seeing if the website will be working when I fill in the referees report, which must be done on the web.

This is insane!
END RANT

I do not think I'm being a luddite to complain about this. Being a luddite (different link) is not the topic of todays post. I do not think that electronic refereeing systems using the web are a bad idea. But electronic refereeing systems are not todays posting. Todays posting was a rant!.

Impact of Facebook platform on CS enrollment

(Guest Blog by Amir Michail) As you may know, the Facebook platform was launched recently amid great excitement. This API allows developers to integrate their web applications with Facebook, a popular social networking service, particularly among students.

So why is the Facebook platform interesting? And what does it have to do with CS enrollment?

Web 2.0 entrepreneurs aim to attract millions of users to their service. The Facebook platform facilitates this by creating a highly viral environment for spreading a web service by leveraging the social network graph. In particular, when a Facebook user uses an application, his/her friends in the social network graph will know about it automatically and they might use it too, thus automatically informing their friends, and so on.

The Facebook platform may very well boost CS enrollment. After all, who cares about an uncertain job market when what you really want to do is to pursue your own startup and make millions?

For more on the Facebook platform and its potential, see this excellent keynote by Facebook's CEO Mark Zuckerberg: excellent keynote by Facebook's CEO Mark Zuckerberg

Now a question for you: as educators, what can you do to take advantage of this phenomenon to increase CS enrollment?

Checkers- Clarification by Schaefer

Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry and Scott's entry on checkers, and the comments on it. the comments on it. Then Aaron Sterling and Jon Schaefer had an email discussion about the checkers result. Here is the transcript abbreviated.

Sterling: Please clarify what you mean by checkers being solved. As you can see from the discussion, there is lack of agreement on what the Science article really meant.

Schaefer: Checkers has been weakly solved. The game is a proven draw and the proof online gives the sequence of moves for white and black to achieve the draw.

Sterling: More pointedly: what percentage of the total gametree is now determined?

Schaefer: We considered 10¹⁴ positions out of the total search space of 10²⁰.

Sterling: If the search area was pruned, what were the criteria used for that?

Schaefer: Lines of play that were provably irrelevant to determining the final result were ignored.

Sterling: Is there even a shred of possibility that a "supposedly losing" move could in fact lead to a won position, and so certain game lines were improperly excluded from search?

Schaefer: None.

Sterling: Most significantly, perhaps, is this only a statement about 8x8 checkers, or does it generalize in any way?

Schaefer: 8x8 checkers only. The program can, however, be used to solve any game of checkers (it does, in fact, work for an 8x8 variant and 10x10 international checkers).

FOCS registration Open

(Guest Informational Post by Phil Klein)

Registration has opened for FOCS 2007, which will take place in Providence on October 20-23.  Please go to

http://focs2007.org

Note that the early registration deadline is September 20, and the deadline for reserving a room at the hotel at the conference rate is also September 20.  (The hotel's regular rate is much higher.)

The Knuth Prize lecture will be given by Nancy Lynch on October 21.
A program of tutorials takes place on October 20, the Saturday before the regular conference program begins.  The tutorial talks are as follows:

Terrence Tao
Combinatorial Number Theory

Dan Boneh
Recent Developments in Cryptography

Daniel Spielman
Theory and Applications of Graph Spectra

Abstracts for the tutorials should be available soon.

A New Job and Journal

Guest Post by Lance Fortnow

As an anonymous commentor mentioned on Monday, I am moving to Northwestern University EECS in January. Northwestern also hired Jason Hartline and Nicole Immorlica so I have an exciting opportunity to join an up and coming theory group without having to move my family.

In other news the ACM Transactions on Computation Theory has been approved and will be starting up soon with yours truly as editor-in-chief. Watch for details and get your papers ready.

Graduate Complexity Theory Course

I will be teaching a Basic Graduate Course in Complexity Theory in the fall. Complexity Theory has too many theorems that you absolutely must cover. Hence you have to pick and choose. The people taking my course will largely not be doing theory. Hence I want them to come away knowing some very definite things. Also, I want every part of the course to have a definite goal they can appreciate. Here is the rough syllabus.

1. Defining TM's, Time-Hierarchy Theorem. NL=coNL. Savitch's theorem.
2. Cooks Theorem, some NPC reductions. Mahaney's theorem, PH, Karp-Lipton theorem.
3. If GI is NPC then PH collapses. (This will use PH, Karp-Lipton. Will also need hash functions, AM protocol for GIbar.)
4. If PARITYSAT is in P then SAT is in R. (This will use some of the machiney devoloped for GI.)
5. Everything in PH is \le_T^p #SAT. (Toda's theorem.)
6. If CLIQUE can be approximated then P=NP. (STATE PCP, give proof of some easier cases, but do not proof the full theorem or even try.)

Other topics that would be reasonable to cover: Baker-Gill-Solovay Oracle, Hard vs Random stuff, PARITY not in constant depth, and CLIQUE not in Monotone P. Not doing BGS-oracle since I'm not doing enough proofs that relativize in the first place. Not doing Hard vs Random since its a bit hard and a bit random for this level of course. Not doing Circuit Stuff since that does not fit in that well with these topics (concrete vs. abstract complexity). Any of these points are debatable.

I'll be giving out my own notes. My experience is that using other peoples notes does not work, and others using mine does not work. My notes work for students taking my course, who see my lectures, and who have access to me. But they would not be good for anybody else.

Math in Turkey

There is a recent story and a request for a petition signing that SEEMS like we should support it, but rather than repeat the story, here are pointers. It involves a Math Summer School in Turkey being closed down, and the person running it being arrested for "Education without permission" for apparently no good reason.

See Terry Tao's blog: here and a weblog he points to here.

Theorists who got jobs for fall07-where?

Aravind Srinivasan: I have a great idea for a Blog Post!

Bill Gasarch: What is it!

Aravind Srinivasan: We all know where Scott Aaronson ended up- MIT, but where did the other theorists on the market end up!?

Bill Gasarch: Living in a cardboard box with a sign saying ``will prove theorems for food'' !?

Aravind Srinivasan: No, thats for Math PhD's! The blog should ASK theorists who got a job in Fall 2007 to tell us where they got their jobs so we'll all know!

Bill Gasarch: Okay, I'll do it!

if you are a theorist who got a job starting in Fall 2007, please leave a comment telling us where it is and anything else you want to add about the job market, or life, or whether pi should be 2*pi, or anything else you care to expouse on.

Is Pi defined in the best way?

&pi, the ratio of the circumference to the diameter of a circle, is one of the most important constants in Math. However, &pi could just as easily have been defined as the ratio of the circumference to the radius of a circle. This would not change math in any serious way, but it would make some formulas simpler. Think about how often `2*&pi' comes up in formulas.

This theme was explored by Bob Palais in this article. He makes a good case. I look at two examples not in the article, one of which supports his case, and the other is a matter of taste. During this blog I will denote the ratio of Circumference to Radius by PII.

EXAMPLE ONE: Consider the volume and surface area of an n-dim sphere. There is no closed form formula (that I know of) but there is a recursive formula. See this. The following table shows, for each n, the volume of an n-dim sphere divided by Rⁿ.

n	Trad Vol/Rn	New Vol/n
1	2	2
2	&pi	(1/4)*PII
3	(4/3)*&pi	(1/6)*PII
4	(1/2)*&pi2	(1/32)*PII2
5	(8/15)*&pi2	(1/60)*PII2
6	(1/6)*&pi3	(1/382)*PII3
7	(16/105)*&pi3	(1/1640)*PII3

Is the New Volume easier or harder? A little easier in that all of the numerators are 1. But no real pattern. Similar is true for surface area. Are these formulas better? That is a matter of taste.

EXAMPLE TWO: The Zeta Function is

&zeta(n) = &sum r^-n (The sum is from r=1 to infinity.)

It is known that

&zeta(2n) = (-1)^n-1 ((2*&pi)²ⁿ/2(2n)!)B_2n

where B_n is the nth Bernoulli Number. If we use PII instead we get the simpler

&zeta(2n) = (-1)^n-1 ((PII)²ⁿ/2(2n)!)B_2n

This is BETTER!

This is the 1000th post !

This is the 1000th posting on the complexity blogs. 958 were when Lance was running it and the rest (I'll let you do the math) were when I was running it. This is not an exact count of how many postings we made since there were many guest posts.

SO, how to celebrate? I request that readers comment on their favorite and/or least favorite postings of either Lance or I.

I'll start: my favorite posting of Lance's was on how fields tend to view themselves as NOT being in a golden age: here it is

My least favorite was Lance's fairwell post. Not quite fair- it was a fine post, but I didn't like that he was stepping down.

~

Scorpio's Logic

The job market for theorists is rough, and for logicians even rougher. Hence some seek employment outside of academia, outside of research labs, outside of mathematics! This may explain the following which appeared in the onion astrology column under Scorpio. We quote it here:

Scorpio Love means different things to different people, but you're the only one for whom it means that to every w-consistent class K of formulas there corresponds recursive class-sign r (on free var. v), such that neither (v Gen r) nor ~(v Gen r) belong to Fig(K).

I leave it to my commenters to identify what this means. However, it does require someone who knows some logic to come up with it. I would like to think that some recent PhD's in logic got a job at the onion and is happy there.

Away Message

When I won't be in email contact for a while I set up a vacation program so that if someone emails me they get a message. I used to use the following:

I am not in email contact. If you absolutely, positively, have to contact me then get a life.

My wife told me this was offensive, so I changed it to

I am not in email contact. If you absolutely, positively, have to contact me then you have the wrong priorities.

She didn't like that one much either, but it was better. And I think its cleverer. But this raises the question, what is the proper etiquette for vacation programs?

1. 15 years ago someone who is not computer savy was offended by the `get a life' vacation program, thinking that I had send it personally.
2. 2 years ago a shy grad student from a different school was terrified by my `wrong priorities' vacation program.
3. Aside from that, most people tell me they like both of them.
4. I often email someone, get a vacation program reply, and then within 5 minutes get a real reply. I find that someone rude.
5. Whatever the vacation program etiquette it will likely be irrelevant as we are logged on more and more, even on vacation.

Suggestion for STOC /FOCS(guest post)

(Guest post from Shiva Kintali. All capital letters, italics, and boldface are from Shiva.) A request to FOCS/STOC PC members Hi All, I would like to point out a concern I have about the FOCS/STOC conference proceedings. There is a huge gap of around four months between the announcement of accepted papers and the conference date. For example: STOC'07 acceptance date was Feb-18th and conference date is June 11. FOCS'07 acceptance date was July 1st and conference date is Oct 21.

Most of the authors don't upload their drafts/camera-ready papers on their homepages, for some unknown reasons. Some of them are kind enough to send their drafts if you send them an e-mail. Some don't bother to reply. If there is an exciting result (most of the STOC/FOCS papers have exciting results), most of us would like to know the techniques used, as soon as possible. For example, one of the FOCS'07 result helped me a lot in my research. I knew that the result can be used in my research, but I had to wait for four months. Waiting for four months to know the details of a result is really frustrating.

Also, there is a gap of around 40 days between the acceptance date and the deadline for camera-ready submissions. I guess the difference between the submitted paper and camera ready version is latexification and adding the suggestions of the reviewers. This should not take more than couple of weeks. Once the committe is happy with the camera-ready version, the digital proceedings can be uploaded on the ACM/IEEE portals. I think a gap of one month between the acceptance date and uploading the digital proceedings is reasonable. Of course, this would require some hardwork from the authors and the committee. This hardwork would not go waste !!

Can somebody PLEASE propose this in the next FOCS/STOC business meeting !!

Checkers Solved- its a draw!

The game of checkers seems to have been solved. Its a draw. See here or here if you don't mind seeing an ad for low cholestrol cooking before getting to the article or here if you subscribe to the nytimes or here if you trust wikepedia. The checkers program CHINOOK cannot lose (it can draw). The program has been around for quite some time, being improved over time. The researchers are Jon Schaeffer (the originator), Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. They say they have a `computational proof not a math proof'. Not sure what that means, but I do believe that Checkers is now done.

There is a very good book called One Jump Ahead that is about the program Chinook that plays Checkers very well (now perfectly apparently) but it was written a long time ago, before the recent news.

My impression of Chess and Checkers playing programs is that they are very clever engineering but not really much for a theorist to get excited about. However, very clever engineering should not be underrated. I also think that these programs have taught us that (some) humans are very good at these games in a way that is different than machines. When Deep Blue beat Kasporov, rather than thinking (as the popular press did) Oh no, computers are smarter than humans!! I thought Wow, it took that much computing power and that much look-ahead to beat Kasporov. Kasporov must be very good (duh) and the way he plays is different than what a computer would do.

Similarly, the Chinook researchers ended up being very impressed with Marion Tinsley (the best checkers player of all time, since deceased). Analysing his games it seems as though he almost never made a mistake. Chinook and Tinsley had two matches- Tinsley won the first one with 4 wins to Chinook's 2. During the second one Tinsley took ill and had to forfeit- he died a few months later.

Will checkers decline in popularity? I don't think so--- its already so unpopular that it can't decline much. This story may give it a temporary revival.

W(6,2) = 1132! (excitment, not factorial)

A PhD Student, Michal Kouril, found a new van der Waerden number, W(6.2)=1132. See here for details. I had a list of known VDW numbers in an earlier post, but I redo it here with the new result.

VDW(k,c) is the least number W such that no matter how you c-color the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15) that are the same color. W(k,c) exists by VDW's Theorem. See Wikipedia or my post in Luca's blog

The only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005 and the website above about W(6,2).

1. VDW(3,2)=9, (easy)
2. VDW(3,3)=27, (Chvátal, 1970, math review entry,
3. VDW(3,4)=76, (Brown, Some new VDW numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432.
4. VDW(4,2)=35, Chvátal ref above
5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!
6. VDW(6,2)=1132. Michal Kouril. 2007. (Not available yet.)

Over email I had the following Q & A iwth Michal Kouril.

BILL: Why is it worth finding out?

MICHAL: As my advisor Jerry Paul put it Why do we climb Mount Everest?" Because it is there! The advances we've made during the pursuit of W(6,2) can have implications on other worthy problems.

BILL: Predict when we will get W(7,2)

MICHAL: Septemer 30, 2034. Or any time before or after. Interest in Van der Waerden numbers has been growing lately and I would not be surprised if we saw W(7,2) lot sooner than this. Some unknown VDW numbers are already just a matter of the amount of computing power you throw at them in order to prove the exact value. But W(7,2) still need more analysis to make them provable in a reasonable amount of time.

(Back to bill's blog:) In a perfect world Michal would be interviewed by Steven Colbert instead of me. Oh well...

Can Jerry Seinfeld crack P vs NP ?

The following is a quote from Comedian Jerry Seinfeld. The source is Seinfeld Universe: The Entire Domain by Greg Gattuso (Publisher of Nothing: The Newsletter for Seinfeld Fans, page 96.

I was great at Geometry. If I wanted to train someone as a comedian, I would make them do lots of proofs. That's what comedy is: a kind of bogus proof. You set up a fallacious premise and then prove it with rigorous logic. It just makes people laugh. You'll find that most of my stuff is based on that system ... You must think rationally on a completely absurd plane.

I doubt that many comedians have seen lots of proofs though they may have an intuitive sense of logic for their routines. And not all comedians use this style.

I know of one theoretical computer scientist who is a comedy writer. Jeff Westbrook got his PhD in 1989 with Robert Tarjan on Algorithms and Data Structures for Dynamic Graph Algorithms. He was faculty at Yale, and then a researcher at AT+T before working on the TV shows Futurama and The Simpsons. I actually met him in 1989- he didn't seem that funny at the time.

Are there other theorists or mathematicians that are also professional comedians or comedy writers? I doubt there are many. If you define theorist or mathematician as having a PhD then I assume its very very few. If you defining it as majored in math or CS there would probably be some.

A postal campaign against spam

I will be sending the following letter by snail mail and you should send a similar letter- you may have an effect on spam.

Dear Govenor Huckabee,

There is someone trying to destroy Americas computer infrastructure and blame it on you! I received an email (excerpts below) that look like it was from your campaign but clearly it is not. I know it is not from your campaign since spam is so vile, so disgusting, that a man of high moral character such as yourself would not use it. (Note that even your ethically challenged competitors have not used it.) The spam in question asks the receiver to send a certain email to friends, relatives, and co-workers. This sounds like a chain letter, which is illegal, but of more importance it could crash America's computers. I urge you to take some action to make sure the public knows it is not you behind this vile spam, and put some effort into tracking down the people responsible.

Here are excerpts and my comments on it.

Mike Huckabee - The Exploratory Committee

When we launched the barber pole campaign a few weeks ago to raise 400 contributions in 96 hours, we had a tremendous response: 600+ total contributions, 400+ first-time contributors to the campaign and quite a few laughs.

While this is not quite asking for money, that might be the next step in this disgusiting scam.

Republicans, Democrats and Independents. I am interested in sharing my vision for America with all comers. I have a clear record that I'm proud of and I am willing to promote it to anyone regardless of their politics.

Another dead giveaway--- during the primaries you target your own party only.

The goal of this new, online campaign is to have 400 online volunteers send emails ! on the campaigns behalf over the next 72 hours. Please focus only on people you know: friends, family members and co-workers. We have designed a special email that we would like you to send.

This is the real dirt- they want to flood our computers with this email!!!

Now that you are allerted to the danger, please do something about it.

William Gasarch, Concerned Citizen

An Open Problem wiki!

A blog entry of Lance's on open problems noted that it would be good to have a repository of open problems. Perhaps a wiki or something.

I recently go the following email that may be an answer:

I am writing you in (very belated) response to a post on your blog in mid March. You posted a message called "A Place for Open Problems" where you suggest: "We need some Web 2.0 system. A blog or wiki to post the problems. A tagging method to mark the area and status. A voting system to rank the importance of the problem. A commenting system for discussion. A sophisticated RSS system for tracking. A visual appealing and simple interface. And most importantly, someone willing to put it all together for no compensation beyond the thanks of the community."

Together with Robert Samal, we have just finished the construction of a system which matches your request quite closely. There are still some small modifications we are making, but it is alive and fully functional, and we would greatly appreciate any input/publicity from you and your readers. Our website is called "The Open Problem Garden" and lives at the following url: here it is

Hope you enjoy it.



Best, Matt DeVos

I corrected them about Lance making that posting, not me. Of much more importance - they have a wiki!! Is it good to use? Will we use it? This is one of those chicken-and-egg problems where if enough people use it then it will be a good resource. Of course, Matt and Robert are not innocent bystanders- if it has a good interface and other features then we are more likely to use it. It seems to be open problems in all of mathematics, though computer science theory is a category. If there was a wiki tailored to Theory would that be better or worse? I would guess worse because the distinction can be artificial anyway.

And of course there is the issue of- are you better off working on your open problems or posting them? It may come down to this:

Which is greater, your curiosity or your ego?

A ``Concrete'' Open problem

(Guest Post by Ken Regan) pdf file available here

Computational complexity theory is the study of information flow and the effort required for it to reach desired conclusions. Computational models like cellular automata, Boolean or algebraic circuits, and other kinds of fixed networks exemplify this well, since they do not have "moving parts" like Turing machine tape heads, so the flow's locations are fixed. Measures of effort include the time for the flow, the amount of space or hardware needed, and subtler considerations such as time/space to prepare the network, or energy to overcome possible dissipation during its operation. These models and measures have fairly tight relations to Turing machines and their familiar complexity measures.

For an example and open problem, consider the general task of moving all "garbage bits" to the end of a string, leaving the "good bits" in their original sequence. We can model this as computing the function f: {0,1,2}^* ® {0,1,2}^* exemplified by f(1020212) = 1001222, f(2200) = 0022, f(101) = 101, etc., with 0,1 as "good bits" and 2 as "garbage." A rigorous inductive definition, using e for the empty string, is f(e) = e, f(0x) = 0f(x), f(1x) = 1f(x), and f(2x) = f(x)2. This is the "topological sort" of the partial order B = {0 < 2, 1 < 2} that is stable, meaning that subsequences of incomparable elements are preserved. The problem is, can we design circuits C_n, each computing f(x) on strings x of length n, that have size O(n)?

The circuits C_n have input gates labeled x₁,...,x_n which receive the corresponding "trits" (0, 1, or 2) of the input string x, and output gates y₁,...,y_n giving y = f(x). The first question is, what interior computational gates can C_n have? A comparator gate g for a partial order (P, < ) has two input and two output wires, maps (a,b) either to (a,b) or (b,a), and never maps to (d,c) when c < d. The unique stable comparator g_P maps (a,b) to (a,b) unless b < a. The following slightly extends the famous 0-1 law for comparator networks:

Theorem 1. If a circuit C_n of comparator gates computes f(x) correctly for all x Î {0,2}ⁿ (not even including any 1s), then for every partial order (P, < ), the circuit C_P with each comparator replaced by g_P computes the stable topological sort of P.

Proof. First suppose C_P errs for a total order (P, < ). Then there are x,y Î Pⁿ such that C_P(x) = y, but for some j, y_j+1 < y_j. Take the permutation p such that x_i = y_p(i) for all indices i. Define a binary string y¢ Î {0,2}^* by y¢_i = 0 if y_i < y_j, y¢_i = 2 otherwise, and x¢ by x¢_i = y¢_p(i) for all i. Then C_n(x¢) = y¢ (exercise: prove this by induction taking gates one at a time), contradicting that the original C_n was correct on {0,2}*.

For (P, < ) not a total order, an error C_P(x) = y (which might violate only stability) is also an error in the total order (P_x, < ¢) with P_x = {(a,i): x_i = a} and (a,i) < ¢(b,j) if a < b or a is not comparable to b and i < j. [¯]

Corollary 2. Circuits C_n of comparator gates computing f require size n*log₂(n) - O(n). [¯]

This follows by applying the standard sorting lower bound to C_P. It's interesting that we did not need 1s in x to argue stability, and the lower bound allows gates g in C_n to be arbitrary when either input is 1.

For general circuits, however, the argument doesn't hold, and all bets are off! To see why, consider sorting the total order {0 < 1 < 2}. Clever O(n)-size circuits can count the numbers a,b,c of 0s, 1s, and 2s in the input string x, respectively, and then assemble the correct output y = 0^a 1^b 2^c. For the basic idea see Muller-Preparata, 1975, and various sources on the "Dutch National Flag Problem." Applying this counting idea to our poset B reduces our task to "nice" strings z of length N = 2^k with exactly N/2 2s.

Theorem 3. If s(N)-size circuits D_N can compute f(z) for "nice" z, then f has circuits of size at most s(4n) + O(n).

Proof. We can build O(n)-size circuits E_n that on inputs x of length n count b,c as above and find k such that m = 2^k-1 is the least power of 2 above n. Make E_n(x) output z = x1^m+c-n2^m-c, which gives |z| = N < 4n. Then compute y¢ = D_N(z) and re-use the computed b,c,m to pluck off the n bits of f(x). [¯]

This reduction to nice z enhances the "flow" metaphor. The m-many 2s in z can be advance-routed to the last m places of y¢, so the whole issue is how the m-many 0s and 1s in z flow together into the first m places of y¢. Must this flow progress (without loss of circuit-size generality) by "squeezing out 2s" in an intuitively plane-filling fashion, allowing "mileposts" whose forced spacing might mandate having n*log₂(n) - O(n) gates? Or can linear-size networks rise above the planar view? No one I've asked has known, and lack of them frustrates a desired general linear-size circuit simulation of my "Block Move" model. Issues here may be involved. Nor do I know nicer descriptions of O(nlogn)-sized circuits than "use ancillas to tag bits of x and work in P_x as in the proof of Theorem 1, employing ideas of Theorem 3 and/or mapping into the O(nlogn)-sized Ajtai-Komlos-Szemeredi networks." Those seeking an o(nlogn) upper bound may be my guest, but those believing a super-linear circuit lower bound must reflect that no such bounds are known for string functions whose graphs belong to NP or to E.

The above inductive definition of f yields a linear-time algorithm on any model that simulates each operation of a double-ended queue in O(1) time. But is booting a 2 to the rear in f(2x) = f(x)2 really in constant time, even amortized? True, our technical issues shrink away on passing from linear to polynomial time, so all this may seem to have nothing to do with P versus NP. But au-contraire the Baker-Gill-Solovay "oracle" obstacle may mean nothing more than that standard "diag-sim" and timing techniques are insensitive to internal information flow. The "Natural Proofs" obstacle may ultimately say only that network-preparation/"nonuniformity" is a subtly powerful consideration. Honing tools for information-flow analysis on incrementally more-general cases that yield super-linear lower bounds may be the walk to walk before trying to run.

---

File translated from T_EX by T_TH, version 3.77.
On 21 Jun 2007, 23:36.

`Its Huffman coded!' does make sense!

On the post Math Terms used in Real Life- Good or Bad I mentioned the following:

On 24, season two, there was a line `we can't break in, its been Huffman coded!' This makes no sense mathematically but it raises awareness of security issues.

I had thought that Huffman Codes are just used to compress data and had nothing to do with hiding information. I was wrong! Yakov Nekrich pointed out the following to me:

Actually Huffman codes can be difficult to break, see for instance this article: On breaking a Huffman code by Gillman, D.W. Mohtashemi, M. Rivest, R.L.

I'm curious- did the writers of 24 know this or not? I would guess no, and they just lucked out. Unless Hillman or Mohtashemi is moonlightening as a writer for 24 (I doubt Rivest needs the money.)

A Review of THE KLEIN FOUR's CD

As a collector of Novelty songs and a math-person I was morally obligated to purchase Musical Fruitcake by The Klein Four, a band consisting of math grad students singing songs about math. They sing a cappella (without instruments). While you are not morally obligated to purchase their CD,you can. Or find out more about them (or go here for samples).

SO, how is their CD? I give each song a rating between 1 and 10, 10 being Excellent and 1 being unlistenable.

1. Power of One: A love song that uses Math. Rather pleasant and clever. But the math is fairly easy. lyrics Rating: 8.
2. Finite Simple Group of Order two: Their signature song, and their best known since its on You-Tube. Another love song that uses math, but much more sophisticated math. Better sung on the CD than on the video. lyrics Rating: 9
3. Three Body Problem: Sung by a guy about losing his girl to another guy. Lots of Physics-Math involved. Touching. lyrics Rating: 7
4. Just the four of us: Seems to be autobiographical and partially a Rap Satire. More fun for them than for me. lyrics Rating: 5
5. Lemma: Lyrics are not online. Thats just as well. It sounds like its a song about liking a lemma- not funny enough for satire, not serious enough for--- how could a math song ever be serious? Rating: 4
6. Calculating: The best song ever written about algebraic topology. lyrics Rating: 6
7. XX Potential: Lyrics not online. About Women doing math (XX vs XY). Nice rythmes but not much math in the song. Rating: 6
8. Confuse Me: About how confusing math can be. Mentions some math- mostly group theory. (A commenter corrected me on this- there is no group theory in this song. I was... confused.) lyrics Rating: 7
9. Universal: Yet another love song that uses Math. The math used is intermediary between Power of One and Finite Simple Group. Tune is not catchy. Lyrics are as tedious as Category Theory. Lyrics not on line. Rating: 4
10. Contradiction: Seems to be a guy singing about having lost his girlfriend. But its hard to tell- which is a problem. Also, no math except `contradiction'. Lyrics not on line. Rating: 4
11. Mathematics Paradise: To the tune of Gangster Paradise by Coolio. Weird Al had the song Amish Paradise to that tune, and for a brief time Coolio was mad at him for that (they seem to have made up). I doubt Coolio has heard this album, but you never know. Anyway, this is the BEST song on the CD. Clever words, sung well (at least well enough). About the pain of being a 5th year grad student in math. Hopes, dreams, despair- its all there! lyrics Rating: 10
12. Stefanie (The Ballad of Galois): Historically inaccurate, but kind of fun. Has a Country-Western Twang to it. Rating: 8
13. Musical Fruitcake (Pass it Around) Mostly random words, but kind of interesting. Rating: 6
14. Abandon Soap Mostly random words, but not so interesting. Title is like `abandons hope' Very short. Rating: 5

So, what is the final evaluation? I rate CD's by how many songs I really like. I like six of them which is very good. Based just on their Video I had written they shouldn't quit their day jobs- thought since they are grad students in math they probably don't have day jobs.. My current opinion is higher. Still, the math novelty song business is brutal- I wish them luck.

The number of times I've bought a CD because the artists had one really good song, and then found out that the one good song was there only good song is at least VDW(4,2). (Yes Arrogant Worms, singers of the brilliant CARROT JUICE IS MURDER but nothing else even half as good- I'm talking to YOU!).

As for other Math-novelty song- I'll have a post on that once I get a complete list of all that I know on this topic. Could take a while.