More NSF News

CMU's Jeannette Wing named head of the CISE directorate. Hopefully she can put some of that Computational Thinking into the NSF.

Theory Candidates

Having looked at the applications of several theoretical computer science job candidates, I notice some interesting differences from even one year ago.

• 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.

The last two points are not completely uncorrelated.

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.

Good News for the NSF

A 6% increase for the National Science Foundation for the current fiscal year (via the CRA Blog). Now go write those proposals.

Thought of the Day

Life is just a big Markov chain, whose stationary distribution is death.

Rating Papers

Suzanne Zeitman, associate editor of AMS Mathematical Reviews (and on the web), would like to get suggestions from the TCS community on how MR "can do a better job at covering the literature (wherever it is) in theoretical computer science."

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?

Too Useful to be a Computer Scientist

A conversation I heard about several years ago.

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 becomes a self-fulfilling prophesy. Once computer scientists have done something physicists care about they cease to be computer scientists and are now physicists.

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.

The Bourbaki Lecture

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.

Perhaps the AMS rejected his application on the technicality that Bourbaki did not actually exist as a person, he was just a pseudonym for a collection of French mathematicians writing a series of books on modern mathematics.

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?

Is it Morning or Mourning for American Science?

Last week Chicago Cosmologist Michael Turner gave a talk "Trends in Science Funding: From NSF to the ACI". Turner was head of the Mathematical and Physical Sciences, NSF's largest directorate, from 2003 until last summer (computer science is mostly funded from the CISE directorate). The slides describe the state and process of science funding in the US and argues for the importance of physical science funding.

In his position, Turner played a role in helping to push the American Competitive Initiative that Bush proposed 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.

Complexity Textbooks

A reader asks

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?

You have more choices than you think with textbooks by Homer and Selman, Hemaspaandra and Ogihara, Ko and Du, Wegener, and several others. Also several complexity theorists have put their lecture notes on line, quite a valuable resource. Jin-Yi Cai has the makings of a textbook from his lecture notes.

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.

Proceedings Papers

Grant Schoenebeck asked this question for the Q&A Podcast but we didn't get to it.

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?

We have the two-column format in proceedings because it saves space, a paper typically drops 30-40% by moving to a two-column format. Less white space.

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.

The Academic Road Trip

Jason Teutsch is an Indiana Math Ph.D. student who has been working with me via the CIC Traveling Scholars program. Tomorrow he defends his thesis so today I'm driving Jason and another faculty member and graduate student down to Bloomington. Road Trip!

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.

Computing Square Roots

My daughter learned about square roots and she did her homework taking those roots using a calculator. She asked me how to compute the square root without using a calculator.

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.

The Proceedings

It is a conference ritual as far back as I remember. Your arrive at the conference and receive the proceedings, all the papers to be presented at the conference many of which you are seeing for the very first time. I would take the proceedings to my room, smell that new proceedings smell and open it up, first checking that my papers looked fine, not that I could do anything if they weren't. Using the proceedings I would plan what talks I would attend the first day.

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.

Events

Richard Ladner wants me to remind my readers about the SIGACT student research competition. From his chair letter in the last SIGACT news.

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 TARK (Theoretical Aspects of Rationality and Knowledge) conference meets this year in Brussels in June mixing computer scientists, economists and philosophers discussing knowledge, rationality and how it all plays in CS and economic models. And I'm on the PC this year. Submission deadline is January 30.

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.

The Sum and Product Riddle

A cute problem that I got off Steve Fenner's door that he got from FOM.

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.

What are the numbers?

The State Universities

While Luca suffers in Hong Kong, I am visiting beautiful Columbia, South Carolina. (The ribs are better here) Next week a day in Bloomington, Indiana and the following week a couple of days in Ann Arbor, Michigan as I visit the flagship universities of those states.

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.

Four Eyes

Why do so many scientists wear glasses? Thirty years ago this question was essentially equivalent to "Why so many scientists have bad eyesight?" I don't have a good answer to this second riddle, perhaps some genetic link between scientific ability and eyesight, perhaps scientists don't have worse eyesight than society in general and I just have biased beliefs.

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?

SODA and Funding

Suresh and Jeff cover the SODA Conference currently meeting in New Orleans. Suresh talked about a lecture given by Luc Devroye giving techniques that might help determine the actual constant factors in some algorithms. I usually ignore constants even in the exponents. Perhaps that's why you tend not to see me at SODA conferences.

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.

Dress for Success

A graduate student asks

What should I wear for an academic job interview?

Most computer scientists won't notice and will completely forget what you wore when it comes to decision making time. But the wrong clothes might make a bad impression on some of them and you might meet administrators or faculty from other department with different standards of attire. You never want to give the appearance that you are not taking the interview seriously.

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.

2007 Celebrations

Jan van Leeuwen runs down many of the anniversaries coming up this year.

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.

Solving Puzzles

An economist, a physicist and a computer scientist were sitting at a table. A true story, not the beginning of a joke. One of them said

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.

Any one of them could have said that, scientific insecurity runs through all fields. A similar set of scientists probably had a similar discussion twenty years ago as well.

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.

Baseball and Opera

The New York Times reports on a possible merger of the two major US satellite radio companies. This would resolve one of the great dilemmas as XM carries the audio of every Major League Baseball game and Sirius has a station devoted to live and archival broadcasts of the Metropolitan Opera.

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.

The Job Talk

As we begin January so begins the hiring season. In January CS departments start sifting through candidates deciding whom to bring in for interviews. Don't wait until you get your interview call, now is the time to get your job talk ready.

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.

Fail to do the first two and you will not get the job. We theorists have a tendency to want to "wow" an audience with our clever techniques but first you must spend several slides carefully giving an intuitive description of your research and why those in the audience should care about the results. Be sure and mention what your own research is early in the talk and again at the end.

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 prepare 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.