Which one should you choose? You don't have to, you can freely submit to both ECCC and CoRR. But how do they compare? [Disclosure: I am on the ECCC Scientific Board.]

• ECCC focuses on computational complexity though often contains papers across theoretical computer science. CoRR broadly covers all of computer science (with tags for subfields) and is part of the arXiv project covering physics and math as well.
• An article has to be approved by an ECCC board member to meet a minimum standard before it can appear. CoRR only checks for relatedness to the topic area.
• Both plan to have papers posted forever. ArXiv is currently run by the Cornell Library that gives stronger backing to this promise. However every paper on the ECCC and CoRR should later appear in a conference proceedings and/or journal.
• ECCC takes postscript submissions. CoRR prefers LaTeX submissions and processes them with hypertex.
• Both systems allow revisions and all versions remain available.
• ECCC has a (not-so-user-friendly) discussion system and email announcements of new papers. CoRR has RSS feeds for each subject class. Both systems plan to continually update their interfaces and features.

I heard a complaint that in the movie Deja Vu they used face-recognition algorithms to find a suitcase in a large city in a matter of seconds. Because it's important to keep the computer science accurate in a time-travel movie.

In the last Numb3rs, Charlie the mathematician was seen carrying a copy of the SIAM Journal on Computing, a prominent TCS journal. Was he reading my paper or yours? At the end of the episode Larry the physicist left on the space shuttle to spend six months on the International Space Station while the actor, Peter MacNicol, moves over temporarily to the show 24. Couldn't Larry just have gone on a normal sabbatical?

On a more serious note we finally got around to watching Al Gore's documentary An Inconvenient Truth. Gore seriously impressed me with how he laid out the arguments and effects of global warming. The movie really affected my daughters leading to some interesting family discussions about warming and what we can do. I highly recommend watching the movie for those who haven't yet done so.

--
Posted by Lance to Computational Complexity at 12/20/2006 03:30:00 PM

The boundary between science (as the study of natural phenomena) and engineering (as the development and study of man-made artifacts) has become much more porous and in certain areas has virtually vanished. Historically, the University of Chicago has had a major international presence in science, but with a few special exceptions, has not systematically developed programs in engineering. With this important and evolving paradigm shift in the relationship between science and engineering, there are important questions regarding how the University should respond. These questions arise both because of exciting and important new areas of investigation at the science/engineering interface and because a lack of an explicit investment in engineering may hamper the development of our science.

Dear Recruiting Committee:

George Henry is among the top fifty computational complexity theorists on the market this year and you should consider him for any faculty, postdoc or janitorial position in your department.

Computational Complexity compares complexity classes representing different amounts of complexity resources among different computational models. There are hundreds of complexity classes and thousands of variations on those classes. Henry's best result shows that for two of these classes, one of them is not contained in the other assuming that some third class is not contained in some fourth class. This work appeared in a theoretical computer science conference you've never heard of.

For service, George Henry has wasted his money joining the ACM, IEEE, AMS, MAA, ASL and SIAM. He's even (under duress) refereed a paper or two.

Henry gave a seminar once and nobody ran out screaming, probably because they were too busy sleeping. Henry also taught a course once. He was not actually convicted on any harassment charges.

On the plus side George Henry has no two body problem since he's never had a relationship last more than three days.

In short, there are several great complexity theorists on the market this year but since your department has no chance of hiring any of them you might as well look at Henry.

Sincerely,

Lance Fortnow
Professor of Computer Science

--
Posted by Lance to Computational Complexity at 12/22/2006 01:24:00 PM

But over recent years this season seems far less quiet. We also work in a more global society and many countries, like Israel and India, treat this week not much differently than any other week. We can access the internet from anywhere and more importantly, we know everyone else can access the internet from anywhere. Taking time to visit relatives and friends or even going on vacation for many does not mean a break from email. Yesterday, Christmas Day, I received several actionable emails almost at the level of a typical workday.

We need an internet-free week. We should just shut down the whole network for seven days. Some people would use the time to relax and take a break knowing they will not be missing anything important. Others would continue to work finding themselves surprisingly much more productive than usual.

--
Posted by Lance to Computational Complexity at 12/26/2006 08:12:00 AM

Joan Feigenbaum and Michael Mitzenmacher have written a report "Towards a Theory of Networked Computation" available on the group's web page. The report is still under revision and Joan welcomes your comments.

SIGACT Chair Richard Ladner writes in the latest SIGACT News about the importance of the required Broader Impacts criteria in NSF proposals.

One way to think about the Broader Impacts criterion is that when we receive money from the people of the United States through NSF, the people would like to know ahead of time of what benefit the research may or will be to society. If there is little or no benefit then why should the people continue to support NSF? When NSF goes to Congress to ask for money, it is going to the people's representatives, who ask for justification to spend the people's money on scientific research. Basically, NSF's funding, and ours indirectly, depend on the belief by the public that broader impacts come from our research. Some people have said to me that a focus on Broader Impacts is a move away from basic research to more mission oriented research, or research with strings attached. If we look at the ways that we can satisfy the Broader Impacts criterion, they are very general, and relate to education, broadening participation by underrepresented groups, and other benefits to society. Please read the representative activities for concrete ideas for how to include Broader Impacts in our proposals.

As SIGACT Chair, I am trying to help increase the funding for computer science theory research. The best way to increase funding for research is to convince people it is important to them and the people around them. There is a difference between "important" and "useful". Artists are able to convince people to buy art, not because it is useful, but because it inspires them. Astronomers convince people to pay them to study the stars, not because they are useful (except for our own star, the sun), but because the stars are fascinating in their own right. Understanding the birth and possible death of the universe is of no practical value, but is just a fundamental question.

All this said, I am a firm believer in serendipity. Often, research leads to unexpected results and unanticipated applications. Unfortunately, this phenomenon is quite rare and probably not common enough to convince people to provide large amounts of research money. The best approach is to have a great story about the benefits of theoretical computer science research and its promise for the future. This will generate enough money for all of us so that rare serendipitous events will happen naturally in the course of doing our research.

The story of the year goes to Grigori Perelman, his proof of the Poincaré Conjecture, his declining of the Fields Medal and Shing-Tung Yau's portrayal in the New Yorker and the lawsuit threat that followed. Science magazine named Perelman's proof the Breakthrough of the Year.

Meanwhile the theory-friendly number theorist Terrence Tao accepted his Fields medal and CMU cryptographer Luis von Ahn and Tao won MacArthur genius awards.

My post FOCS Accepts and a Movie received over 200 comments mostly about the state of the theory conferences. Sadly the movie and the rest of the science.tv site have disappeared. I also finished my favorite complexity theorems, at least for now.

In 2006 we celebrated the centennials of the births of Kurt Gödel and Richard Rado and mourned the early death of Mikhail Alekhnovich.

Thanks to guest blogger Claire Kenyon, guest posters Eldar Fischer, Jérémy Barbay, Janos Simon and podcast guests Luis Antunes, Eldar Fischer, Troy Lee and his opponents. The biggest thanks to Bill Gasarch who did all of the above several times.

Happy New Years to all my readers and let's look forward to an exciting FCRC and a recommitment of the United States to increased funding in the basic sciences.

--
Posted by Lance to Computational Complexity at 12/28/2006 11:14:00 AM

A great job talk by itself won't guarantee you a job, but I've heard of many an instance where a bad talk has ruined a candidate's chances despite otherwise stellar credentials. A good job talk should achieve three goals.

1. Explain your results.
2. Explain why your results are important.
3. Explain how you achieved your results.

Know your audience, usually a broad spectrum of computer scientists. You give a different talk to them than you would in a regular theory seminar. Motivation and intuitive explanations of your research are key.

Repeat the following mantra as you make your slides: Formulas bad. Pictures good. Formulas bad. Pictures good.

Give a practice talk in your own department. Invite some people from outside theory. Listen to the comments. Revise your talk. Repeat.

--
Posted by Lance to Computational Complexity at 1/02/2007 07:29:00 AM

On the face of it, you would expect most baseball fans would rather watch paint dry than attend an opera and vice versa. But I'm not alone among the people who fanatically follow both. I can't pin down the exact connection between opera and baseball and one can make many philosophical comparisons (e.g. both require large teams but at most fixed times individuals rule the stage, both require a good attention span). Most lovers of both that I know are also scientists though that might just be my lack of a good sample. And I can't explain the Italians who seem to embrace opera and soccer.

In the academic world we get little choices about where we can live, so I find myself extremely lucky to be in a city with a great tradition in both baseball and opera. I've mentioned baseball more than opera in this weblog, but it was the baseball season tickets that I gave up once the kids were born.

If you are a great lover of baseball or opera you should give the other a try. And if you read the title of today's post and thought about the browser, shame on you.

--
Posted by Lance to Computational Complexity at 1/03/2007 08:48:00 AM

We were solving fundamental problems twenty to thirty years ago. There is still much we don't understand but today we are only solving puzzles.

At the end they all concluded that the future of their fields lied not in the cores of their fields but in the interaction between them and other fields not represented, like biology. They probably also said that twenty years ago.

--
Posted by Lance to Computational Complexity at 1/04/2007 06:14:00 AM

Reading your post 2006 Year in Review, I was reminded of a number of memorable things that are coming up in 2007.

Are there any commemorative facts to be noted in 2007? Most certainly there are, although it isn't anything like the Gödel year we just had. I'm not counting the Robert A. Heinlein Centennial to be held in Kansas City later this year, undoubtedly a major event for the science fictionists among us.

Staying closer to our field, in 2007 it will be 100 years ago that John Mauchly was born. Together with Howard Aiken and J. Presper Eckert he is one of the best known, early computer pioneers from the US. Together with Eckert he built the ENIAC and later the UNIVAC I (built between 1946 and 1951).

2007 also marks the 100 year anniversary of another computer pioneer, namely Antonin Svoboda from the Czech Republic. He was the main designer of the first Czechoslovak relay automatic computer SAPO (built between 1947 and 1951), working in the Research Institute of Mathematical Machines within the Czech Academy of Sciences.

From a more theoretical perspective, in 2007 it will be 100 years ago that Hassler Whitney was born. As a mathematician he made some highly original contributions to early graph theory, notably on the four color problem and on planarity (cf. Whitney's planarity criterion). He is also widely credited as the inventor of matroid theory, of which the foundations were defined in his 1935 paper On the Abstract Properties of Linear Dependence.

Other mathematicians whose centennials are coming up include H.M.S. Coxeter and Harold Davenport.

But 2007 also marks the 300 year (!) anniversary of the birth of Leonhard Euler. The math community is celebrating the Tri-Centennial Birthday of Euler in many ways.

• The journal IJMAS is devoting special issues to this year.
• The MAA devoted it Mathematical Study Tour for 2007 to an Euler tour, visiting his birthplace, Basel, and the two cities in which he spent his working life, St. Petersburg and Berlin.
• The city of Basel itself organizes The Leonhard Euler Tercentenary - Basel 2007 and celebrates it with a series of activities.

What should I wear for an academic job interview?

On the other extreme I have seen candidates looking uncomfortable in suits they clearly borrowed or bought off the rack. My suggestion, dress as nicely as you feel comfortable. To be specific, I'd suggest nice pants and a jacket with or without a tie for men. For women the best I can say is dress professionally.

Don't feel afraid to ask the person hosting your visit about these kinds of questions. The host generally wants you to succeed and can tell you about who you will meet and any expectations they may have.

--
Posted by Lance to Computational Complexity at 1/07/2007 08:27:00 PM

Many readers pointed to a New York Times article discussing how the freeze on spending levels for 2007 will affect science funding, a problem I mentioned last month. The Times article mostly describes the affect on big science projects but those of us doing "small science" will be hit hard as well. The CRA recommends that you contact your representatives and senators.

--
Posted by Lance to Computational Complexity at 1/08/2007 06:13:00 PM

But now the question "Why do so many scientists wear glasses?" has much less to do with eyesight. With advances in contact lenses and surgery most people can do away with their glasses. But most scientists seem to keep their glasses, even wearing them with pride. Is it really a fashion statement? I've asked some of my colleagues, they worry about the price or the risks, both of which are quite low once you do the research.

I couldn't wait to get rid of my glasses. I started wearing contacts in college in the late 80's and had LASIK surgery in 2002. I've had better than 20/20 vision and haven't needed to worry about my eyesight since. How do your glasses feel?

--
Posted by Lance to Computational Complexity at 1/10/2007 10:18:00 AM

Over my life I have visited the flagship campuses in Arizona, Indiana, Iowa, Maryland, Massachusetts, Michigan, Minnesota, Nebraska, New Jersey (Rutgers), North Carolina, Oregon, Pennsylvania (Penn State), South Carolina, Texas, Vermont, Virginia, Washington, West Virginia and Wisconsin. (Illinois is conspicuously absent). I have also visited several campuses of the California and New York systems which don't have a specific flagship. I can more locations of flagship campuses than I can state capitals.

The state universities got a strong push from the Morrill Land Grant Act passed during the Lincoln administration after the southern states that objected (like South Carolina) had left the union.

One of the great strengths of the US higher education system are these state universities, independent and competing, instead of a system of nationalized universities that you find in many other countries.

--
Posted by Lance to Computational Complexity at 1/11/2007 08:13:00 AM

Let x and y be two integers with 1<x<y and x+y≤100. Sally is given only their sum x+y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.

The following conversation now takes place:

• Paul: I do not know the two numbers.
• Sally: I knew that already.
• Paul: Now I know the two numbers.
• Sally: Now I know them also.

There will be a new event at STOC 2007, the Student Research Competition, which will be a poster and short presentation competition for undergraduates. The deadline for submissions is February 23rd, 2007. If you are working with an undergraduate on research, please encourage him or her to submit to this competition. Accepted students are provided up to $500 for travel to the conference. This competition is an excellent way to engage the next generation of theory researchers in our conference. I want to thank Brent Heeringa for chairing this new activity for SIGACT.

The 27th Crypto conference will be held August in Santa Barbara, one of the few conferences held in the same location each year. Submission deadline February 19th. For those who feel Crypto focuses too much on applied research, the Theory of Cryptography Conference (TCC) meets next month in Amsterdam.

ICALP, the granddaddy of European theory conferences, meets in Poland in July. Submissions by January 25.

RANDOM/APPROX in Princeton in August. Deadline April 7. MFCS (Eastern European Theory) in Czech Republic in August, deadline April 2.

There are many many more. DMANET and TheoryNet will keep you on top on what's going on.

--
Posted by Lance to Computational Complexity at 1/15/2007 07:16:00 AM

The proceedings would never leave my room until after the conference. I just hated lugging the heavy proceedings around. Sometimes when a speaker said something that didn't make sense to me, I would simply borrow a proceedings from someone sitting next to me.

When I returned home I would put the proceedings in its proper place on my office shelf, marveling at my complete collection of STOC, FOCS and Complexity proceedings back to 1986, incredibly useful for looking up recent papers.

How has technology changed how I use a proceedings? Not much during the conference, but I now rarely use proceedings to look up papers and no longer have complete collections of STOC and FOCS.

Other people use proceedings during a conference in different ways. Some never open them up. Some follow along in the proceedings during a talk. Some read the paper before or after the talk.

That's the important point to keep in mind when we have our debates on whether to eliminate proceedings, or put them on the web or on CD-ROMs. We all use proceedings in different ways and no single solution will address everyone's needs.

--
Posted by Lance to Computational Complexity at 1/16/2007 06:56:00 AM

I actually learned this procedure in the mid-70's, probably the last generation to do so. But unlike long division or Euclid's Algorithm, I quickly forgot how to compute square roots since the process was quite cumbersome, one didn't have to take square roots that often and reasonably priced calculators appeared soon thereafter. Almost no one even 50 years ago used the manual method for square roots, using slide rules or log tables instead.

I rarely even use calculators today. I find square roots like I find out anything else, praying to the Google Gods.

--
Posted by Lance to Computational Complexity at 1/17/2007 05:04:00 AM

In graduate school we took these trips quite often. Many conferences meet in the Northeast and we would pile into cars and drive out. A good chance to bond with your fellow students.

Fewer conference meet in the Midwest and in Chicago you tend to fly to travel. But we do have the occasional reason to take the long drive. We will be in a closed environment with no internet (assuming everyone stays off their cell phones). We'll actually have to talk to each other, maybe even try and prove a theorem. How quaint.

--
Posted by Lance to Computational Complexity at 1/18/2007 08:10:00 AM

In proceedings, papers are printed in a hard-to-read two column format and are artificially cut off at (usually) 10 pages. Personally, I look for a more readable/extended format on-line before suffering through the conference format. However, if we no longer have printed proceeding (or even if we did, but also had on-line proceedings) then these restrictions would no longer need to apply. We could print things is a way that would be much easy to read and could have original versions of the papers that we not oddly missing some proofs or sections.

Is this a good idea? Why don't we start doing this now?

But I would go further than Grant and suggest that every author should have a complete version of their paper available on their web pages and/or an archive site before the conference. I hate the phrase "A full proof will be available in the full paper" when one doesn't exist. But I don't want to require the extra version or we may end up discouraging people from writing up their results properly with yet another deadline.

--
Posted by Lance to Computational Complexity at 1/19/2007 08:30:00 AM

What are currently considered to be the best textbooks for complexity? I know the choice is small (Papadimitriou is probably still the best even if it is very outdated and somewhat buggy), do most of the lecturers just write their own lecture notes? Is there a set of notes that is especially popular and also used by others. I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching?

The topics and style of a computational complexity course varies from instructor to instructor and no single book would work for all. You really just need to find what best works for you and your class.

I personally don't use a textbook when I teach graduate complexity. I've been so close to the field no book would fit my philosophy unless I write it myself. And that's not going to happen anytime soon.

--
Posted by Lance to Computational Complexity at 1/22/2007 06:32:00 AM

In his position, Turner played a role in helping to push the American Competitive Initiative Bush presented at the State of the Union last year that would have, among other things, doubled the NSF budget over ten years, about a 7% increase a year. The ACI was "stillborn" with the continuing resolution that froze most of the government's budgets at last year's level. The continuing resolution has put a very tight squeeze at NSF and other governmental scientific institutions.

Still Turner has some reason for optimism. He expects the president to push for ACI again, if not in tonight's State of the Union, then in his budget for FY08 and has hopes congress will support ACI or a similar plan. Also several congressmen have signed a Dear Colleague letter requesting to add funding to the NSF for this fiscal year, though Turner was pessimistic that this request would be fulfilled.

--
Posted by Lance to Computational Complexity at 1/23/2007 05:45:00 AM

Hanging in the Indiana University Mathematics Lounge is a letter dated November 16, 1948 written to Max Zorn from Nicolas Bourbaki and cc'd to André Weil.

I am glad to be able to inform you that the American Consulate in Paris has now granted me a visa, and that I have booked passages, for my wife and myself, which should just enable us to reach Columbus, Ohio, in time for my scheduled talk to the Association for Symbolic Logic.

At the same time, I must say that I have learnt with no little surprise the rejection, on technical grounds which I do not understand, of my application for membership in the American Mathematical Society. Under such circumstances, it will be clear to you that I cannot but decline your kind invitation to attend a dinner which, I believe, is chiefly sponsored by that Society.

Bourbaki did have an invited paper presented at the ASL Meeting in Columbus on December 31. Weil, one of the founders of the Bourbaki group, presented the paper at the conference.

If the same kind of story happened today would we hang a framed email on the wall?

--
Posted by Lance to Computational Complexity at 1/24/2007 06:24:00 AM

Physicist: Computer scientists have done nothing for quantum computing.

Computer Scientist: What about Shor's quantum factoring algorithm?

Physicist: Peter Shor is a physicist.

This view has changed a bit, now we do see a number of physicists (though certainly not all of them) seeing value in many of the tools, techniques and results from computer science. We are also making headway in other fields like economics and biology.

If we want computer science to continue to prosper we need to continue to reach out to other fields and do our best to make them understand the role computer science can play in helping understand their basic questions.

--
Posted by Lance to Computational Complexity at 1/25/2007 09:38:00 PM

Looking at a random sampling of papers, the reviews seem to give a short description of the main results of the paper without much or any opinion on the quality of the paper though the fact the paper has a review indicates some positive view of the paper. Other than that the review doesn't seem to give more information than a well-written abstract.

As comments on this weblog show, many people will give more honest views if they don't have to reveal their identities. Anonymous reviews of papers might prove equally fruitful.

On this topic, David Bacon created a Digg-like site scirate.com for quant-ph. Kudos to Dave for bringing some Web 2.0 tools to highlight important papers.

Still researchers looks at papers more like movies—we like different genres and then have different preferences within these genres. Could some sort of recommender system for academic papers help us find good papers to read?

--
Posted by Lance to Computational Complexity at 1/28/2007 07:59:00 PM

• Last year many of the stronger candidates were coming off of postdocs looking for tenure-track jobs. This year we see more strength from the fresh Ph.D.s.
• Last year there were a large number of outstanding cryptography candidates. This year no particular field dominates.
• Last year the strongest candidates were heavily weighted with MIT Ph.D.s. The degrees of this year's candidates are much more spread out.

There are some notable exceptions to the above and the differences are easily explained by statistical variations on small sample spaces. But still worthy to note how much variation we see in the theory market from one year to the next.

--
Posted by Lance to Computational Complexity at 1/31/2007 09:52:00 AM