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.