Moons and Planets

When I was in grade school we learned that Jupiter had twelve moons. We had a test. "How many moons does Jupiter have?" I wrote "12" and it was marked correct. In 1974 a thirteenth moon was discovered. The moon didn't just pop into existence in 1974, it was always there (at least when I took my test). Now we know Jupiter has at least 63 moons. The answer of 12 wasn't even close; what I was taught to be a fact was simply not correct.

Now we have ten planets (or is it eight?) circling our sun. Is nothing sacred? What about "My very educated mother just served us nine pies?" What other "facts" from my childhood were incorrect. Are we sure we just have one sun in our solar system?

Maybe that's why I like mathematics and theoretical computer science. Eight plus seven will always be fifteen; nondeterministic space will always be closed under complement. We know what we know; we know what we don't know; sometime what we didn't know we now know but nothing we knew later becomes false.

Two New Blogs

Chris Leonard who edits the Elsevier journals in theoretical computer science has started a weblog Computing Chris. He plans to address some of the concerns of the community to commercial publishers and Elsevier in particular. Feel free to suggest topics to Chris.

Jeff and Suresh point to David Eppstein's new weblog 0xDE. Eppstein always had a number of fun and useful stuff on his website including a catalog of the complexity various games and puzzles.

Relativizing Space

We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a special state q_? and will magically go to a state q_y if x is in A and q_n otherwise.

Scott Aaronson asked me about relativization for space classes noting the difficulty of the above definition. Does the oracle tape count as space? You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage.

Ruzzo, Simon and Tompa developed the best model for oracle relativization. They allow a long oracle tape with the following restrictions:

• The oracle tape is one-way write only.
• A nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape.
• Once the query is made the tape is magically erased.

In this model a log-space machine can ask polynomial-size queries but these queries can be computed in log-space from the input and an extra O(log n) bits (the configuration of the machine right before writing the oracle query).

The Ruzzo-Simon-Tompa definition works well for defining Turing reductions for space-bounded machines but not so much for relativizing theorems, for example showing that alternating polynomial-time equals polynomial space for all oracles. Jonathan Buss gave a model to handle this case but we don't really get limitations on techniques for relativization results on space classes like we do for time. Best not even to bother looking for relativized space class oracles and just think of PSPACE of alternating polynomial-time in results like there is an A such that P^A=PSPACE^A.

The Secrets of Success

What does it take to be a successful in our profession?

• Intelligence. You need an innate talent in different forms to succeed as a scientist.
  • Problem Solving. Using well-established techniques in the appropriate way to find solutions.
  • Creativity. Original research means one needs to look beyond the current set of tools and develop new approaches to problems.
  • Vision. Discovering new problems and directions of research.
• Hard work. Enough said.
• Luck. Working on the right problem at the right time. If you work long enough` the law of averages will catch up with you (for good or for bad).
• Discipline. The discipline to focus on research for a period of time without getting distracted from other responsibilities or by the internet or other activities. Some people find it best to schedule time for research and hole themselves up somewhere to think about a problem.
• Commitment. Be willing to spend a considerable amount of time on a problem even if you keep running into dead ends.
• Training. Taking and working hard in classes. Having and taking advantage of a good advisor. Reading papers and textbooks. When you see a theorem in a paper try to prove it yourself first. Only then can you truly appreciate a proof and learn from it.
• Colleagues. Having co-authors, especially those that complement your talents, can help you do more than you could on your own. But just having good people to talk to, to bounce off proof ideas and discuss research directions can greatly help you find the right approach to a problem.

Powerful, Aware and Evil

The Americans develop a powerful computer to run its nuclear weapons. The Soviets develop a similar machine. The two are connected and take over the world with threats of nuclear annihilation. So goes the story of Colossus: The Forbin Project, one of the scariest movies of my childhood.

Build a powerful computer, it becomes self-aware and turns evil. We've seen this theme in many movies including 2001: A Space Odyssey, War Games and Terminator 3. Computer scientists as Frankensteins, building monsters they cannot control.

In 1982, Disney put together a TV special that tried to argue against the computers as monster theme. They could have used a better title than "Computers are People, Too!" and avoided pushing their new movie Tron about an evil computer.

Colossus did scare me as a kid but when I grew up I realized computers, as powerful as they get, don't become self-aware or inherently evil and they can always be rebooted or unplugged. Bad people can use computers in evil ways but computers themselves are just tools not the perpetrators.

I bring this up because of the new movie Stealth opening today in the States about a plane controlled by a computer that becomes self-aware and starts destroying stuff. Scaring a new generation about the evils of computer science.

Majority is Stablest

Consider the following two voting schemes to elect a single candidate.

1. Majority Vote.
2. A Majority of Majorities (think an electoral college system with states of equal size).

Which of these voting systems are more stable, i.e., less likely to be affected by flipping a small number of votes?

In an upcoming FOCS paper, Elchanan Mossel, Ryan O'Donnell and Krzysztof Oleszkiewicz prove the "Majority is Stablest" conjecture that answers the above question and in fact shows that majority is the most stable function among balanced Boolean functions where each input has low influence. To understand this result we'll need to define the terms in the statement of the theorem.

• Balanced: A Boolean function is balanced if it has the same number of inputs mapping to zero as mapping to one.
• The influence of the ith variable is the expectation over a random input of the variance of setting the ith bit of the input randomly. The conjecture requires the influence of each variable to be bounded by a small constant.
• Stability: The noise stability of f is the expectation of f(x)f(y) where x and y are chosen independently.

The majority is stablest conjecture has applications for approximation via the unique games conjecture.

Understanding Proofs

When do you understand a proof? Such understanding has many levels.

• Knowing the rough techniques used.
• Following the proof line by line.
• Can recreate the proof.
• Can explain the proof to others.
• If someone else claims a mistake in the proof, you can show them why they are wrong.
• Applying the proof techniques to other theorems.

For me for example, Toda's theorem I fully understand; the PCP theorem I sort of understand (though hopefully I'll understand it better after I teach Dinur's proof in the fall) and the parallel repetition theorem I will never understand in its current form.

Why do we understand proofs?

• Part of the job, as a referee, reviewer or advisor.
• We care about the theorem, because it is important and/or something we've worked on.
• We've heard the proof is nice and short and worth reading.
• We want to apply the proof techniques to other problems.

Unfortunately I suspect most proofs are read with the last goal in mind. A nice proof is a work of art, something to be savored, not something to be milked.

What Kind of Science is Computer Science?

In 1981, Juris Hartmanis wrote some observations on the early days of computational complexity. The article also contains some interesting discussions on issues like how CS fits in with the other sciences.

I see computer science as a brand new species among other sciences, and I believe that it differs fundamentally from the older sciences. As a matter of fact, I am convinced that in large parts of computer science the classic research paradigms from physical sciences or mathematics do not apply and that we have to develop and understand the new paradigms for computer science research. The fundamental difference between, say, physics and computer science is that in physics, we study to a very large extent a world that exists, and our main objective is to observe and explain the existing (and predict new observable) phenomena. The relations between experiments and theory are quite well understood and richly illustrated by successful examples. Computer science, on the other hand, is primarily interested in what can exist and how to describe and analyze the possible in information processing. It is a science that has to conceptualize and create the intellectual tools and theories to help us imagine, analyze, and build the feasibly possible.

Computer science is indeed a different intellectual discipline than we have ever encountered before. It shows some haunting similarities with physical sciences and mathematics (whose basic research paradigms and goals are quite different), but it differs from both of these disciplines in some very fundamental ways. As a matter of fact, quite often the paradigms, borrowed from physical sciences and mathematics, have been incorrectly applied to computer science research with predictably frustrating results. Similarly, the attempt to view computer science as an engineering discipline does not properly capture its essence. There is a substantial engineering component in computer science (or its applications), particularly in building computing machines and managing large software projects, but its core activities do not fit the traditional engineering paradigms.

In view of these observations, I believe that one of the very important tasks for the computer science community is to understand better the nature of computer science and develop the new research norms, paradigms, and methodology without which it will not mature into an independent and influential science. In particular, the relations between theoretical and experimental computer science must be clarified and new interactions must be forged. This is not just a matter of producing "more practical theories" and applications of theory, which we certainly need. It is the hard and challenging task of determining for a new science how theory, experiments, and practice should interact. Furthermore, this is not just an esoteric exercise in the philosophy of science; whether we admit it or not, our underlying beliefs, our conception of our field of study, and our perception of what is possible all fundamentally influence what kind of science we are going to build.

Complexity versus Computability

To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability (Recursion) Theory started in the 1930's with the work of Turing, Church, Gödel and Kleene and complexity theory gathered steam in the 60's. Complexity theory derives many of its definitions from computability theory such as Turing machines, reducibility, completeness and lowness and the polynomial-time hierarchy is an analogue of the arithmetic hierarchy. Several complexity theorists originally received their Ph.D. in computability theory.

One can say computational complexity is just computability theory with resource bounds but the fields feel quite different.

• Complexity theorists consider themselves part of the theoretical computer science community and find themselves mostly in CS departments. Recursion theorists consider themselves logicians and find themselves mostly in math departments.
• Complexity theorists try to understand efficient computation analogous to theoretical physicists trying to understand how the universe works, where computability theorists consider more ethereal questions of logical definability. Consider the example of quantum computing: Many complexity theorists analyze the computational power of these machines where quantum has had virtually no effect on computability theory.
• Outside of diagonalization, the tools and techniques used in the fields are completely different. Rare does one see a priority or finite injury argument in complexity, whereas algebra and combinatorics don't appear in most computability proofs.

The University of Chicago has had for many years a strong presence in computability theory led by Bob Soare who wrote a major textbook in the area. I sat in Soare's class in the hope some of the techniques in computability would help my research in complexity (for the most part they haven't) and have gone to a few logic seminars. Everything I do they call "zero."

The difference in thinking hit me during a logic seminar where the speaker asked "How do we usually show that a language is computable?" I thought find an algorithm. The speaker answered his own question "Show that the language is c.e. and co-c.e."

Magic is in the Eye of the Beholder

I just finished the latest Harry Potter book. Amazing how much you can read when stuck at an airport. It seemed like half the people at the Seattle airport on Monday were reading that book.

No spoilers in this weblog. Let's just say the wizarding community has seen better days.

Ever notice that except for a few new potions and spells, technology has not changed much in the wizard world. If Hermione could only google "half-blood prince" she wouldn't have to spend so much time in the library. Email beats owls any day. Wouldn't it be nice for them to have some music in their lives, an iPod or at least a radio?

This is what happens in a culture where they don't teach their young science and math and no one seems to go to college.

Winnie the Mathematician and a Few Comments on Comments

Today's Science Times has an article on Danica McKellar an mathematically-talented actress, best known for her role as Winnie on Wonder Years. She has a Bacon number of two and an Erdös number of four, the first completely legit example I know of someone with finite Bacon and Erdös numbers.

An administrative issue on comments. Because I apparently violated a security policy on our department computers, you can no longer post new comments on the old commenting system, that is on posts before May 9, 2004 as well as the General Comments link. You still can read the old comments and post comments on posts since May 9, 2004.

And while I'm on the topic of comments and because some have asked, I have never and never will post a comment anonymously on this weblog. I encourage everyone to sign their comments (what do you have to hide) or at least use an alias so we can match comments to the same writer. Still I'd rather you leave comments anonymously than not leave them at all.

I've also been asked about deleting comments. I reserve the right to delete any comment but so far have done so only in the following cases:

1. Duplicate comments.
2. Comment spam.
3. Once because the author of the comment requested it to be deleted.
4. Once because the comment was too long. The comment started with something like "I wrote a book on the topic and here is the first chapter…" If you have something long to say put it somewhere else on the web and put a link in the comments.

Computer Science Has Been Very Very Good To Me

Ever notice how computer science departments in the US are like baseball teams. They try to hire the best players so they can be better than other departments (try to be in the "top ten" for instance). Already strong departments with lots of resources continue to hire the best people and become even stronger. MIT, despite being close to Boston, is like the New York Yankees of computer science.

One can push an analogy too far and I've already crossed that line but let's keep going.

• Baseball players are initially tied to a certain team though after a certain number of years they can become a free agent or prevent their team from trading them. Professors can become free agents after any year and after seven years, if they are still with the department, get a no-fire clause.
• Baseball teams have minor leagues to train young players. We have graduate students.
• Baseball has had a strong commissioner who mediates disputes and can make changes for the good of the game. We could use someone like that.
• Baseball sells naming rights of its stadiums. Universities sell naming rights of their buildings.
• Baseball has a hall of fame honoring the very best. We have the Turing award. But like baseball we could also have a physical location with memorabilia like the original draft of Cook's paper or the chalk Manindra Agrawal used to prove Primes in P with his students.
• Baseball teams trade players. Imagine David Karger and Madhu Sudan for Umesh Vazirani, Luca Trevisan and a grad student to be named later.

Do Only Simple Theorems Have Simple Proofs?

My technical posts rarely draw many comments but Tuesday's post on Savitch's Theorem brought a long discussion on hard versus easy proofs that started with this comment.

This is a good example of how STOC/FOCS have grown significantly in quality over the years. Savitch's theorem was in STOC 1969, and the proof is trivial.

The proof of Savitch's theorem is easy (trivial is a little strong) but the result was surprising at the time and has had a profound impact on complexity since. I'd love to see STOC and FOCS have results this easy and this important.

I had mentioned before that an easy proof can hurt your chances of acceptance at a conference. Let's take a look at the viewpoint of the program committee.

If you have a previously established hard theorem, one that many people have worked on but no proofs or only complicated proofs have been found, then short proofs are valued. Dinur's proof of the PCP theorem fits in this category. A simple proof of the parallel repetition theorem or the unique games conjecture would also be welcome in STOC or FOCS.

But most papers at STOC and FOCS do not solve previously established hard theorems. They extend previous work, improve bounds or make partial progress towards the major open questions. The program committee has to decide whether the result represents real progress or it just easily follows from previous work. An easy proof gives an indication of the latter.

Unfortunately this gives an incentive for the authors to make their proofs look difficult in their papers. A quick way for a PC member to kill a paper is to show an easy proof but the committee doesn't have the time to try and find easy proofs for all the submissions.

MC Plus +

Guest post from theory music expert Bill Gasarch.

There is some (not a lot) of novelty songs about computer science, and less about theory.

There is a new CD (with mp3 downloads) of computer science songs in Gangsta Rap style.

One of the song is about Alice and Bob transmitting messages, so that would qualify as theory.

The CD is more interesting than funny.

Warning: Not suitable for children.

Favorite Theorems: P = NP for Space

June Edition

In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic space with only a quadratic slowdown.

Walter Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities, Journal of Computer and System Sciences, 1970.

In complexity terms, for any space constructible function s(n) ≥ log n,

NSPACE(s(n))⊆DSPACE(s²(n))

You can find the proof in an earlier post.

As a consequence you get PSPACE=NPSPACE, which is why you don't see NPSPACE in the zoo.

Chandra, Kozen and Stockmeyer used a modification of the Savitch algorithm to show that polynomial space can be simulated in alternating polynomial time. This relationship led to showing lots of games PSPACE-complete and played a critical role in showing IP=PSPACE.

Circuit wise, Savitch's algorithm puts NL (nondeterministic log-space) in SAC¹ (log-depth circuits with constant fan-in ANDs and unbounded fan-in ORs).

For a directed graph G=(V,E), let G^k=(V,E^k) where (u,v)∈E^k if there is a path of length at most k from u to v in G. One way to view Savitch's theorem is to compute G^2k from G^k using O(log n) additional space. You then apply this graph powering log n times to get from G=G¹ to Gⁿ where (u,v)∈Eⁿ if there is a path from u to v in G.

Reingold uses a similar paradigm in his result that SL = L. He shows for undirected graphs that you can do a weaker form of graph powering (using expander graphs) but with a similar effect using only O(1) additional space at each step.

But after 35 years we still have no better upper bound on the deterministic space complexity of NL than O(log² n) from Savitch's Theorem.

The Organized Scientist

Some professors consider it a badge of honor to keep huge stacks of papers covering their desk and often most of their floor. But in reality once you bury a paper in other papers you won't ever deal with it or find it again when you need it. We are really no different than any other professional and just a few simple techniques can greatly unclutter your life.

For every piece of paper that enters your life you should do one of three things:

1. Trash (or recycle) it.
2. File it away, and it its an action item put it on your To Do list.
3. Deal with it right away and then do one of the above.

Do not just drop it on your desk for future action. It will get covered by another piece of paper and you might as well have recycled it.

If it is a form that needs to be filled out than do so. If it is something you don't have time for now (like a referee report) than keep those in a special place in your desk and add it to a To Do list.

The above rules apply to email as well.

For a To Do list, I use the Tasks page on Yahoo Calendar which I can access from any computer (and it's free). I use the "Due Date" field as a start date so I can sort tasks by when I want to do them.

If you print a paper from the web to read and you think you might need it again in a week or so what should you do? Recycle it and print it again when needed. Don't tell me I'm wasting paper. You'll just print it again when you can't find it anyway. As a general rule you should never save anything you can find on the internet.

How to get started? Go through all of your papers in your office applying the rules above. Too much effort. Then recycle everything. You weren't going to deal with them anyway and now you'll have a clean office and be ready to stay organized.

Computer Science in High School

When I went to high school (1978-81) we had a computer room with three teletype machines that connected at 10 characters/second and we saved programs on paper tape. We also had a math teacher, Mr. Jaeger, who taught us not only how to program those computers but also used them to teach concepts like probability. We would run simulated card shuffling algorithms to test our calculations of the probabilities of poker hands.

A recent AP article says that computer science courses in high schools are getting less interest from students as well as from the states setting curriculum. This decline in interest at high school leads to the decline in CS majors we see throughout the American universities. A similar phenomenon is going on in many other countries as well.

The usual reason given is the perception of a weak job market in computers. But I think there is another issue. In my high school days, outside of a few games you couldn't do much with a computer unless you programmed. Today computers have become almost as commonplace as televisions and teens use them for a variety of tasks, including researching on the web, communication via email, instant messaging and blogging, and writing papers, all without an inkling of how to program. Computers have become a commodity and they don't see an additional value in knowing how and why they work any more than they need to know physics to drive their cars.

One of the great challenges of computer science was to make computers important and useful in everyday life. We are now becoming victims of our success.

Matrix Rigidity

Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices.

The rigidity of a matrix M is a function R_M(r) equal to the minimum number of entries of M that you need to change in order to reduce the rank to r. Strong rigidity bounds would have applications for circuit and communication complexity.

Let N=2ⁿ. We define the N×N Sylvester S by labeling the rows and columns by n-bit vectors and let s_i,j=(-1)^i·j.

Theorem: If r ≤ N/2 is a power of 2 then R_S(r) ≥ N²/4r.

Proof: Divide S uniformly into (N/2r)² submatrices of size 2r×2r. One can easily verify these submatrices each have full rank. So we need to change at least r elements of each submatrix to reduce each of their ranks to r, a necessary condition to reducing the rank of S to r. QED

This proof works for any matrix whose submatrices have full rank. Consider the N×N matrix B where b_i,j=1 if i ≡ j (mod 2r) and 0 otherwise. By the same proof R_B(r)=N²/4r even though the rank of B is only 2r.

The moral of this story: We conjecture that the Sylvester matrices have very high rigidity but we still lack the tools that make full use of the structure of these matrices.

Different Views of Consciousness

The great game theorist Robert Aumann writes about consciousness.

Sometimes, people express perplexity as to the nature of the problem. They do not see anything mysterious about consciousness, and do not understand in what way it is different from other neurological functions like, say, the regulation of breathing. Asked whether a computer could in principle be conscious, they answer, "why not?"

We are dumbfounded by this reaction, and can only conjecture that these people are themselves not conscious. To me, it is evident that no combination of silicon chips and wires could conceivably "experience" in the sense that I do. Consciousness involves something beyond the merely physical and mechanical.

A bit of a different view than that of Manuel Blum.

The question whether an entity is CONSCS is a function of its algorithms, not the stuff (silicon or carbon) that implements those algorithms.

Why are great scientists like Blum and Aumann taking on consciousness late in their careers? One of the many possible research questions Blum threw out in his talk:

What happens when an entity stops being an entity?

So perhaps they study consciousness as a way to deal with their own mortality.

Independence Day in America

Old Joke: Is there a fourth of July in Canada? Sure there is, right between the third of July and the fifth of July.

Outside of the US the Fourth has no special meaning so non-Americans have no qualms running conferences and workshop over our holiday. This will be my first time in three years spending the entire Independence Day in the US. Last year I was in Banff and in 2003 on a plane to Denmark. (I may not collect much sympathy here.)

How will I celebrate America's 229^th Birthday? A parade in the morning, a friend's house for barbecue and capping the night with fireworks. Should be a perfect Fourth.