Suggestions to Program Committees

A program committee member who asked me to review a paper pointed me to Oded Goldreich's Suggestions to Program Committees, one of his Essays and Opinions. In his suggestions he gives a reasonable interpretation to the usual ten point scoring system. A few minor quibbles: I would never score a paper a ten (which represents unattainable perfection) nor would I ever resign from a program committee, certainly not over a single paper.

The ends of the scale are not so important; a PC does not distinguish between the excellent papers from the merely great nor does it distinguish between the merely bad and the truly lousy but instead a PC must distinguish the pretty good papers from other pretty good papers.

Later on Oded strongly supports using "ex-submission information" in evaluating proposal even to the point of actively contacting authors for clarification during the review process. While PC members do not live in a vacuum and will be exposed to results they have to later review, actively contacting authors is patently unfair as it favors authors with whom you have a working relationship. Authors who cannot give enough information in the submission for the PC to properly evaluate the work deserve to have their paper rejected.

The State of CISE

While we have seen a increase in computer science funding over the past few decades, it has not kept up with the great increase in the number of researchers in our field making it difficult for many computer scientists to find funding. Peter Freeman, who heads the Computer and Information Science and Engineering (CISE) directorate of the National Science Foundation, co-authored this piece in the current Computing Research News describing has CISE funding has changed over the past decade.

A companion piece written by the CISE division directors describes how CISE is adapting to the large number of proposals. The article emphasizes some reorganization and making connections to other funding centers in and out of the NSF. Until CISE sees a large budget increase, too many computer scientist will remain unfunded or under funded which will hamper CS research in the long term.

Conflicts

Yesterday a program committee member sent one of my submissions to one of my current students to review. Heh Heh. I'll make sure he gives an unbiased positive review.

A good excuse to talk about conflicts of interest. You should not review, edit or referee a paper if one of the authors is

1. a relative and/or someone you are romantically involved with, or
2. a member at your institution.

The second because departments use major conference publications for bragging rights and we have seen some abuse in the past.

The NSF has more stringent restrictions for reviewing proposals. If we used these restrictions for paper reviews, like no close collaborators or no former students/advisor, there might not be any one left to properly evaluate the paper. If the restrictions (1) and (2) don't apply to you, you should state any potential unknown conflicts but feel free to say whether the paper soars like an eagle or gobbles like a complete turkey.

Speaking of turkey–Have a great Thanksgiving everyone!

NSF Budget

Over the weekend the US Congress passed an omnibus spending bill for the fiscal year that started on October 1. The CRA has a roundup of the budget for the National Science Foundation and other funding agencies. Bottom line: NSF down 1.9% overall, with a 0.7% drop for "research and related activities."

It's going to be another tough year for grants.

Letting Go

You just submitted your paper, working hard right up to the final deadline hour. Congratulations! Now what?

Forget about it. Oh you should distribute the paper: make it a technical report; email it to friends and family; put it on your web page and send it to an archive site. But don't keep working on it. All the tension you had getting the paper finished for the deadline needs a release. And no matter how much effort and time you continue to put into it, your paper will never be perfect.

Instead catch up on the todo's you've been ignoring. Say hi to the friends you have deserted while you bunkered down working. Take some time for you: catch a movie; eat a slow meal at a nice restaurant; take a walk.

Afterwards get back to research so you have another paper to write for the next deadline. You know you have successfully put that first paper out of your mind when you get caught off guard from the email from the PC chair letting you know your paper is

• accepted: Great. Now you have to fix the paper up again for the proceedings deadline.
• rejected: No problem. Now you have to fix the paper up again for the next conference deadline.

And it starts anew.

Zig-Zag Connectivity

The Zig-Zag Graph Product (Reingold-Vadhan-Wigderson) gave a new way to create expander graphs, graphs on n vertices with constant degree such that for some ε>0 and every subset of the vertices S with |S|≤n/2, |S∪N(S)|≥(1+ε)|S| where N(S) is the set of neighbors of vertices of S.

The zig-zag expander construction was not as simple as previous constructions nor did it have as good an expansion property. It did have one thing the other constructions lacked: a simple and beautiful proof of expansion.

The zig-zag construction had another property, a compact representation of the expander from the original graph. Reingold used this property to convert an arbitrary undirected graph to an expander in logarithmic space, the basis of his new result giving a log-space algorithm for undirected connectivity.

Why did George Lucas wait so long between the third and fourth Star Wars movies? He wanted the technology of movie making to catch up to his vision for the movie. Computational Complexity can also tell this story. We hit a wall a decade ago in reducing the space needed to solve graph connectivity. We needed a new technology (zig-zag product) and someone (Reingold) realizing they could use this technology to solve the problem.

Google Scholar

Google has just launched a new search engine for academic papers scholar.google.com. Google has received permission from some publishers to allow searching through their papers that would normally not be available for Google to crawl. Based on random checking, it seems ACM for example is allowing Google to see their papers but not Elsevier.

How about Informaticians?

A dinner conversation with my daughters.

Annie (age 9): How many computer scientists are there in the world?
Me (Wildly Guessing): About 100,000.
Molly (age 6): I know there are at least two. You and our computer teacher at school. Someone asked him if he was a scientist and he said, "yes, I am a computer scientist."

I don't think Molly's computer teacher tried to mislead; he just did a play on words. But it was enough to fool a six-year old and I suspect many adults as well. Maybe we need a new name for people in our field.

The Polar Express

I went with my family to see the movie The Polar Express. This movie blurs the line between between acting and animation. Tom Hanks played several characters including a young boy by wearing sensors on his face and body that recorded his expressions and then used for the computer generated characters on the screen. I had trouble explaining to my children (and my wife) how Tom Hanks played the boy even though someone else did the voice. Where in a more traditional computer animated movie like The Incredibles, the actors doing the voices get the credit.

We saw The Polar Express on an IMAX screen in 3-D. Since computers stored the entire movie, converting the film to 3-D could be an automated process. I predicted to my unbelieving children that when they grow up they will not be able to distinguish between computer generated film and those filmed live. Perhaps all movies then will be stored in some specific format like papers in PDF today that could be easily converted and optimized to whatever display device a person has.

Unless you have small children, I would recommend The Incredibles over The Polar Express. Technology does not win over substance. But I have seen the future and it is cool.

Does Google Make Us Lazy?

The search wars are brewing. Microsoft starts a beta test of their new search engine. Yahoo keeps improving their searching as well and Google does not stand still with doubling the number of pages it indexes and their new desktop search (which is rather useless to me because it doesn't index LaTeX files). In addition, search engines now do more than just web searching, for example you can directly use dictionaries, maps, time, a calculator and more with the right shortcuts on Google, Yahoo and Microsoft. What does it mean though when we need a manual to use a search engine?

All this searching power leads to the mistaken belief that the best way to find anything is by a direct search. For example many people look for a paper by Googling on the name of the paper. Usually that does lead to a version of the paper to download. But Google searches the deep recesses of the internet and often returns old versions of papers, even technical reports well after conference and journal versions have appeared. Google says "Don't be evil"; I say "Don't be lazy." If you have a reference to a paper in a particular conference or journal, search for that conference or journal and find the paper there if you have access. Or use a site like DBLP. Otherwise look on the author's web pages; good authors will keep versions of their papers up to date. If all this fails you can fall back on Googling the name of the paper. Working off the newest version of the paper will save you far more than the extra fifteen seconds you'll spend searching for it.

Undirected Connectivity in Log Space

Omer Reingold has shown Undirected s-t Connectivity in Deterministic Log-Space. This settles a long-standing open question for a problem previously known to be in randomized logarithmic space (Aleliunas-Karp-Lipton-Lovász-Rackoff) and deterministic log^4/3 space (Armoni-TaShma-Wigderson-Zhou). Wow!

In layman's terms, suppose you have a big maze, far too big to fit into your computer's memory. You can only ask questions of the form: given two locations A and B, are A and B directly connected? Reingold's result shows that you can determine whether there is a path from the entrance to the exit using only an amount of memory equivalent to storing a constant number of maze locations.

How Did We Survive Before the Internet?

A grad student asked me how we managed before the internet specifically in relation to submitting to conferences? I cannot completely answer that question as I started graduate school in 1985, a few years after the birth of the internet and already when most computer scientists reliably read email. But let me explain how it worked when I was a student.

In the second half of the 80's we generally still did not distribute papers electronically and the world wide web remained several years away. Nearly everyone in theory subscribed the the Theorynet mailing list (not so true today) and the call for papers were emailed to this list as well as sent out to all SIGACT members by postal mail. To submit to a conference we had to make ten copies of a paper and physically send them to the program committee chair who then sorted the papers into ten stacks and sent each stack to each program committee members. A few months later the program committee would meet and choose the papers for the conference sending out accept/reject letters through postal mail. Since MIT always had one or more PC members on the faculty we found out about our papers from them well before we got the official word.

Initially the STOC and FOCS PCs did not take deadlines seriously. For some reason about 1987 they decided to strictly enforce the deadline first by postmark and then by receipt. Federal Express made considerable money from us theorists and I can still tell you which Fed Ex offices in Boston and Chicago remained open the latest. One year an MIT faculty memeber hired a same-day service to send the papers to the PC chair giving us at MIT an extra night to work on our papers. Not many of us showed up for classes the next day.

Electronic submissions, starting in the early 90's, leveled the playing field and made the process slightly more sane. The STOC call still has the line

Authors who cannot submit electronically must send 21 printed copies (double-sided preferred) of an extended abstract, together with a cover letter, to:

When I served as the Complexity PC chair in 1999 exactly one person sent me their submission by Federal Express. "Am I going to have to send a copy of this paper to each of my PC members?" I thought. Instead I emailed the author and luckily he sent me a postscript file and I could manage the PC electronically. We have since removed the non-electronic submission instructions from the Complexity call.

Favorite Theorems: Quantum Lower Bounds

October Edition

Alice and Bob have subsets of {1,…,n}. How much communication do Alice and Bob need to determine if their subsets have a empty intersection. In classical communication complexity even with probabilistic players, Alice and Bob need Ω(n) bits of communication to solve this Set Disjointness Problem.

What if we allow communication with quantum bits? A clever protocol by Buhrman, Cleve and Wigderson based on Grover's quantum search algorithm shows how Alice and Bob can solve Set Disjointness communicating with (up to log factors) n^1/2 quantum bits. Could Alice and Bob do better? The best known lower bounds were about O(log n) until Razborov showed the Buhrman-Cleve-Wigderson protocol was essentially optimal.

Quantum Communication Complexity of Symmetric Predicates by Alexander Razborov.

In another important paper in quantum lower bounds, Andris Ambainis developed the hybrid method for proving lower bounds on quantum query complexity. This method gave researchers a new tool in proving stronger and sometimes tight bounds in the number of queries a quantum algorithm needs to an input to solve a problem like inverting a permutation. Ambainis' work formed the basis for many other papers applying the techniques and improving them including work recently presented at Dagstuhl.

Public Referee Reports

From Paquet via Nielsen comes an idea of publicly posting referee reports. Let's kill this idea quickly.

A review of the usual referee process: The editor-in-chief of a journal receives a submission and assigns a member of the editorial board to act as editor for that paper. The editor will contact potential referees and ask them to review the paper. The referees read the paper and write a report on whether to recommend the paper for publication and give suggested changes. They send this report to the editor who relays this information to the authors without revealing the identities of the referees. The authors will comment on the referee reports and revise the paper. The paper often goes back to the referees and the process repeats until the editor is happy with the paper or decides the paper is not worthy of the journal. The editor then sends his recommendation back to the editor-in-chief.

An argument for posting the reports goes as follows: If we make the reports public (though still anonymous) referees will feel a greater responsibility to make their report thorough and accurate.

The process of refereeing requires considerable back and forth conversation between the three parties: the authors, the editor and the referees. Posting the original reports will give a misleading view of the process and will cause referees to act far too cautiously about pointing out problems in a paper.

We have an editor responsible for making sure that he has enough quality reports to properly make a decision about publication. Using the public as an editor will often lead to some very difficult and messy situations.

Keep in mind the distinction between the referee process and reviews of published papers. We should encourage publicly available reviews of research papers whether in Mathematical Reviews or informal settings like weblogs. These reviews help us find the gems among the sea of research papers out there.

Life Goes On

Our department, like most other academic departments, felt a strong sense of depression today. Just remember there are still theorems to prove, papers to write, talks to give, students to advise, meetings to attend and classes to teach. Life goes on and so must we.

Memo to the future 2008 STOC PC Chair: Don't even think of scheduling the STOC deadline immediately following the elections again. There is only so much stress one can take in a week.

Vote Complexity

Complexity theorists have an important choice to make this week. That's right, I'm talking about whether to send your papers to STOC or Complexity. So let me put on my hat as chair of the Complexity conference committee and tell you why you should be thinking about our conference.

With the great growth in theory the STOC conference can now only accept a small number of papers in computational complexity theory. For the same reasons we have seen many strong papers appear in Complexity over the past several years from a quite broad range of complexity topics. Don't take my word for it and look at our last three conferences.

With your help we can add even more strength to the Complexity conference and continue to make it the primary venue for exposition of results in computational complexity. So submit your papers and I look forward to seeing you in San Jose.

And after you submit your paper to either conference, I highly recommend also sending the paper to ECCC. You will get quick publication and more exposure than any single conference.

I'm Lance Fortnow and I approve this message.