Wednesday, January 31, 2007
- 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.
Tuesday, January 30, 2007
Monday, January 29, 2007
Sunday, January 28, 2007
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.
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?
Thursday, January 25, 2007
Physicist: Computer scientists have done nothing for quantum computing.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.
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.
Wednesday, January 24, 2007
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.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.
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?
Tuesday, January 23, 2007
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.
Monday, January 22, 2007
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.
Friday, January 19, 2007
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.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.
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.
Thursday, January 18, 2007
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.
Wednesday, January 17, 2007
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.
Tuesday, January 16, 2007
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.
Monday, January 15, 2007
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.
Friday, January 12, 2007
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.
Thursday, January 11, 2007
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.
Wednesday, January 10, 2007
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?
Monday, January 08, 2007
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.
Sunday, January 07, 2007
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.
Friday, January 05, 2007
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.
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.
Thursday, January 04, 2007
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.
Wednesday, January 03, 2007
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.
Tuesday, January 02, 2007
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.
- Explain your results.
- Explain why your results are important.
- 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 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.