An Auction of Computing History

From Ryan O'Donnell

Christie's is auctioning off a bunch of documents related to the history of computing.

A '46 IAS report by von Neumann and others to the US Army on the concept of a computer is expected to go for around $35k, an original copy of Turing's "On computable numbers" for about $17.5k, a letter from Gödel to Skolem for about $15k, Shannon's collected works for about $10k, etc.

More from Anupam Gupta: Some related info (including dates of exhibitions in Cambridge MA, and Palo Alto) and also on Boing Boing.

DIMACS

This week I'm in the great Garden State of New Jersey (my home state) for back to back DIMACS workshops on Bounded Rationality and Markets as Predictive Devices.

Since 1989 DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) has greatly served our community with a collection of workshops, visitor and postdoc programs built around special years (later becoming special foci as they extended to several years). The workshops this week come under the Special Focus on Computation and the Socio-Economic Sciences. DIMACS also has a strong educational mission with programs for teacher training and for high school and undergraduate students.

DIMACS started as a National Science Foundation Science and Technology Center and when that program ended in 2000 DIMACS continues through a series of smaller state and federal grants. DIMACS based at Rutgers has partners drawn from several New Jersey universities and research laboratories. DIMACS has a strong but small staff and many volunteers within our community but I attribute the recent continued strength of DIMACS mostly to the tireless efforts of its director Fred Roberts.

DIMACS plays an important central organizing effort in theoretical computer science and has often represented theory to the NSF and other funding agencies. DIMACS has had an important direct and indirect role in my academic career and I suspect the careers of most theorists. Let's hope DIMACS can continue its multifaceted role in our field for decades to come.

Choosing Your Advisor

Someone threw out this quote yesterday.

Choosing your advisor is like choosing your spouse.

I would say more like choosing your parent since the advisor-student relationship is not symmetrical. But the point remains: No single decision will make or break your graduate career more than the choice of advisor.

A good advisor serves as a mentor and a colleague. Someone who will represent you, fight for you, challenge you and push you but not belittle you or take advantage of you. He or she will direct your research to primarily address your future career. An ideal advisor-student relationship will develop into a mutually strong research environment and will last well beyond the student's graduate career.

You should ideally choose an advisor whose expertise matches your research interests. But more importantly you need to find the advisor with which you can have a strong working relationship. You don't have to see eye-to-eye on every issue but you need to have mutual respect. Like in marriage, an advisor might work well with one kind of student but not with another. You need to find the right advisor that fits your needs and personality. If the advisor relationship goes sour for any reason, you need to change advisors. Being stuck in bad advisor-student relationship is almost a guarantee of a disastrous graduate career.

Remembering the Holocaust

As you probably know today was the sixtieth anniverary of the liberation of Auschwitz. In religious school as a kid we read books, saw gruesome movies, met holocaust survivors and I visited a concentration camp during a college trip to Europe. But the enormity of the holocaust hit me most during my sabbatical year in Amsterdam in 1996. One fourth of the population of the city was Jewish in the 30's. We had to work hard to find the small Jewish population so we could properly celebrate the Jewish holidays during our year there.

I worry sometimes about how to keep my children aware of the holocaust. How do I prevent them from just thinking it was just some event that happened a long time ago? When they reach my age what will they and the world do for the 100th anniversary of Auschwitz? Let us hope we can always remember.

STOC Papers

The list of accepted papers for STOC is up. Nice to see they accepted Trifonov's paper in addition to Reingold. Many other nice complexity results too. Take a look.

Blink

A publisher sent me a copy of Blink a new book by Malcolm Gladwell. Gladwell wrote the very popular Tipping Point about phase transitions which I haven't read.

The main thesis of Blink states that people can make good predictions quickly and with a small amount of information if they have experience or are properly trained. The real challenge is to get people to ignore excess information and focus on the few bits that can really can accurately determine an outcome. Often people make better decisions when rushed since they won't have time to focus on the extraneous details.

Gladwell does his homework and makes his case best by describing experts who do a good job predicting the longevity of a marriage, the flight of a tennis ball or the popularity of a new food item. I find his one-time examples less convincing since anyone can get lucky and even his best experts make occasional mistakes.

How do these ideas relate to computer science? In many more ways than I can mention in this post. Juntas (or NC⁰ as we used to call them) are functions that depend on a constant number of input bits and we've seen recent work on learning juntas. In general most of learning theory focuses on finding a short description that predicts well. Transformations like Fourier transforms and wavelets which allow researchers to focus on a small amount of important information useful in many areas like computer vision. The recent areas of sublinear algorithms and property testing often can say something interesting about an input by only looking at a small part.

In my job I also find myself using less information to make just as good decisions. I can often get a good feel about a research paper or a recommendation letter by a quick focus on a few key elements. I can almost always predict the quality of a talk within the first thirty seconds. Even in research where one has to narrow the list of techniques, I can eliminate large sets of approaches without having to work them out thoroughly.

One needs care not to weed out a good idea too quickly but if you allow yourself to get bogged down in details you will spend too much time often making the same or possibly worse choices.

The Premier of Numb3rs

Feel free to comment on last night's premier of Numb3rs, a show that has seemed to capture the interest of this community. For good reason as apparently the P versus NP problem will get mentioned on episode four, the best publicity we'll get since Homer Simpson went 3-D.

My wife and I enjoyed the show. Charlie, the mathematician character, definitely fits within the convex hull of math types I know. I liked the scene where Charlie asked several people to position themselves randomly and remarked that they were evenly spaced while real random points would have some clusters. Viewers might actually learn some interesting mathematical concepts watching this show.

At one point Charlie's physicist friend says something like "You are almost thirty at the peak of your game and most mathematicians only have five to six good years in them." Generally accurate but a little disheartening to this forty-one year old.

Machine Learning, Information Markets and Love

John Langford starts a new weblog Machine Learning & Theory.

2004 Year End Awards from Chris Masse's Predictions Market Digest (from David Pennock)

Is love more complicated than computational complexity? I can't make this up.

Does a Chess Program have Free Will?

A non-CS Chicago Alum asked me a question about free will and computation. I passed the question to David McAllester, an AI professor at TTI, and he gave the following interesting reply.

The idea that I could be simulated on a computer seems at odds with my subjective experience of free will and my intuition that my future actions are not yet determined — I am free to choose them. But consider a computer program that plays chess. In actual chess playing programs the program "considers" individual moves and "works out" the consequences of each move. This is a rather high level description of the calculation that is done, but it is fair to say that the program "considers options" and "evaluates consequences". When I say, as a human being, that I have to choose between two options, and that I have not decided yet, this seems no different to me from the situation of a chess playing computer before it has finished its calculation. The computer's move is determined — it is a deterministic process — and yet it still has "options". To say "the computer could move pawn to king four" is true provided that we interpret "could do x" as "it is a legal option for the computer to do x". To say that I am free is simply so say that I have options (and I should consider them and look before I leap). But having options, in the sense of the legal moves of chess, is compatible with selecting an option using a deterministic computation. A chess playing program shows that a determined system can have free will, i.e., can have options. So free will (having options) is compatible with determinism and there is no conflict.

Favorite Theorems: The First Decade

I have listed my favorite theorems for the first and second decades of my research career corresponding roughly to the third and fourth decades of research in computational complexity. This year I will list my favorite theorems for the first decade of complexity, 1965-1974.

As opposed to the previous lists, we have 30-40 years of hindsight to see what theorems have stood the test of time. Each month starting in February I will highlight one result and mention related work to show how computational complexity went from a simple but beautiful idea to an important subdiscipline of computer science.

Recommendation Letters

A few random comments as I read and write recommendation letters for various academic positions:

Back in the old days, a candidate would send a department a list of references and the department would send to each reference by postal mail a request for a letter which would be sent back by postal mail and followed up by a thank you sent again by postal mail. Faculty had a lot more secretarial support back then. This year I only got one such request, from a math department. Many departments have the candidates ask the recommendors to send letters directly by post and/or email. The best organized departments send the recommendors a link that leads to a secure upload page that puts the letter directly in the department's database.

Some misguided people like to send letters by post because they worry about the security of email and the electronic storage of their letters. Letters sent by post are far less secure. Copies of these letters must be made and these copies get left, on copy machines, in mailboxes in public areas, on peoples desks and in conference rooms. In any case it doesn't make sense to go crazy over security, any student with a little imagination can find a way to see their letters. Students: Don't do this. No good will come out of it.

There is an old saying "If a price is advertised as under $30 you can rest assured it is not $19.99." I take this saying into account when I read recommendation letters, particularly lines like "among the top half of complexity theorists graduating this year". In general I read letters more for what is not said than what is said.

"Strong potential" looks good for a fresh Ph.D. and the kiss of death for a senior candidate.

I ignore negative recommendations as probably personal issues. If you really dislike someone write a lukewarm letter. Seriously, if you don't feel you can write a strong letter for someone make up an excuse for why they shouldn't list you as a reference. Don't refuse to write if you get a request directly from a department. No letter is seen as a negative letter.

"I recommend" is a weak recommendation. "I very strongly recommend" is a strong recommendation. "I give my strongest recommendation" is a meaningless lie. "Don't hire this person because we plan to make him/her an offer and we want him/her for ourselves" is as strong as they get.

Theory for Dentists

Thanks to Rahul Santhanam for covering for me last week. If you are looking for a smart hard-working postdoc in complexity take a look at Rahul.

On the plane last week the passenger sitting next to me, a dentist from Vancouver, was reading a Scientific American article on quantum cryptography. Quantum cryptography got its start from people in the theoretical computer science field like Charlie Bennett and Gilles Brassard. For our field to flourish we must produce research of interest to others and to see outsiders reading about the fruits of our labor just for fun is a good sign.

Your Patience Has Been Rewarded (by guest blogger Rahul Santhanam)

For Lance is back, and raring to go. It has been an interesting one week, but on the whole, research is probably easier than blogging, and certainly less nerve-wracking. I wish I could say the same about my job search. Wish me luck.

Open papers (by guest blogger Rahul Santhanam)

Lance has posted quite a lot on conference papers, review processes and the like recently, so one more won't hurt. Because of the resource constraints on program committees and the page limits on submissions, we have "standard" FOCS/STOC papers, which may contain two or three main results which improve in a natural way on previous results, proofs for the results which have a certain minimum technical complexity, and a few clever new ideas underlying the proofs. This is a good thing in that it steadily advances the state of the art in established areas, and in that it creates a congenial climate for collaboration because results are efficiently transmitted (one need only note the difference from previous results) and proofs easily digested (by understanding the role of the new ideas).

But my personal preference is for papers which are more mysterious, in which the results may be a little less clean. Research is often awkward (as opposed to the products of research, which are more often beautiful than not). I like papers which reflect this, in which perhaps there is some backtracking and re-examination of assumptions because a conventional line of research is stalled , or in which the motivation is not a technical but rather a philosophical question, or in which a promising idea is proposed which hasn't yet found an interesting application, or in which a connection between two disparate areas is hinted at but not completely formalized. By their very nature, their acknowledgement of contingency, these papers open themselves up to the reader; they are speculative, not authoritative, and by their speculativeness they inspire speculation in the reader. Also, since the results in open papers may not be compelling in themselves, the authors may be forced to make a stronger case for their ideas - this lays bare intuitions which in normal circumstances are shrouded within proofs.

My personal favorite among open papers, reflecting my interest in pseudorandomness, is Sipser's "Expanders, randomness or time versus space", which is all of 4 pages long. I was wondering whether the STOC/FOCS climate has become less receptive to openness of late, but in fact during my time as a graduate student there have been several instances that have caught my attention... Here is a (necessarily subjective) list: this one, this one, this one and this one. And it is a vindication of openness, of the primacy of ideas over short-term results, that the last-mentioned paper led, directly or indirectly, to this.

Theory used to be Fun (by guest blogger Rahul Santhanam)

Was leafing through some old copies of SIGACT News from the 80s. Once the forests of facial hair had ceased to distract me, I was intrigued by glimpses of a mysterious event known as the FOCS Follies. I have no information about the provenance and history of this event, but I amused myself by imagining such an event taking place in the hectic and efficient world of the contemporary FOCS... Of course, the globalization of theory is a good thing, and talks still provide a medium for the expression of individuality.

Mandatory Technical Post (by guest blogger Rahul Santhanam)

The theory of derandomization has had many successes, but challenges remain. Perhaps the most significant of these are finding a deterministic poly time (or even subexp time) algorithm for arithmetic circuit identity testing, and finding a deterministic NC algorithm for perfect matching. A question that hasn't received as much attention as the above is whether fully poly time randomized approximation schemes (FPRASs) for #P-complete problems can be derandomized.

Question 1: Is there a natural #P-complete problem which has a fully poly time deterministic approximation scheme?

A good candidate is counting satisfying assignments to DNF formula, for which the best deterministic algorithm is more than a decade old, and takes slightly super-poly time. There is a beautiful theory of Monte Carlo Markov Chain based FPRASs for #P-complete problems, but I don't believe it is known how to derandomize any of these FPRASs.

Now, to weaken Question 1 slightly... Say that a randomized approximation scheme A for a function f is an FPRAS with symmetry breaking if with high probability, A outputs a single value that's a good approximation to f (as opposed to garden-variety FPRASs, which may output different values on different sequences of random bits, subject to the condition that most of these values are good approximations to f). FPRASs with symmetry breaking were studied in a paper by Cai, Lipton, Longpre, Ogihara, Regan and Sivakumar.

Question 2: Is there a natural #P-complete problem which has an FPRAS with symmetry breaking?

Question 1 (and hence also Question 2) has a positive answer under Nisan-Wigderson style circuit lower bound assumptions, which imply that any FPRAS can be derandomized. Moreover, if any FPRAS can be derandomized, BPP = P. What about the weaker assumption that any FPRAS can be converted to an FPRAS with symmetry breaking?

Question 3: Does the assumption that every function f which has an FPRAS also has an FPRAS with symmetry breaking imply any collapse of conventional complexity classes?

Recreational Complexity (by guest blogger Rahul Santhanam)

We all like problems. But it's sort of sad that as our careers develop, we get to spend less and less time on problems that don't offer opportunities for resume enhancement. I don't think twice about watching a 3-hour movie, but feel guilty if I spend more than an hour on a problem that has nothing to do with research...

A fellow grad student was TAing an algorithms class and posed a question about the change-making problem. In the change-making problem, you're given a set of denominations c1 > c2 > ... > cN and a value M and asked to find the minimum number of coins that add up to M. The greedy strategy is to choose as many c1's as possible, then as many c2's as possible etc. Is there a polynomial-time algorithm that, given a set of denominations as input, tells if the greedy strategy is always optimal for the set (i.e., optimal for every M)?

We pondered awhile, but then of course I had to ruin things by Googling the very elegant solution published by David Pearson a decade back.

Fresh-faced undergrads and first-year grads out there, resist the urge. Enjoy your freedom and treat each problem the same while you still can, before your research becomes too compelling (= compulsory)

World Series of Complexity Theorists (by guest blogger Rahul Santhanam)

Ex-guest blogger Adam Klivans is off to become the resident learning theorist at Austin. But no matter, Eli Ben-Sasson will be at TTI till the summer, and Prahladh Harsha returns in the fall. What is it with Bostonian theorists and Chicago anyway?

What's in a Name? Complexity (by guest blogger Rahul Santhanam)

Hullo, all. Nice of Lance to lease me this space for a week, I most sincerely hope he won't come to regret it. I was thinking about names. Lance is most economical, so why the "computational" in "computational complexity"? Any theory attempts to understand and explain complexity, so it's no surprise there's an ambiguity about the term "complexity theory". A complexity theorist could be (1) one of us, i.e., someone studying the complexity of solving discrete mathematical problems (2) someone studying the evolution of complex dynamical systems with reference to phenomena such as chaos, self-organized criticality, emergent structures and suchlike (3) someone studying the complexity of doing continuous mathematics, where only partial information is available about the input. And there may be further incarnations of which I am unaware. Journal names are instructive - the journal "Complexity" hosts theorists of type (2), "Journal of Complexity" harbors theorists of stripe (3), and of course we have "Computational Complexity" to ourselves. I wonder: when a non-scientist who is curious about science hears the term "complexity theorist", which of the above does he visualize? (2), most probably. I remember reading Mitchell Waldrop's book "Complexity" as an undergrad, and there have been several other popular books of the same flavor. Has computational complexity failed to reach out to a wider audience and define itself, or is it rather that we have aspired to a different goal: acknowledgement by the mathematics community of our significance?

While the advisor is away ...

I'm off the net next week. My student Rahul Santhanam will guest post in my absence. Enjoy!