Favorite Theorems: Efficient Computation

February Edition

How do we formalize the notion of efficient computation? Two important papers from the 60's suggest polynomial time algorithms are efficient though both caution against equating the concepts.

Paths, Trees and Flowers, Jack Edmonds, 1965.

The Intrinsic Computational Difficulty of Functions, Alan Cobham, 1964.

Edmonds paper will always be best known for giving the first efficient algorithm for matching on general graphs. But I list it here because of a section of his paper labeled "Digression". Edmonds talks about the difference between exponential and algebraic (polynomial) order though he cautions against any rigid criteria for efficiency.

An explanation is due on the use of the words "efficient algorithm"…I am not prepared to set up the machinery necessary to give it formal meaning, nor is the present context appropriate for doing this…For practical purposes the difference between algebraic and exponential order is more crucial than the difference between [computable and not computable]…It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion…However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence.

Cobham defined the class we now call P as important because of its machine independence.

For several reasons the class P seems a natural one to consider. For one thing, if we formalize the definition relative to various general classes of computing machines we seem always to end up with the same well-defined class of functions. Thus we can give a mathematical characterization of P having some confidence it characterizes correctly our informally defined class. This class then turns out to have several natural closure properties, being closed in particular under explicit transformation, composition and limited recursion on notation (digit-by-digit recursion).

Cobham also offers a caution.

The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of effectiveness. But the emphasis is different in that the physical aspects of the computation process are here of predominant concern.

Perhaps Cobham realized there might be future models of computation that may not correspond to his class P. Later developments of randomized and quantum computation will show that perhaps we cannot have a fixed notion of efficient computation.

The Researcher's Dilemma

I finally read Clayton's Christensen's The Innovator's Dilemma. A few years ago an NEC executive gave a talk using the ideas in the book to explain NEC's interest in quantum computing.

Christensen divides new technologies into two groups: sustaining and disruptive. Sustaining technology helps improve a product for its current customers for example Intel building a faster microprocessor. Disruptive technology is technology that is not initially useful for a big company's current clients. So other newer and smaller companies develop the technology for a niche market. But eventually the technology improves to meet the needs of the original big company's customers at a much lower cost. At this time the big company cannot catch up with the new technology and loses their main business to the newer startups. Christensen gives many examples such as the development of smaller disk drives and the advent of discount stores like Target hurting bigger retailers like Sears.

The book makes some solid arguments but determining which technologies will be disruptive is quite difficult. So companies need to place lots of bets perhaps why NEC funds quantum computing research just in case it becomes a disruptive technology in the future.

Do the same concepts apply to research? In complexity we have had some disruptive technologies, for example, the PCP theorem for hardness of approximation or the idea of Nisan and Wigderson of using hard languages to derandomize, or going way back the whole concept of NP-completeness. Other concepts like circuit complexity have not been as disruptive as originally thought. Also one could view tools like the probabilistic method or extractors as disruptive.

What could happen to large companies can also happen to researchers. Suppose George is a researcher who creates new results building on current ideas with small twists (sustaining technology). George ignores some new ideas in complexity because it doesn't seem to help him prove new results in his area. But as those new technologies develop they later allow others to go well beyond what George has done. Now George is behind the curve on the new disruptive technology and can no longer play an important role even in his own field.

What can George do? He can learn the new techniques or he can change fields. And often the newcomers never properly learn the old tools and George can still pull a few surprises out of his hat.

Finding Duplicates

Here is an interesting problem given by Muthukrishnan during his talk in the New Horizons workshop.

Start with an array A of n+1 entries each consisting of an integer between 1 and n. By the pigeonhole principle there must be some i≠j and a w such that A(i)=A(j)=w. The goal is to find w. Depending on A there may be several such w, we want to find any one of them. The catch is that you only get to use O(log n) bits of memory.

First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing.

Now suppose A is streamed, that is we get in order A(1),A(2),…,A(n+1) and then get another pass etc. How many passes do you need to find a w?

You can find w in n+1 passes just by trying each possible value for w. With a little work you can use O(log n) passes doing a binary search.

Muthukrishnan asks whether the number of passes needed is Ω(log n) or O(1) or something in between.

Theory in Japan

Japan has produced some excellent theorists, like Seinosuke Toda who won the 1998 Gödel prize for his paper reducing the polynomial-time hierarchy to counting solutions of NP problems. But Japan has not had the large international impact in theoretical computer science as countries like Israel, India or Hungary.

In this trip I am seeing signs that this may change for the better. The conference is kicking off a new project New Horizons in Computing that shows a serious commitment of the Japanese government to computer science theory. The large turnout, over 130 registrants the majority of which are students, shows a keen interest in theory from the academic side as well.

I'd like to see more Japanese go abroad for graduate work and postdoc positions and more Japanese universities making theory an important part of their computer science programs. But given the excitement I see at this meeting I am very hopeful that Japan will also become a true theory powerhouse in the near future.

Are we the university?

Two fellow (and slightly better known) Chicago professors Gary Becker and Richard Posner run a joint weblog on various social issues. This week they tackle the question of whether the faculty "own" a university. Becker says yes and Posner says no. I have to go with no. I believe the board of trustees acts as the owners on behalf of the "shareholders" known as alumni. Many professor do act for the betterment of the university but professors come and go are no more owners than players on a baseball team.

Another question that comes up in discussions is who are the university's customers? Some possible answers:

• Students. But why is their success based on their performance?
• The Government who give the grants for research.
• The employers of the students.
• Society at large.

Perhaps the mistake is in making the analogy between university and corporation.

New Horizons in Japan

I'm off to Japan for a Workshop on New Horizons in Computing that kicks off a new theory project sponsored by the Japanese Ministry of Education. This will be my first time in Kyoto and my first trip to Japan since I was stranded there after September 11. Let's hope history doesn't repeat itself.

I'll be talking about my favorite theorems of the past decade but you, my loyal weblog readers, have seen it here first.

Ramanujan's Lost Notebook

Below the paid ads, Gmail gives me related links on the side of my email. In a discussion on a bad P ≠ NP proof (don't ask) Gmail pointed to this interesting article on Ramanujan's lost notebook.

Now only if we could find Gödel's lost notebooks on P versus NP…

The Complexity of the Nash Equilibrium

We know only a few natural problems in NP that are not known to be NP-complete or in P. The two most often named are factoring and graph isomorphism. Another that has come to forefront is Nash Equilibrium.

Given two n x m matrices A and B, consider the game where simultaneously player I picks a row i and player II picks a column j. Player I's payoff is A(i,j) and player II's payoff is B(i,j).

Nash proved that for all A and B there are probability distributions σ on the rows and τ on the columns so that if the player I plays according to σ and player II plays according to τ

1. There is no i such that if player I chooses row i his expected payoff will increase with player II still playing according to τ.
2. There is no j such that if player II chooses column j her expected payoff will increase with player I still playing according to σ.

The computational problem is to find σ and τ given A and B. It's a major open question whether a polynomial-time algorithm exists.

Using linear programming we can find Nash Equilibrium in a zero-sum game (A(i,j)=-B(i,j) for all i,j) or if we know the set of i where σ(i)=0 and the j where τ(j)=0.

We can also find a correlated equilibrium in polynomial-time which is a distribution on pairs (i,j). However to implement a correlated equilibrium you need either a third trusted party or use some cryptographic techniques.

I don't know a good survey on the complexity of Nash Equilibrium but perhaps my readers will have some good references.

Factoring NUMB3RS

Scott Aaronson weighs in on last night's NUMB3RS episode "Prime Suspect". Mild Spoiler Warning.

Last night's NUMB3RS again centered around complexity. A brilliant mathematician (not Charlie) tells his friends that he's on the verge of proving the Riemann hypothesis -- and not only that, but his proof will somehow yield a fast factoring algorithm. When the bad guys get wind of this, they kidnap the mathematician's six-year-old daughter, demanding the algorithm as ransom. But the mathematician refuses to cooperate with the FBI investigation of the kidnapping. The reason, we later learn, is that the mathematician has fooled himself: he doesn't have a proof or an algorithm, and he's terrified the bad guys will find out. (One thing that has to be said for NUMB3RS: in contrast to, say, Good Will Hunting, it does get across the idea that math problems are hard.) So Charlie has the improbable task of helping the other mathematician fake a factoring algorithm -- apparently, the bad guys won't be savvy enough to run whatever they get on a few random instances!

In a way, this episode represents a retreat from the premise that "math helps us solve crimes" -- I mean, no duh it helps, if the crimes in question happen to involve polynomial-time factoring algorithms! But in my opinion, the fact that math was actually integral to the plot helped to make this the most effective episode so far. In contrast to the P versus NP episode, this time they actually explained a little about prime numbers, RSA, and factoring, and did a fairly non-egregious job by TV standards. Admittedly, an RH proof leading to a factoring algorithm seems pretty farfetched, but what path to efficient factoring isn't farfetched? (Other than building a quantum computer, of course.)

My main criticism is that, whenever Charlie and the other academics open their mouths, I feel like I'm listening to foreigners speaking perfectly grammatical sentences that no native speaker would ever utter. The phrasing is just too pretentious -- a trivial example being that everyone calls the Riemann hypothesis "Riemann's hypothesis." If they wanted to, the writers could easily fix this problem by reading the scripts to mathematicians, and seeing which lines pass the cringe test.

Computer Science Recruiting

I've already heard from several graduating students who have had few or no interviews scheduled and are really worried about finding a job next year. Don't panic yet.

CS recruiting is not a well coordinated affair running from January to June and often beyond. Each department determines their needs and resources and invites candidates for interviews, makes some of them offers and makes later interviews and offers as the first offers are turned down or as resources change, like a current faculty member decides to go somewhere else.

What does this mean? There is a small set of top candidates that get most of the interviews and initial offers. Some of these candidates can tie up offers for months because they are waiting for some other university to decide or they are simply indecisive and no one puts pressure on them to decide.

For students not in this top group they will get few or no early interviews and feel like they will never get a job. The market will shake itself out and dig deeper into the applicant pool. Departments that have theory as a secondary priority will realize they can't find good candidates in their top priority and start looking at theory candidates. In short the recruiting is game is just beginning.

Meanwhile broaden your search and look at places you may not have considered before. Work on your job talk even before you have anything scheduled and give a practice talk in your department. But mostly keep busy and get your mind off the job market. I found working hard on the thesis helps.

Complexity Accepts

For this weblog it's the Super Bowl, the Grammys and the Oscars all rolled into one: Announcing the accepted papers of the 2005 Conference on Computational Complexity.

It's Safe to Study in America Again

I've seen several pointers to this nice article on origami and Erik Demaine in the Science Times section of yesterday's New York Times but also check out today's editorial page.

Thanks to pressure from prestigious academic and scientific organizations and leaders of high-tech industries, the administration added staff and streamlined the [student visa] process so clearance now takes less than two weeks, on average.

The capstone was a policy change announced last week that made a clearance valid for four years for students and two years for working scientists, making it easier for them to stay in the country for the duration of their study or research. America's reputation for welcoming scholars from around the world can only benefit.

We should always treat such news cautiously but hopefully these new policies will encourage more foreign students to come study in the states.

Update: Also in today's Times, an article announcing the ACM Turing Award that went to Robert Kahn and Vinton Cerf for their early work on the internet. The Turing Award is the closest computer science has to the Nobel Prize and its nice to see the New York Times taking it as such.

From Industry to Academics?

A reader question (anonomized):

How should you decide whether to go into industry? Are there ways back after you have sold your soul? The occasion: I got an offer from a major internet company to work at one of their labs. I have until Monday to decide. At this moment, I don't have any promising leads to do the research I'm interested in inside academia. My advisor says that if I don't like it at this company I can always come back, but I am a bit doubtful of that…what is your take on this?

It depends on the kind of industrial lab and how long before you would go back into academics. If you go to a basic research lab and continue to produce academic papers then you can find an academic job afterwords. You'll lose a little by not having teaching experience but that gets offset by having more time for research.

If on the other hand you go to an industrial job for even a couple of years and don't continue to produce academic research papers or attend conferences it will be very difficult to find an academic job afterwords particularly in a theoretically oriented field.

If you really want to stay in academics take an academic job that might not be to your liking and work hard to produce good research and try again later.

Do any of you readers have stories of people that have successfully gone from industrial jobs back to academics?

Just Say No

I have one word of advice that applies especially to junior faculty: No.

You will be asked to referee papers, look at graduate applications, look a faculty applications, write reports and recommendation letters. You will be asked to sit on committees: curriculum committees, space committees, program committee, web page committees, budget committees, planning committees and other committees you would never have imagined. You'll have committee meetings at the departmental, divisional and university levels as well as committees to serve the broader theory community. You will be asked to organize workshops, conferences and edit special issues. You'll also be teaching, writing grants and going to faculty meetings.

All of the above are good things to do. But do all of the above and you'll never get tenure. You need time for research. So learn to limit yourself, learn to say "no". I'm not saying not to do any of the above. Most of these tasks have to get done; you should do your fair share and be a "good citizen". But you don't need to agree to every request, feel free to turn down requests when you feel yourself getting overloaded. If you gain a reputation as someone who can't say "no" people will take advantage of you. And don't fall for the "You are the only one who can do a good job" ploy.

If you try to do too much you won't do anything particularly well. I would much rather have someone say "no" to me than saying "yes" and doing a mediocre job.

Favorite Theorems: The Seminal Paper

Introduction

We should start off off my list of favorite theorems from the first decade of complexity with the seminal paper in complexity, the one that gives the field and this weblog its names.

Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, 117 (1965), 285-306.
This paper formalizes the idea that we now all take as obvious that we should use Turing machines to determine complexity of complexity by measuring time as a function of the size of the input. Ever since the Hartmanis-Stearns paper we measure nearly every resource (time, space, random bits, circuit depth, etc.) as a function of the input size.

This paper also gives the first hierarchy of classes, showing that for nice functions t and u with t²(n)=o(u(n)) then there are problems solvable in time u(n) but not time t(n) on multitape Turing machines. Soon later Hennie and Stearns showed the same result if t(n) log t(n) = o(u(n)).

Maybe He Missed Some Math

Thomas Garrity's book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says

The N in NP is somewhat of a joke; NP stands for "not polynomial".

and later

While initially the smart money was on P ≠ NP, today increasingly the belief is that the statement P=NP is independent of the other axioms of mathematics. Few believe P=NP.

For the record NP stands for "Nondeterministic Polynomial-Time" (not a joke) and at least this complexity theorist feels that a proof of P≠NP exists and we just haven't found it yet. Just because we are too stupid to find the proof doesn't mean the problem is independent.

I don't mean to be hard on Garrity. He should be lauded for including the P versus NP problem in his book.

Thanks to Varsha Dani for the pointer.

Guest Post on Numb3rs P vs NP Episode

Suresh has been doing a fine job reviewing the Numb3rs episodes. Nevertheless Bill Gasarch wanted to write a guest post on the P versus NP episode which was the second episode broadcast and not the fourth as I had previously mentioned. But first my comment to Charlie: Don't let your brother mess up your priorities. Go back to solving P versus NP. So what if a few bank robbers get away?

Now on to Bill's Guest Post:

REVIEW OF SECOND EPISODE OF NUMB3RS USE OF P vs NP.

This is the `P vs NP' episode.

"Are you still working on that P vs P thing"

"Its the P vs NP thing"

They mentioned P vs NP ALOT of times.

PROS: ANY mention of our favorite problem on TV is good. This may be the first mention of P vs NP on an entertainment show since Homer Simpson fell into the third dimension where there were all kinds of equations floating around in the background including P = NP.

CONS: Wasted Opportunity. They made NO attempt to explain the problem. Could they have? Trying to color a map with 3 colors might be the problem easiest to explain. Or TSP. Might be hard to tie that to a crime, but minesweeper is also contrived. For that matter, could they have explained minesweeper better, and add something like "One way to solve it is to look at all possibilities. Even with really powerful computers, that could take to long. We want to know, is there a faster way?" I would not even try to explain NP or `checkability' I would just say that here are problems we can solve by looking at all possibilities, and we want to know if we can do substantially better.

ODD POINT: They mentioned a few times that it was `unsolvable' What did they mean? Options-

1. Charlie was trying to prove P=NP and this is unlikely to be true
2. Charlie was using techniques from recursion theory that likely to not work because of the oracles. (the what?)
3. Charlie was using proofs that naturalize, which won't work because of the results of Razborov and Rudich (Judd Hirsch: So use unnatural techniques)
4. The problem is independent of PA
5. The problem is independent of ZFC
6. The problem is just very very hard.

Likely they meant 1 or 6 (SARCASM ALERT: 2-5 were not meant to be taken seriously). But they should have spoken more clearly about this.

PRO: They do (in general, not just this episode) show Math in a good light and show Mathematicians in a good light.

PREDICTION: Will be canceled within 1.5 years. Don't need Charlie's math to predict that.

The Super Bowl Parties

My old apartment-mate Eric Schwabe came over to watch the game last night and brought along old posters he had from the Super Bowl parties we used to throw as grad students at MIT. The Lance Fortnow Super Bowl Party continued at MIT after I left with a much larger crowd in my absence. A few years later it morphed into the Who the Hell is Lance Fortnow Super Bowl Party. Around this time (about 1992) an MIT student was excited to meet me at STOC not because of any research I had done but because he had been to "my" party. Eventually even the memory of the memory of me faded away and so did the party.

What happens now? We invited a few friends over for the game, every single one of which left early to put their respective kids to bed.

Information Markets and Quantum Computing

The DIMACS Workshop on Information Markets drew a neat crowd, a mix of computer scientists, economists (mostly experimental) and members of industry from companies as big as Microsoft and so small they are run by individuals in their spare time. Information markets create securities that can aggregate people's beliefs and help predict the likelihood of future events.

This workshop reminded me of the early conferences in quantum computing a decade ago. Quantum computing back then had some promising research (factoring algorithms for example) and no one was sure whether it would lead to whole new computing paradigm or just disappear into the ether. Information markets are also a new technology with some promising research (mostly analytic and experimental) and no one knows whether it will revolutionize the way everyone does prediction, information aggregation and decision making or just slowly disappear.

Information markets face different challenges than quantum computing. The technology already exists to run efficient markets and better tools are being developed. However the field needs to convince business and governmental leaders of the value and accuracy of the markets, overcome the stigma from the terrorism futures scare and find ways to overcome the legal issues relating to gambling in running real money markets.

Quantum computing needs to deal merely with the laws of physics but information markets need to deal with the laws of the United States of America.

Update 2/9: Ken Kittlitz's report on the workshop. (Thanks to Chris Masse)

Internet at Conferences

One of my students wanted me to complain in my weblog at the lack of wireless access in conferences like the recent SODA meeting. Sorry but I don't agree. I've discussed before how I find internet at conferences reduces conversation between participants and prevents us from escaping from work back home. Is it so bad that the SODA participants were forced to (gasp) talk to each other?

On that note let me finish this post so I can pay attention to the talk.

How to Judge a Weatherman?

Each day a weatherman gives a probability p of rain for the next day and each day it either rains or it doesn't. How do we judge the quality of these forecasts? A first attempt uses linear scores, p if it rains, 1-p if it doesn't. However when you analyze this system the weatherman should predict p=1 if his belief is greater than 1/2 and p=0 otherwise.

A better measure is the log loss. The weatherman gets penalized -log(p) if it rains and -log(1-p) if it doesn't. A weatherman now has the incentive to announce his belief. There are other scoring functions with this property but the log loss has some nice properties such as the best a weather could hope to achieve is exactly the entropy of the distribution. The log loss and other measures are often used to analyze prediction mechanisms such as information markets.

Dean Foster and Rakesh Vohra have a different take looking at a notion called calibration. Here you take all the days that the weatherman predicted 70% chance of rain and check that 70% of those days it actually rained. A prediction algorithm calibrates a binary sequence if for finite set of allowed probabilities, each of the subsequences consisting of predictions of probability p have about a p fraction of ones. Foster and Vohra showed that some probabilistic calibration scheme will calibrate every sequence in the limit. In other words you can be a great weatherman in the calibration sense just by looking at the history of rain and forgoing that pesky meterological training.

Dean Foster and Sham Kakade gave a couple of interesting talks at the Bounded Rationality workshop giving a deterministic scheme that achieves a weak form of calibration and use it to learn Nash equilibirum in infinite repeated games.

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.

Complexity Year in Review

Theorem of the year goes to Omer Reingold who shows Undirected Connectivity in Logarithmic Space, settling the long-standing open problem. Also of note, Ran Raz's lower bounds on multilinear formulas and a series of paper extracting randomness from independent sources I had mentioned earlier as well as new improvements by Raz. We had many other great results throughout the year, check out the ECCC to sample many of them.

The National Science Foundation and computer science funding face a challenging future. We have seen the end of the ITR program that has poured needed money into IT research. CISE reorganizes (putting complexity theorists and numerical analysts into the same program for example) as they struggle to meet a new reality of CS funding. To add to the burden the NSF had an actual decrease in its funding for FY 2005.

The decrease in foreign graduate students as US schools made news over the past year. The difficulty in obtaining visas since the terrorist attacks in 2001 certainly play a role but I give more weight to stronger local alternatives manned by many of those foreign students we have educated over the last several decades.

We lost three prominent members of our community: Shimon Even, Carl Smith and Larry Stockmeyer.

Outside of complexity we had an election that divided this country (but not the scientists), the Red Sox winning the world series and an ongoing struggle in Iraq. Unfortunately the year ends with a terrible natural disaster and we all should support the efforts to help those affected recover from this tragedy.

Copyrights on Conference and Journal Papers

A guest post from Alan Selman

It is a common and acceptable practice to present a preliminary version of a paper at a conference and then to submit the full paper to a refereed journal. The Foreword of a recent STOC proceedings states, for example,

The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.

That is the ideal. In practice, many of us have been in the habit of putting complete versions of accepted papers in conference proceedings. This is not a wise strategy. Assuming that the publisher of the conference proceedings holds copyright of the papers that appears in the proceedings, the paper that one submits to a refereed journal must be substantially different from the one that appears in a conference proceeding in order to avoid copyright infringement. I asked my contact at Springer, the publisher of the journal Theory of Computing Systems, how different the journal version of a paper should be from the conference version, and was told to use 25% as an acceptable guideline. This is a reasonable response that should not too difficult to manage for theorists, and can be taken up by proofs and explanations that were not included in the conference version. I should add however, that Lance Fortnow asked the same question of IEEE, the copyright holder for papers that appear in the Conference on Computational Complexity, and the response was far more onerous. Lance's contact at IEEE called for 30% to 70% new material, and material from the original paper should be there only to support new ideas. I would rather abide by Springer's recommendation than IEEE's. The essential point is that the journal version must be essentially different from the conference version.

Computation and the Socio-Economic Sciences

Fred Roberts, Rakesh Vohra and myself are co-charing the DIMACS Special Focus on Computation and the Socio-Economic Sciences, a series of workshops and other activities designed to bring together computer scientists and social scientists. The focus has already hosted some good workshops on topics like Electronic Voting and Auctions. Let me put in a plug for a couple upcoming workshops.

At the end of January, Richard McLean, Daijiro Okada and myself are organizing a workshop on Bounded Rationality at Rutgers. Bounded rationality looks at game theory questions like equilibria with computationally-bounded participants.

Immediately following the Bounded Rationality workshop is the workshop on Markets as Predictive Devices (Information Markets). The organizers Robin Hanson, John Ledyard and David Pennock have created a program with a set of speakers that spread the range from theory to practice in markets designed to estimate the probability of future events. The program ends with a panel discussion on the Policy Analysis Markets that came under fire a year and a half ago for its "terror futures".

In mid-April, Rakesh Vohra and I are organizing a workshop on Large-Scale Games to be held at Northwestern. This workshop will examine questions in game theory that deal with issues in large scenarios like the internet with many players, incomplete information, lack of common knowledge, asynchrony and related problems.

We have two other scheduled workshops in the focus, Polyhedral Combinatorics of Random Utility in June and Yield Management and Dynamic Pricing in August, and many more workshops under development.

Tragedy in Asia

Chennai, the location of the recent FSTTCS conference reviewed in the last post, was one of the areas hit hard by today's earthquake caused tsunami. The globalization of science really makes these tragedies seem close even to those of us on the other side of the planet.

Our condolences and prayers go to those in all areas affected by today's events.

FSTTCS 2004 at Chennai

By Prahladh Harsha and Jaikumar Radhakrishnan

It was nice to be back in Madras after a long time and even nicer to meet friends from MIT and elsewhere during this year's Foundations of Software Technology and Theoretical Computer Science Conference. FSTTCS is the longest-running international conference on computer science in India, and is organized under the aegis of the Indian Association for Research in Computing Science (IARCS).

The 24th edition was held in Chennai between Dec 16 and Dec 18. The conference was preceded by two workshops on Algorithms for dynamic data (Dec 13 - 14) and Logics for dynamic data (Dec 15). Here are a few statistics about this year's FSTTCS: 38 accepted papers (out of 178 submitted from 38 countries), attendance of about 175 (nearly 35% from outside India). The invited speakers: Pavel Pevzner (UCSD), Javier Esparza (Stuttgart), Piotr Indyk (MIT), John Reynolds (CMU) and Denis Therien (McGill). The proceedings of the conference were published by Springer in LNCS series.

FSTTCS attracts papers in Logics & Semantics and Algorithms & Complexity. Biased by our interests, we attended only the presentations on Algorithms & Complexity. In our view, the highlights were:

• M Fürer, S P Kasiviswanathan, An almost linear time approximation algorithm for the permanent of a random (0-1) matrix.
• A K Ponnuswami, H Venkateswaran, Monotone Boolean circuits for bipartite perfect matching require exponential size.
• L Radamacher, S Vempala, Testing geometric convexity. This paper demonstrates that testing whether a given set S in R^n is convex or far from convex (in the property-testing sense) can be determined by queries, whose number is independent of the actual size of the set S, but is however exponential in the dimension of the space (i.e., n). The set S is presented to the tester by a membership oracle and a random oracle.
• J Hitchcock, A Pavan, Hardness hypotheses, derandomization and circuit complexity. This paper shows that the NP-machine hypothesis is implied by both the Measure hypothesis and pseudo-NP hypothesis. These 3 hypotheses are some of the commonly used hypotheses in derandomization. Furthermore, the authors show that several of the derandomization and circuit lower-bound results that are known to follow from the latter two hypotheses also follow from the NP-machine hypothesis.
• J Kempe, A Kitaev, O Regev, The complexity of the local Hamiltonian problem. The local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It was known that the 1-local Hamiltonian problem is in P while the k-local Hamiltonian problem is QMA-complete for k >= 3. This paper settles the case for the 2-local Hamiltonian problem and shows that it is also QMA-complete. Thus, the k-local Hamiltonian problem is similar in spirit to MAX-k-SAT which is NP-complete for k > = 2.

Some authors could not attend the conference. The paper Minimum weight pseudo-triangulations by J Gudmundsson and C Levcopolous was presented beautifully by Mark de Berg. The paper on No, coreset, no cry by S Har-Peled, was presented by Kasturi Varadarajan. The author did not get a visa in time from the Chicago consulate (there are some advantages to traveling on an Indian passport), and had sent a recording of his presentation. In the end, Kasturi did a wonderful job using only the slides, but one was left wondering what the video looked like.

Prof. Rani Sirmoney, who turned 75 in July 2004, was honored in a special session at the conference. Prof. Sirmoney is a senior and highly respected theoretical computer scientists in India who works in the area of Formal Languages, Automata Theory, Machine Learning and DNA Computing. She has nurtured several generations of researchers through her teaching and collaborations. In her speech, she thanked her colleagues at the Madras Christian College for their support and encouragement, and mentioned, among other things, that she never faced any gender-based discrimination at that institution.

Favorite Theorems Recap

In 1994, I listed My Favorite Ten Complexity Theorems of the Past Decade in conjunction with an invited talk at that year's FST&TCS conference. Over this past year in this weblog I went back and picked my favorite ten complexity theorems of the decade since that first paper.

• Derandomization (Impagliazzo-Wigderson)
• Primality (Agrawal-Kayal-Saxena)
• Probabilistically Checkable Proofs (Håstad)
• Connections (Trevisan)
• Superlinear Bounds on Branching Programs (Ajtai)
• Parallel Repetition (Raz)
• List Decoding (Sudan)
• Learning Circuits (Bshouty-Cleve-Gavaldà-Kannan-Tamon)
• Quantum Lower Bounds (Ambainis)
• Derandomizing Space (Saks-Zhou)

The purpose of these endeavors is not just to have a top ten list but to use these great results to highlight several areas in computational complexity where we have seen significant progress in recent years. Ten areas do not do justice to complexity and we also have great results in proof complexity, Kolmogorov complexity, constructions of expanders and extractors, zero-knowledge proofs and structural complexity.

We'll do this again in ten.

Numb3rs

Coming in January to the American television network CBS, a series about a FBI agent who recruits his brother, a math genius, to help solve crimes. I don't hold much hope for realism in Numb3rs (anyone remember Q.E.D.?) but any show that shows mathematicians in a good light helps shape public perception of our field.

I would like to know the "actual events" that inspired this series.

Ooscla

One of my Indian graduate students mentioned the university yookla and gets confused when I talk about Texas (not UTA) or Illinois (as opposed to UIUC which is too easily confused with UIC).

So for the foreigners out there, here is a quiz for the common names for some major American universities, which all native-born Americans know because of their sports teams.

• USC (not ooscla or USCLA)
• South Carolina (not USC)
• Wash U (not woostle) as opposed to Washington or George Washington or Wash State
• California or just Cal. Though I would never say "Cal Prof Luca Trevisan"
• UTEP this time pronounced U-tep.
• Bama as opposed to UAB
• Mizzou
• Ole Miss
• UVM
• Wisconsin as opposed to UWM
• Maryland not UMCP as opposed to UMBC
• Miami (FL) as opposed to Miami (OH)

I could go on forever. Sometimes the name depends on where you say it. In Illinois we have Northern, Southern, Western, Northeastern as well as Northwestern.

Quality Matters

A commenter yesterday asked about a Crooked Timber post arguing that many strong departments place an emphasis on hiring students from other strong departments more than their actual publication record. The Crooked Timber post focuses on the social sciences and the hard sciences can and do put more focus on research itself.

In computer science, particularly in theoretical computer science we can really judge the quality of a student's research in a more objective way than a paper in say sociology. It does not matter where you got your Ph.D., if you didn't have strong results as a graduate student you won't find employment at a top university. If one does have solid results from a lesser known school one can find a top academic job though admittedly this happens less often.

I won't deny a strong correlation between where you got your Ph.D. and where you get employed: The best undergraduates choose the best graduate schools. At the strong schools you can usually find stronger faculty as potential advisors, stronger fellow students to work with and push you and you will have letter writers with stronger credentials when you do enter the job market. There is a social network among stronger schools that we cannot ignore. And some places, particularly those without experts in an area, will put too much emphasis on a student's department.

But we can better measure the quality and importance of a student's research and impact and that always plays the most critical role in whether one offers that person a position in a particular field.

Decryption by Clancy

Consider the following paragraphs from Tom Clancy's 1998 novel Rainbow Six.

The phone they spoke over was the Russian version of the American STU-3, the technology having been stolen about three years before by a team working for Directorate T of the First Chief Directorate. The internal microchips, which had been slavishly copies, scrambled the incoming and outgoing signals with a 128-bit encryption system whose key changed every hour, and changed further with the individual users whose personal codes were part of the insertable plastic keys they used. The STU system had defined the Russians' best efforts to crack it, even with exact knowledge of the internal workings of the system hardware, and they assumed the the Americans had the same problems—after all, for centuries Russia had produced the world's best mathematicians, and the best of them hadn't even come up with a theoretical model for cracking the scrambling system.
But the Americans had, with the revolutionary application of quantum theory to communications security, a decryption system so complex that only a handful of the "Directorate Z" people at the National Security Agency actually understood it. But they didn't have to. They had the world's most powerful supercomputers to do the real work. They were located in the basement of the sprawling NSA headquarters building, a dungeonlike area whose roof was held up with naked steel I-beams because it had been excavated for just this purpose. The star machine there was one made by the company gone bankrupt, the Super-Connector from Thinking Machines, Inc., of Cambridge, Massachusetts. The machine, custom build for NSA, had sat largely unused for six years, because nobody had come up with a way to program it efficiently, but the advent of quantum theory had changed that, too, and the monster machine was now cranking merrily away while its operators wondered who they could find to make the next generation of this complex machine.

I doubt anyone could turn a souped-up ConnectionMachine into a quantum computer. But one could imagine some smart NSA scientists finding a way to simulate a variation of Shor's quantum factoring algorithm on such a device, well enough to break moderately long RSA codes. Just thinking.

Favorite Theorems: Derandomizing Space

November Edition

We started this list of favorite theorems with derandomization of time classes. Now we end the list by looking at derandomizing space-bounded classes.

Over the last fifteen years we have seen several exciting results on removing randomness from space. Unlike time they require no hardness assumptions but until very recently didn't achieve full derandomization.

The techniques of Savitch's Theorem give us that randomized logarithmic space sits in deterministic log² space. We will focus on results that reduce the space needed to simulate randomized algorithms and the space for the most well-known randomized space algorithm, undirected s-t-connectivity.

Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. Nisan, Szemeredi and Wigderson give a log^3/2 algorithm for s-t connectivity. Saks and Zhou give the same bound for every problem in randomized log space.

BP_HSPACE⊆DPSACE(S^3/2) by Michael Saks and Shiyu Zhou

Saks and Zhou's result remains the best known bound for randomized logarithmic space but we can do better for s-t connectivity. Armoni, Ta-Shma, Wigderson and Zhou improved the s-t connectivity bound to log^4/3 space. And just a few weeks ago we had Reingold's result putting s-t connectivity in the optimal logarithmic space, currently a front runner for the next favorite theorems list in 2014.

Can We Fairly Teach and Grade?

Academic bloggers (like Jeff and Suresh) are up in arms about a column by Ailee Slater in the University of Oregon student paper.

We are currently paying a large amount of money to attend this University and receive an education. If I have paid to be taught something, shouldn't there be a repercussion for the teacher rather than, or at least as well as, the student when knowledge has not been taught?

Although teachers cannot be responsible for the self-failings of their students, it still seems unfair that they are allowed to judge how much a particular student is learning. I pay the teacher to teach me, and then I get slapped with the label of failure if the teacher deems that I haven't learned the correct information?

If students only paid for education they why would my grade matter? Whether I give you an A or a D won't affect how much you actually learned over the quarter. Students also want a certificate of quality of that education (a diploma and a transcript) to further their future careers. No legitimate university would give such certification just for tuition money. They need to verify that the students have indeed learned. That's why we have a grading system.

But Ailee does have a good point: I do have a conflict grading the students based on what I tried to teach them. Most of us try our best to grade fairly but deep down we know if a hard-working student hasn't mastered the material perhaps we should have taught differently. We often tend to overcompensate for this bias leading to grade inflation.

Unfortunately, other than standardized exams, I see no other reasonable alternatives of evaluating students. So professors need to grade students as fairly as they can and students need to acknowledge that education is not just a right but also a responsibility even when they are paying for it.

A Map of Complexity Classes

Iowa State graduate student Chad Brewbaker created a graphical map of the complexity classes in the zoo. Who says you can't have fun with complexity?

The Other Nigerian Scam

Volunteer to organize a conference and I guarantee you will get an email like the following

I am a computer scientist from Nigeria. I am interested in attending your conference. I come from a very poor university and I am in need of funds and/or please write me a letter for visa.

They play to our vanity and our desire for diversity. Wow, Africans interested in computational complexity! Don't be fooled, in nearly every case they have no interest in computer science, they just want an easy way to come to Europe, the US or Canada.

There is that small chance a poor African student really is interested in complexity so I typically reply to such letters by

Thank you for your interest in our conference. Please send us your latest CV and a statement explaining your reasons for attending the meeting and we will be happy to consider your request.

In every case I have never heard from the letter writer again.

The NSF Gets Some Attention

The National Science Foundation rarely gets mentioned in the popular press. After the recent budget cut, the NSF now gets some mention, including a New York Times article, editorial and Thomas Friedman's column and an editorial of the the San Jose Mercury News. Perhaps taking a cut this year will help NSF in the long run as congress should no longer feel it can cut science funding without anyone noticing.

However, the US budget process takes the greater part of a year and we need to put pressure at many points, from the initial proposed budget from the White House to the various committees to the final vote in the fall. Complaining after the fact alone will not help the NSF but instead we need to make the case during each part of the process particularly when the final budget bills get approved starting in September.

When Average Case is the Worst Case

Birthday Boy Rocco Servedio gave a talk at TTI on Friday on learning random functions over random inputs. John Langford asked about distributions that put more weight on simpler string, those of lower Kolmogorov complexity. That reminded me of a nifty 1992 result of Ming Li and Paul Vitányi.

Fix your favorite programming language and let K(x) be the length of the smallest program generating string x. Define μ(x)=2^-K(x), known as the universal distribution for reasons I won't get into here. Notice how strings of smaller complexity get more weight.

Theorem (Li-Vitányi) Any algorithm using time T(n) on average over the universal distribution uses time O(T(n)) in the worst case.

Li and Vitányi prove their theorem by showing that if the set of worst-case inputs is small they will have a short description and thus more heavily weighted under μ. Read all the details in their paper.

Bad Timing

Texas student Vladimir Trifonov gives An O(log n log log n) Space Algorithm for Undirected Connectivity. If it came out a few months earlier (assuming the proof is correct) it would have been an amazing result, greatly improving the previously best known O(log^4/3 n) bound. Unfortunately for Trifonov, Omer Reingold announced his result giving the stronger O(log n) space algorithm a few weeks earlier. Trifonov's work was done independently from Reingold.

Trifonov's proof uses techniques based on PRAM algorithms for connectivity completely different from Reingold's zig-zag methods.

Use Google to Search Your LaTeX Files

In the month of November 44.3% of the hits on this website came from windows machines. If you are in this minority and don't mind a small amount of hacking, read on.

GDS Plus allows Google Desktop Search to search text files. Use this GDSPlus.conf where I've added the "tex" and "bib" extensions and your LaTeX and BibTex files will be indexed and searchable. A great benefit for those of us who can't keep track of which theorems and definitions we put in which papers.

Suggestions to Program Committees

A program committee member who asked me to review a paper pointed me to Oded Goldreich's Suggestions to Program Committees, one of his Essays and Opinions. In his suggestions he gives a reasonable interpretation to the usual ten point scoring system. A few minor quibbles: I would never score a paper a ten (which represents unattainable perfection) nor would I ever resign from a program committee, certainly not over a single paper.

The ends of the scale are not so important; a PC does not distinguish between the excellent papers from the merely great nor does it distinguish between the merely bad and the truly lousy but instead a PC must distinguish the pretty good papers from other pretty good papers.

Later on Oded strongly supports using "ex-submission information" in evaluating proposal even to the point of actively contacting authors for clarification during the review process. While PC members do not live in a vacuum and will be exposed to results they have to later review, actively contacting authors is patently unfair as it favors authors with whom you have a working relationship. Authors who cannot give enough information in the submission for the PC to properly evaluate the work deserve to have their paper rejected.

The State of CISE

While we have seen a increase in computer science funding over the past few decades, it has not kept up with the great increase in the number of researchers in our field making it difficult for many computer scientists to find funding. Peter Freeman, who heads the Computer and Information Science and Engineering (CISE) directorate of the National Science Foundation, co-authored this piece in the current Computing Research News describing has CISE funding has changed over the past decade.

A companion piece written by the CISE division directors describes how CISE is adapting to the large number of proposals. The article emphasizes some reorganization and making connections to other funding centers in and out of the NSF. Until CISE sees a large budget increase, too many computer scientist will remain unfunded or under funded which will hamper CS research in the long term.

Conflicts

Yesterday a program committee member sent one of my submissions to one of my current students to review. Heh Heh. I'll make sure he gives an unbiased positive review.

A good excuse to talk about conflicts of interest. You should not review, edit or referee a paper if one of the authors is

1. a relative and/or someone you are romantically involved with, or
2. a member at your institution.

The second because departments use major conference publications for bragging rights and we have seen some abuse in the past.

The NSF has more stringent restrictions for reviewing proposals. If we used these restrictions for paper reviews, like no close collaborators or no former students/advisor, there might not be any one left to properly evaluate the paper. If the restrictions (1) and (2) don't apply to you, you should state any potential unknown conflicts but feel free to say whether the paper soars like an eagle or gobbles like a complete turkey.

Speaking of turkey–Have a great Thanksgiving everyone!

NSF Budget

Over the weekend the US Congress passed an omnibus spending bill for the fiscal year that started on October 1. The CRA has a roundup of the budget for the National Science Foundation and other funding agencies. Bottom line: NSF down 1.9% overall, with a 0.7% drop for "research and related activities."

It's going to be another tough year for grants.

Letting Go

You just submitted your paper, working hard right up to the final deadline hour. Congratulations! Now what?

Forget about it. Oh you should distribute the paper: make it a technical report; email it to friends and family; put it on your web page and send it to an archive site. But don't keep working on it. All the tension you had getting the paper finished for the deadline needs a release. And no matter how much effort and time you continue to put into it, your paper will never be perfect.

Instead catch up on the todo's you've been ignoring. Say hi to the friends you have deserted while you bunkered down working. Take some time for you: catch a movie; eat a slow meal at a nice restaurant; take a walk.

Afterwards get back to research so you have another paper to write for the next deadline. You know you have successfully put that first paper out of your mind when you get caught off guard from the email from the PC chair letting you know your paper is

• accepted: Great. Now you have to fix the paper up again for the proceedings deadline.
• rejected: No problem. Now you have to fix the paper up again for the next conference deadline.

And it starts anew.

Zig-Zag Connectivity

The Zig-Zag Graph Product (Reingold-Vadhan-Wigderson) gave a new way to create expander graphs, graphs on n vertices with constant degree such that for some ε>0 and every subset of the vertices S with |S|≤n/2, |S∪N(S)|≥(1+ε)|S| where N(S) is the set of neighbors of vertices of S.

The zig-zag expander construction was not as simple as previous constructions nor did it have as good an expansion property. It did have one thing the other constructions lacked: a simple and beautiful proof of expansion.

The zig-zag construction had another property, a compact representation of the expander from the original graph. Reingold used this property to convert an arbitrary undirected graph to an expander in logarithmic space, the basis of his new result giving a log-space algorithm for undirected connectivity.

Why did George Lucas wait so long between the third and fourth Star Wars movies? He wanted the technology of movie making to catch up to his vision for the movie. Computational Complexity can also tell this story. We hit a wall a decade ago in reducing the space needed to solve graph connectivity. We needed a new technology (zig-zag product) and someone (Reingold) realizing they could use this technology to solve the problem.

Google Scholar

Google has just launched a new search engine for academic papers scholar.google.com. Google has received permission from some publishers to allow searching through their papers that would normally not be available for Google to crawl. Based on random checking, it seems ACM for example is allowing Google to see their papers but not Elsevier.