- 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.

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

## Sunday, July 31, 2005

### The Secrets of Success

## Friday, July 29, 2005

### Powerful, Aware and Evil

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.

## Wednesday, July 27, 2005

### Majority is Stablest

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

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
*i*th variable is the expectation over a random input of the variance of setting the*i*th 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.

## Tuesday, July 26, 2005

### Understanding Proofs

- 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.

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.

## Monday, July 25, 2005

### What Kind of Science is Computer Science?

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.

## Friday, July 22, 2005

### Complexity versus Computability

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 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."

## Thursday, July 21, 2005

### Magic is in the Eye of the Beholder

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.

## Tuesday, July 19, 2005

### Winnie the Mathematician and a Few Comments on Comments

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:

- Duplicate comments.
- Comment spam.
- Once because the author of the comment requested it to be deleted.
- 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.

## Monday, July 18, 2005

### Computer Science Has Been Very Very Good To Me

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.

## Friday, July 15, 2005

### Do Only Simple Theorems Have Simple Proofs?

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.

## Thursday, July 14, 2005

### 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.

## Tuesday, July 12, 2005

### Favorite Theorems: P = NP for Space

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.

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

^{2}(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^{1} (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^{1} to G^{n} where (u,v)∈E^{n}
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^{2} n) from
Savitch's Theorem.

## Sunday, July 10, 2005

### The Organized Scientist

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

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

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.

## Thursday, July 07, 2005

### Computer Science in High School

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.

## Wednesday, July 06, 2005

### Matrix Rigidity

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^{n}. 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^{2}/4r.

**Proof:** Divide S uniformly into (N/2r)^{2} 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^{2}/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.

## Tuesday, July 05, 2005

### Different Views of 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?"A bit of a different view than that of Manuel Blum.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.

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.

## Sunday, July 03, 2005

### Independence Day in America

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.