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!

Spamalot

A few years ago an undergrad in my class did his programming project based on the movie Monty Python and the Holy Grail. He attached a note to the project suggesting that I see the movie. I should have failed him right there and then. He should have known that every nerdy American of my generation saw that movie several times and memorized most of the dialog.

To relive those glory days last night my wife and I went to see Spamalot, the new Eric Idle musical based on Holy Grail with a nifty cast of Tim Curry as King Arthur and David Hyde Pierce and Hank Azaria as lots of other characters. The show had many of the great bits from the movie ("just a flesh wound") but completely skipped others ("answer me these questions three"). The songs lacked memorable melodies but mostly had pretty funny lyrics. Besides following the rough plot of the movie the show also parodies big budget musicals allowing them to add a female lead who could sing (Sara Ramirez) and leading up to a happy ending that made me miss the non-ending of the movie.

In short I and the rest of the audience had a great time and laughed throughout but it won't go down in history as one of the great musicals.

Big Omega

We define big-oh notation by saying f(n)=O(g(n)) if there exists some constant c such that for all large enough n, f(n)≤ c g(n). If the same holds for all c>0, then f(n)=o(g(n)), the little-oh notation. Big-oh and little-oh notation come in very handy in analyzing algorithms because we can ignore implementation issues that could cost a constant factor.

To describe lower bounds we use the big-omega notation f(n)=Ω(g(n)) usually defined by saying for some constant c>0 and all large enough n, f(n)≥c g(n). This has a nice symmetry property, f(n)=O(g(n)) iff g(n)=Ω(f(n)). Unfortunately it does not correspond to how we actually prove lower bounds.

For example consider the following algorithm to solve perfect matching: If the number of vertices is odd then output "No Perfect Matching" otherwise try all possible matchings.

We would like to say the algorithm requires exponential time but in fact you cannot prove a Ω(n²) lower bound using the usual definition of Ω since the algorithm runs in linear time for n odd. We should instead define f(n)=Ω(g(n)) by saying for some constant c>0, f(n)≥ c g(n) for infinitely many n. This gives a nice correspondence between upper and lower bounds: f(n)=Ω(g(n)) iff f(n) is not o(g(n)).

On a related note some researchers like to say f(n)∈O(g(n)) viewing O(g(n)) as a set of functions. This trades off a nice clear unambiguous notation with something ugly for the sake of formality. Yuck.

Asher Peres, 1934-2005

By Netanel Lindner, Petra Scudo and Danny Terno via Christopher Fuchs

Quantum information science lost one of its founding fathers. Asher Peres died on Sunday, January 1, 2005. He was 70 years old.

A distinguished professor at the Department of Physics, Technion - Israel Institute of Technology, Asher described himself as "the cat who walks by himself". His well-known independence in thought and research is the best demonstration of this attitude. Asher will be missed by all of us not only as a great scientist but especially as a wonderful person. He was a surprisingly warm and unpretentious man of stubborn integrity, with old-world grace and a pungent sense of humor. He was a loving husband to his wife Aviva, a father to his two daughters Lydia and Naomi, and a proud grandfather of six. Asher was a demanding but inspiring teacher. Many physicists considered him not only a valued colleague but also a dear friend and a mentor.

Asher's scientific work is too vast to review, while its highlights are well-known. One of the six fathers of quantum teleportation, he made fundamental contributions to the definition and characterization of quantum entanglement, helping to promote it from the realm of philosophy to the world of physics. The importance of his contributions to other research areas cannot be overestimated. Starting his career as a graduate student of Nathan Rosen, he established the physicality of gravitational waves and provided a textbook example of a strong gravitational wave with his PP-wave. Asher was also able to point out some of the signatures of quantum chaos, paving the way to many more developments. All of these contributions are marked by a surprising simplicity and unbeatable originality.

Of all his publications, Asher was most proud of his book Quantum Theory: Concepts and Methods. The book is an example of Asher's scientific style: an uncompromising and deep understanding of the fundamental issues expressed in a form which is as simple and accessible as possible. It took Asher six years to carefully weave the threads of his book together. The great quality of the work is acknowledged by anyone acquainted with the final result.

In a favorite anecdote, Asher told about a reporter who had interviewed him on quantum teleportation. "Can you teleport only the body, or also the spirit?" the reporter had asked. "Only the spirit," was Asher's reply. Our community has been privileged to know him and have been touched by his spirit.

I am the cat who walks by himself is a charming twelve-page autobiography covering his life from his birth in the village Beaulieu-sur-Dordogne in France until his meeting with Aviva on a train to Haifa. The rest of his story is in his formal CV.

Embarrassing Mistakes

We talked about embarrassing moments in our careers recently. I've had talks gone bad and conversations with person A thinking they were person B. And once I had a little too much sake in Tokyo and I … never mind.

But alas my biggest embarrassments were the serious problems with published proofs in several of my early papers. So to start out the New Year with a clean slate I will list my failings. Don't blame my co-authors; I take full responsibility for all these mistakes.

• In my first major paper, The Complexity of Perfect Zero-Knowledge, I showed some properties of zero-knowledge proofs using the coins of a verifier. Turns out that doesn't work as I thought. Aiello and Håstad give a correct proof and new results using the coins of the simulator. See the appendix of Goldreich-Ostrovsky-Petrank for more details.
• In the conference version of the paper On the power of multi-power interactive protocols we had to reduce to error of a multi-prover proof system and wrote

  We can run the protocol in parallel without any problem since all messages are independent coin tosses.

  Actually correct as long as you interpret "without any problem" as an forty-page proof by Ran Raz. Section 6 of our journal version describes the problem and some earlier fixes.
• The paper Probabilistic Computation and Linear Time simply had a bad proof of the main result giving a relativized world where BPP was in BPTIME(n). Berg and Håstad discuss the issue. Rettinger and Verbeek have a purported proof of the non-adaptive case and Rettinger claims to have solved the general version in his thesis (in German).
• In the FOCS paper Using Autoreducibility to Separate Complexity Classes we claimed that all the EXPSPACE complete sets were autoreducible. We later realized this result would separate NP from L and discovered the FOCS paper had a bad proof. The autoreducibility of EXPSPACE remains open and settling it in either direction would have major complexity consequences. The journal version has more details.

The vast majority of my papers do have, to the best of my beliefs, correct proofs. But four mistakes is enough to gain a reputation and means you should not trust my proofs on face value. I have also learned this lesson and try to get reliable people to check over my proofs before I make them public.