On March 14, 2008

The Big Red Dance (updated)
from Lance Fortnow at 16:13 PM GMT
Every year about this time, Americans come together and argue and wage large amounts of money on the outcome of a simple binary tree known as officially as the NCAA Division I Men's Basketball Championship. 65 teams play 6 rounds (two teams play 7 rounds) over three weeks in a single elimination to move up the tree.

The participants and the tree itself get unveiled Sunday but the fate of two teams that matter to me have already been decided. For the first time since I was a graduate student my undergraduate Alma Mater, Cornell University, will be in the tournament after going undefeated in the Ivy league. Meanwhile my new school, Northwestern, will be staying home after having won just one game in the Big Ten and having their last slim chance extinguished last night losing to Minnesota in the Big Ten tournament.

In 1988, the last time Cornell went to the tourney, their game against Arizona was televised on tape delay at about 3 AM. I taped the game on my VCR and watched it next morning before I found out what happened. Rooting for a team on a game whose outcome has already been determined feels a bit weird, sort of like waiting to open the box to see if Schrödinger's cat is alive or dead. Still I got emotional at the highs and lows of the game, although there were not too many highs as Arizona beat Cornell 90-50.

Flash forward two decades and now all the games will be streamed live over the Internet for free. But I'll be in Israel, the game will likely be on some ridiculous hour over there and I probably won't have computer access anyway even if they allow streaming internationally. So go Big Red, win your first four games without my live or even taped of a tape delay support, so I can watch you on final four weekend. But I wouldn't bet on it.

Biweekly links for 03/14/2008
from Michael Nielsen at 10:53 AM GMT

Click here for all of my del.icio.us bookmarks.

On March 13, 2008

Investing in undervalued human capital: the Y Combinator model
from Michael Nielsen at 21:15 PM GMT

Y Combinator (YC) is a small Cambridge-based firm that for the past few years has been carrying out a remarkable experiment. What they’ve been doing is investing money and training in (mostly) young hackers, helping them get technology companies up and running to the point where more more conventional investment processes like venture capital can kick in. Many YC funded companies have been successful, with several making their founders wealthy at an early age.

At first glance, YC may appear only of interest to business or technology people. In fact, there are broader things one may learn from the model, with applications and importance outside business and technology.

If you’re not familiar with how YC works, it goes something like this. Twice a year, YC calls for applications to be submitted, either for its Winter or its Summer programs. Applications are submitted by small teams of people (”founders”), typically in their twenties, who would like to start or have recently started a technology company. YC evaluates the applications, and the best are asked to join the YC program. Successful applicants typically receive $5k + $5k per founder to support them for three months, and are required to move to Boston (for the Summer program), or the San Francisco Bay Area (for the Winter program). All the YC teams meet together once or twice a week, to talk with each other and with the YC partners, as well as with a changing cast of expert entrepeneurs specially brought in from outside. The three month program concludes with “Demo Day”, where the founders demonstrate what they’ve built to a large group of angel investors and venture capitalists, in the hopes of sparking further interest. In return for this program, the founders give up a small percentage of their company, typically between 2 and 10 percent.

What makes the YC program successful is that YC have identified a large group of people whose talents were previously undervalued and underutilized, in large part because of their age and lack of experience. For more than thirty years, high-school geeks have played with technology, gone off to university, where they continue to play with technology, often doing astounding and innovative things, but rarely having the entrepeneurial skills or connections to turn their ideas into marketable products. At the end of it all, they go off to work for a big established technology company like Microsoft.

YC has asked a big “what if?” question: what if we gave these talented people an opportunity to build their own company, from the ground up, and gave them training in entrepeneurial skills they lack, complementary to their existing technical ability? Might it be that if we provide this training (which is relatively easy to do), then these people will create more value than if they were off working for big existing technology companies?

It is evident from the above description that this process can be abstracted away to a core unrelated to technology:

  • Identify a talented group of people who are at present undervalued, i.e., not being given an opportunity to contribute commensurate with their talents.
  • Set up a competitive program whereby people in your target group can apply for support.
  • Select the best applicants for support.
  • Help educate successful applicants, trading off the costs of the education against the value that comes from their increased probability of success.
  • Make sure you market yourself to the desired group of people, so you get the best possible pool of candidates (e.g., here and here).

What’s special about YC is the group they’ve identified: young hackers, whose lack of experience means they often have a hard time being considered seriously by existing investors such as venture capitalists. Ironically, this is in part because the venture fund model typically involves investments that are, at a minimum, hundreds of thousands of dollars. Given a choice between investing that money in a 35-year old Harvard MBA’s startup, and a team of three unshaven 21 year-old hackers, most venture partners will go for the Harvard MBA. Part of YC’s insight is that in 2008 many technology companies can be launched for just a few tens of thousands of dollars, far less than the venture funds provide.

Other organizations have adopted an analogous strategy to YC, but for a different group of otherwise undervalued people. A good example is microfinance organizations like the Grameen Bank, which provide small loans to assist entrepeneurs in the developing world. The success of the Grameen Bank indicates that investors previously underestimated the talents of the lendees to build successful businesses. An interesting social consequence common to YC and the Grameen Bank is that both empower people who are otherwise somewhat disenfranchised. (Obviously, the effect is far greater in the case of the Grameen Bank.)

This process of identifiying a talented group of people who are undervalued by the investment market is a curious one. An uncritical advocate of the free market might counter that such people shouldn’t exist - surely investors would have already tracked them down, and offered to invest. In fact, YC is a clear case where (up to now) the market has failed badly, due to the blinkered narrowness of investors. Is it more risky to offer one million dollars to finance a Harvard MBA in their new technology venture, or to fund twenty groups of talented twenty-one year old hackers, at a cost of about $50k each (including the training costs and other overheads)? My money would be on the twenty-one year olds to make a greater aggregate return, but I suspect most investors would feel much safer going with the Harvard MBA - even if they fail, it’s a lot easier to defend your choice to your peers.

What other undervalued sources of human capital might this general model be applied to? When I started to think about this question, I quickly came up with dozens of possible groups. Here’s the first few that came to mind:

  • Talented people who happen to have been born in the wrong place for their talents to flourish. The top students at (for example) the big IITs in India are incredibly talented. While India offers increasing opportunities for technology entrepeneurs, imagine the results of bringing some of the more entrepeneurial students to Silicon Valley, and helping them get set up with technology companies. Think YC with a visa program.
  • The elderly. As a society, we cut many extremely talented and active people off from contributing society, at great cost to them, and to society as a whole. It’d be great to find ways their talents could be made better use of.
  • Bright PhD students in insanely competitive and challenging academic subjects, where even extraordinary students may have trouble getting good academic jobs, and where those same students may lack the connections to find jobs outside academia that make good use of their talents.
  • My current hometown of Waterloo, Canada, is a pretty good setting for a YC style program. It has a growing startup culture, and two universities (University of Waterloo and Wilfred Laurier University) with, respectively, strong technology and business programs. As a rough indicator of student quality, in programming and mathematics competitions, University of Waterloo students are routinely competitive with the best from MIT and other top US Universities. At present, many of these students go to work for large technology companies elsewhere - the University of Waterloo is sometimes said to be Microsoft’s single largest recruiting target. Something like YC would, I think, be highly successful here, although it would need to compensate for a relative paucity of local investors.
The curse of busy-ness
from Michael Nielsen at 17:14 PM GMT

Why do powerful, intelligent, and accomplished people so often exhibit cluelessness or ignorance? (Examples can be supplied on demand, in the unlikely event you need them.)

I don’t mean to rip on powerful people, many of whom become powerful because of outstanding personal traits. But I do think it’s worth understanding the puzzle of why so many people do great things in their youth, and then do apparently sillier things as they get older.

I think my post about the bias towards power contains a partial explanation: powerful people’s ideas often aren’t tested as rigorously as those of the less powerful, and they find it easier to act while ignoring good advice. As an example, a regular Joe with an idea for starting a company has to convince other people of the idea in order to attract investment. A wealthy entrepeneur finds it much easier to get silly ideas funded, in part by investing their own wealth, and in part because other people give undue weight to their words.

(This is also why comics and superheros like Spiderman are interesting: they show what happens when basically well-intentioned people can act without constraint. The results often aren’t pretty.)

However, I think the bias towards power is only part of an explanation. Another part is that powerful people are often far too busy and focused. If you don’t create time just to fool around (”purposeless delectation in ideas” was Gian-Carlo Rota’s lovely phrase), you end up narrow, clueless, and irrelevant. It’s funny to hear that CNN’s Larry King has never used the net, or that George Bush (the elder) was amazed by supermarket barcode scanners in 1992, but, really, these people must have some massive blind spots.

Abuse of Tagging System on amazon (updated)
from Lance Fortnow at 15:51 PM GMT
Amazon has a feature where a reader can associate a word (called a tag) to a book, really user-defined keywords. However, this can be abused. Consider the following book:
Theoretical Aspects of Local Search
  1. fraud (131)
  2. lies (119)
  3. fantasy (103)
  4. mythology (94)
  5. morons (69)
  6. illogical (68)
  7. unintelligent (68)
  8. irony (65)
My my! Is the book really that bad? I recently had it reviewed for my SIGACT NEWS column and it seems like a fine book. Someone is abusing the tag system. But it gets worse. Look at the following book on a similar topic.
Local Search in Combinatorial Optimization
  1. fraud (131)
  2. lies (119)
  3. breathtaking inanity (111)
  4. fantasy (103)
  5. junk science (71)
  6. problem solving techniques (1)

What are the odds that exactly 131 people think that both of these books are frauds? that 119 people think both books are full of lies? that 103 people think that both are fantasy? I have it on good authority that these books are not bad. They may be too theoretical for someone's tastes, but thats no reason to trash them 131 times. So what is going on here? My guess: someone or some group does not like the area and has a program that tags things automatically.

This also happens in the humanities, which is perhaps less surprising since its more subjective.
The Columbia Anthology of British Poetry
  1. anthologies (1)
  2. avoid at all costs (1)
  3. crazy (1)
  4. cult (1)
  5. evil (1)
  6. fraud (1)
  7. insane (1)
  8. junk science (1)
  9. poetry collection (1)
  10. snake oil (1)
  11. vocational (1)
  12. discenment (1)
One big difference- people in the humanities have not learned how to write programs that will tag something multiple times.

On March 12, 2008

The Long Slog (updated)
from Lance Fortnow at 13:16 PM GMT
Mid-March is the time of year we begin to hear concern from students and postdocs on the job market. The CS job market is a lengthy affair running from January to June and beyond. But still if one has had few or no interviews scheduled yet, one cannot help but worry whether the situation will improve.

Some Advice:

  • Don't Panic. Universities start with their very top candidates, often the very same people for each school. It is only after these candidates start deciding that schools will start bringing in other applicants. Also many CS departments first try to hire in applied areas and failing that will only then start to consider theory candidates. So sit tight, there is still a long way to go in this market.
  • Expand your opportunities. Consider some schools you may not have thought of before. There are many possibilities overseas as well, especially for postdocs. The Internet is the great equalizer, allowing one to do strong research from just about anywhere.
  • Consider another postdoc. It is becoming more common in our field to take a second or third postdoc and is no longer frowned upon when you reapply for permanent jobs.
  • Keep busy. Keep your mind off the job hunt. Do some more research. Work hard on your thesis or journal versions of your papers. Take a vacation. Don't just sit at your computer checking your email every 15 seconds.
  • Make some money. The hard truth is that there are not enough good academic jobs for all of the qualified applicants. But CS PhD's don't drive cabs. So join an Internet company or a hedge fund and go have a happy well-funded life.

On March 11, 2008

Creative collaboration: ideals and reality
from Michael Nielsen at 18:21 PM GMT

I’ve been reading Keith Sawyer’s book “Group Genius: The Creative Power of Collaboration”, and thinking about what makes some collaborations work, and others fail.

In this post I describe two principles governing group collaboration. Both principles are obvious and self-evident. Unfortunately, and this is the point of the post, they’re often systematically disobeyed in scientific collaborations, and this may prevent such collaborations from achieving what Sawyer calls “group flow”, a state in which groups collaborate effectively, producing creative works beyond any of the individual members of the group.

Principle: Collaboration should recognize individual effort appropriately

In a jazz performance, it is for the most part transparent who is contributing what to the performance. If someone is slacking off, or trying to hog the limelight, this becomes obvious to the audience.

Science is much less transparent. There are no generally agreed upon norms governing how people are given credit in a paper, and as a result individuals in a group may not feel secure that their role will be properly acknolwedged. To be sure, in some fields there are rules of thumb - for example, in many experimental papers, the principal investigator who runs the lab in which the experiments were performed is often listed as the last author on the paper. But this is a long way short of a full and fair accounting of who contributed what.

This lack of transparency causes all sorts of problems. A common example is the “author” who was in the room when some critical breakthrough happened, but who actually contributed little, and lacks the grace to refuse authorship. Another common example is the author who contributes just enough to deserve authorship, and then goes on their merry way, leaving the bulk of the work to be done by others. Many multi-author papers are primarily the work of a single individual, yet that individual may not be distinguished at all in a long list of 5-10 (or even more) authors.

Some scientific journals, such as Nature, are beginning to address this problem, experimenting with systems whereby each author on a paper is asked to detail what they contributed to the paper. It will be interesting to see whether this creates more incentive for people to contribute in a full and fair fashion to papers on which they are authors.

Principle: collaboration should involve people with complementary skills

This is so obvious that it would seem to fall into the “well, duh!” category. In fact, institutions often systematically violate this principle on such a large scale that it becomes an accepted and almost invisible part of the institutional culture.

Exhibit A is Australian science. I’m picking on Australian science here because I know it well - similar remarks hold true in many other countries. A peculiar feature of the funding system for nearly all Australian Universities is that departments are financially rewarded for keeping their own students within a department. As a result, it’s not uncommon to go into a large research group, and discover (say) 5 PhD students, virtual academic clones of one another, having graduated from the same academic department, often within a year or two of each other, and often with essentially the same list of undergraduate courses. Not a good recipe for reaping the benefits of complementary expertise! The contrast with top American research departments is striking, with students even within a given research group often having quite heterogeneous backgrounds.

Exhibit B is the disciplinary structure of science itself. Most disciplines and subdisciplines have a canon of material, which experts are expected to understand. Unfortunately, in most fields learning the canon requires an enormous amount of time, which leaves little room for learning more individualized skills. It’s interesting to recall that the physicist Richard Feynman famously claimed not to understand either group theory or the standard integration techniques from complex analysis, two skills that are certainly canonical for particle physicists. Perhaps he spent his time learning a more individualized set of skills that made him better able to contribute in a unique way to the collaborative enterprise of science.

Why is PARITY not in AC_0 important? (updated)
from Lance Fortnow at 15:55 PM GMT
When discussing what should we teach in a basic complexity course (taken mostly by non-theorists) we often say results such-and-such is important. The question then arises- why is it important? Can the reasons be conveyed to a non-theory audience? Lets look at PARITY CANNOT BE COMPUTED BY POLYTIME, AND-OR-NOT, UNBOUNDED FANIN, CONSTANT DEPTH CIRCUITS (henceforth PARITY ∉ AC0).

Why is PARITY ∉ AC0 interesting? important? (For a good source on this result and other lower bounds on simple models see boppana_sipser.pdf boppana_sipser.ps, a survey from 1989 which is, sadly, not that dated.) I do find the result interesting, but none of the reasons below seem that satisfying to a non-theorist.
  1. PARITY ∉ AC0 is the way to obtain an oracle that separates PSPACE from PH. (An oracle to make them collapse is easy.) Hence no proof that relativizes can be used to seperate PSPACE from PH (this is not a rigorous concept, but people in the area have a sense of what it means). To motivate this you need to do some proofs that relativize. How many? Perhaps I am biased here- I had a course in computability theory covering 2/3's of Soare's book (I understood 1/2 of it at the time) before studying complexity theory, so I really knew what relativizing technique meant when I looked at oracles. That level of understanding is not needed, but some is. Even so, seems hard to get across to non-theorists in a course.
  2. PARITY ∉ AC0 is a natural problem on a natural model with a natural proof, and hence is interesting. This raises the question: do some people in the real real world really want to construct polysize constant depth unbounded fanin AND-OR-NOT circuits for PARITY, and does this result tell them why they cannot? Are there other lower bounds that are corollaries of PARITY ∉ AC0 that give lower bounds on problems people really want to solve? I ask this non-rhetorically.
  3. One approach to P vs NP is to start with simple models of computation that one can prove lower bounds in, and then scale up. There was more optimism for this approach back in 1989 then there is now.
  4. The techniques used to prove the result are interesting (YES- there are several proofs, all interesting) and useful for other theorems of interest (circular reasoning?).
A more general issue: when are results interesting in their own right, and when are they meant to be part of a larger research program? We may not know until many years later.

And of course, for course content, the question is important? compared to what?
New blogs
from Michael Nielsen at 01:33 AM GMT

Sean Caroll and Chad Orzel both have posts up asking readers to suggest new blogs in comments.

Let me ask the same, but with an added twist: what are your favourite specialty blogs? What do you think is a really great and insightful read, but maybe in some unusual area? Know of a great blog on knitting (or Lego, or kite-flying, or marathoning, or publishing, or whatever)? Please leave it in the comments.

One thing I really enjoy about blogs is that I get to read stuff from experts on pretty much any subject. I love reading about economics (e.g., John Quiggin, Brad DeLong and Greg Mankiw), marketing (e.g., Seth Godin, HorsePigCow), writing (Confident Writing), libraries (John Dupuis, Science Library Pad, Google Librarian blog), machine learning (Machine Learning), and lots and lots of other subjects. Pretty much every subject in the world can be fascinating, providing you’re talking to the right person!

Deference, defiance, and power
from Michael Nielsen at 00:41 AM GMT

Robin Hanson has some thoughts related to my recent post about the consequences of the bias towards power:

People relate to power two ways, via deference and defiance. When we defer to power, we are indeed biased to give it too much inferential weight, but when we defy power, we give it too little inferential weight. We listen too much to the powers that we feel allied with, and too little to powers we feel allied against. To think more objectively, become less allied.

Robin’s comments implicitly highlight the fact that we may be for or against power, but we rarely ignore it. Of course, being ignored is all-too-often the fate of ideas, even very good ideas, expressed by the less powerful.

On March 10, 2008

Adventures in phase space
from Michael Nielsen at 23:50 PM GMT

Aggie Branczyk has an awesome video illustrating some ideas from quantum optics. You’ll need to know what a Wigner function is to fully get this, otherwise you can just admire the pretty animation:

The Video King (updated)
from Lance Fortnow at 14:54 PM GMT
I recently watched a surprisingly good documentary The King of Kong: A Fistful of Quarters where Steve Wiebe tries to break the Donkey Kong record held for many years by the popular Billy Mitchell. These battles take place at video arcades across America as well as Wiebe's garage in Redmond, Washington. A neat back and forth battle fraught with controversy for a record that only a handful of people actually care about. Similar in spirit to many academic battles.

More than just a good movie, it brought back memories from my high school days when video arcades were at their prime. I spent too many nights at the Willowbrook Mall arcade in New Jersey playing Donkey Kong, Pac Mac, Centipede and the like with their simple graphics and repetitive play. These arcade got quite crowded with a few local celebrities that could break a machines record with quite a crowd looking on. Much bigger crowds than Wiebe draws in his world record attempts in the documentary.

I was never a great video game player, I actually prefer pinball, but we took good notes and writing microcomputer simulations of some popular games became a hobby of mine (see Ribbit). I had just enough success to bring me heavily into computers and thus computer science. A little more success and I probably would not have gone into an academic career. Life moves in mysterious ways.

I would reminisce much more about those old video arcades but it's my turn on Guitar Hero. Rock on.

Great Ideas In Theoretical Computer Science Lectures 2-7
from Scott Aaronson at 14:34 PM GMT

For those who missed it on the sidebar, we now have six more GITCS lecture notes available:

Lecture 2: Logic

Lecture 3: Circuits and Finite Automata

Lecture 4: Turing Machines

Lecture 5: Reducibility and Gödel

Lecture 6: Minds and Machines

Lecture 7: Complexity

More are on the way — compared to the Democritus notes, it’s so much easier with others doing the writing! These notes were prepared almost entirely by the students, with only minor editing from me and Yinmeng. In general, I think the students have been doing a fantastic job. On the other hand, if you rely on these notes to build a Turing-machine-controlled jumbo jet which then crashes in the Himalayas, it’s entirely possible that it wasn’t my fault.

Biweekly links for 03/10/2008
from Michael Nielsen at 10:53 AM GMT

Click here for all of my del.icio.us bookmarks.

On March 09, 2008

Social Networking Ads (updated)
from S. Muthu Muthukrishnan at 13:12 PM GMT
Sometime ago, I was deliriously sick in Kyoto, and R. Ravi saved me by reading maps, negotiating taxis, organizing the meal, and getting me back to my hotel, syrups and pills in hand. Last night, after some Jazz, Coffee and talking work with him --- futuristic formulations of economic games in internet advertising --- too hyper to immediately fall asleep, I remembered his recommendation of a NYer story. I am behind on catching up with NYers, but I hopped ahead to this story --- Raj, Bohemian --- in the current issue, and in some ways, felt rescued again. The story is in the ilk of Murakami or Bret Easton Ellis, but doesn't quite get quite as zany or suave. It is ultimately about advertising in social networks, the old fashioned kind, and makes this post definitely CS, if you fall asleep thinking about the underlying mechanisms.

On March 08, 2008

Practice, Practice (updated)
from S. Muthu Muthukrishnan at 19:45 PM GMT
I got to Carnegie Hall the easy way, the rain aside. A short cab ride and free tickets. Not to the main hall that was hosting Joan Osborne, but next door, to the smaller gem of Weill Recital Hall that hosted the Distinctive Debuts series. Martin Grubinger, the multipercussionist, was the performer with Per Rundberg on Piano. Martin thumped ones' eardrums to a frantic frequency and simmered them down with the magical marimbaphone (with multiple mallets in each of his hands) until there was near-silence and even the scratching of my pen on paper felt like an intrusion (videos, clips 3, 5). Brilliant, as the British youth would say. For the encore, he brought on some boyish playfulness --- no one can really be close to drums for any period of time without being playful --- and his father joined in, and one eventually understood how the little boy Martin could have started on this path for his life at the age of 5. I wrote off this week as a loss, took it off my books, because I had to miss my private tour of the Guggenheim museum on Thursday, but this friday evening performance saved the week.

On March 07, 2008

Statement on conceptual contributions in theory
from Scott Aaronson at 18:27 PM GMT

About six months ago, a group of theoretical computer scientists started raising concerns about what they saw as a growing problem in our field. (My parody post “FOCS’36 notification” was one attempt to explain what this problem is.) The group has now put together a statement, which I was happy to sign, and which is meant to serve as a starting point for further discussion at the STOC’08 business meeting. If you support this statement and want add your name to it, please say so in the comments section! Of course criticism is welcome too. –SA


We, the undersigned, are concerned about two related attitudes that seem to be increasingly prevalent in TCS community, and in particular, are affecting its program committees and their decisions. The goal of this statement is to attempt to recognize and reverse this trend. We are happy to note that the STOC’08 PC made a conscious effort to move in the direction of this proposal.

The trends that worry us are the following:

  1. Assignment of little weight to “conceptual” considerations, while assigning the dominant weight to technical considerations.
  2. The view that technical simplicity is a drawback, and the failure to realize that simple observations may represent an important mind-switch that can pave the way to significant progress.

Most works offer a mix of conceptual and technical aspects, where by “conceptual” we mean the aspects that can be communicated succinctly, with a minimum amount of technical notation, and yet their content reshapes our view/understanding. Conceptual contributions can be thought of as contents of the work that are most likely to be a part of a scientific hallway discussion. They may appear in a work’s “bottom line” or “along the way”.

  • A conceptual “bottom line” may be a result that affects the worldview of researchers outside the community studying the problem, or the introduction of a new problem that may appeal to the wider TCS community.
  • A conceptual aspect “along the way” may be an innovative way of modeling, looking at, or manipulating a known object or problem, including establishing a new connection between known objects/problems.

Needless to say, the above list is not exhaustive.

Once understood, conceptual aspects tend to be viewed as obvious, which actually means that they have become fully incorporated in the worldview of the expert. This positive effect is actually a source of trouble in the evaluation process, because the evaluators forget that these contributions were not obvious at all before being made.

Indeed, our community should be warned of dismissing such contributions by saying “yes, but that’s obvious”; when somebody says such a thing, one should ask “was it obvious to you before reading this article?”

We believe that the community needs to remain vigilant about these issues, and program committees should make a conscious effort to pay attention to conceptual contributions (as apparently done by the STOC’08 PC). This will enable our conferences to continue to be a driving force in the progress of our field.

Scott Aaronson
Allan Borodin
Bernard Chazelle
Oded Goldreich
Shafi Goldwasser
Richard Karp
Michael Kearns
Christos Papadimitriou
Madhu Sudan
Salil Vadhan

AI overhyped!!!!!!!!!!!!!!!!!!!!!!!!!!! (updated)
from Lance Fortnow at 16:50 PM GMT
(A commenter left an off-topic comment on my last entry. INSERT GENDER-NEUTRAL PRONOUN HERE SINCE I DO NOT KNOW GENDER OF COMMENTER raisesd a question of interest. I have made a blog entry out of it. (NOTE- if you want a topic discussed on this blog, better to email Lance or I directly rather than make an off-topic comment.))

Kurzweil and others in AI think that computers will surpassing human intelligence in about 30 years. For example, see this overly optimistic entry on wikipedia. The media also seems to over-hype things. For example, when Deep Blue beat Kasporov there were headlines about how computers are smarter than people. These types of article seem to overlook the computational complexity of some of these problems. (Though one can say that we work on worst case and asy results while they work on ``real world problems''.)

My impression of Computer Chess is that they originally wanted a domain where computers could learn and adapt, but winning became too important and computers became too fast, so that (very clever) brute force searches took over. They may have more luck with the game of Go which is likely not able to be won with (even very clever) brute force. However, the whole story seems to be to show the computers are nowhere near human intelligence. (I grant that these terms are hard to define.)
Algorithms and Grand Engineering Challenges (updated)
from S. Muthu Muthukrishnan at 15:11 PM GMT
I have some interaction, past and present, with the National Academy of Engineering (NAE), and it is always inspiring. An ongoing exercise at NAE is to gather thoughts about grand engineering challenges. You can take part in these polls, and participate in the discussions. The list is as follows:
  • Make solar energy economical
  • Provide energy from fusion
  • Provide access to clean water
  • Reverse-engineer the brain
  • Advance personalized learning
  • Develop carbon sequestration methods
  • Restore and improve urban Infrastructure
  • Engineer the tools of scientific discovery
  • Advance health informatics
  • Prevent nuclear terror
  • Engineer better medicines
  • Manage the nitrogen cycle
  • Secure cyberspace
  • Enhance virtual reality
I can immediately see a couple of these challenges where algorithms research will have an impact: secure cyberspace, health informatics, .. On second thought and beyond, I am sure algorithms research is needed to address each of these challenges, more directly in some cases than the others. May be that is really my problem: I like to see (applied) algorithms research as the central piece, with its own form and factor, but often, we are in the belly of a large beast. The beast gets the attention, it is easy to set it up, take it down, or play with it. The belly follows along. I struggle with this nearly every day.
Biweekly links for 03/07/2008
from Michael Nielsen at 10:53 AM GMT

Click here for all of my del.icio.us bookmarks.

On March 06, 2008

Endorsements and Game Theory (updated)
from Lance Fortnow at 15:50 PM GMT
If you are a big shot in the political world then endorsing a political candidate has a game theory flavor to it. I'm sure someone could make a formal game theory problem out of it. There are two possibly competing options:
  1. Endorse someone who you think will get the nomination.
  2. Endorse someone who you agree with politically.
And there are four scenarios.
  1. You endorse someone who you think will get the nomination but who you disagree with.
    1. They win: you may get power (e.g., a cabinet post) but you may not be able to use that power to do what you want. In short, you have power but have lost your integrity (If you have been in politics long enough thats probably already gone.)
    2. They lose: you have lost your power and your integrity. (Pat Robertson's endorsement of Guilliani may be like that.)
  2. You endorse someone who you agree with but probably won't get the nomination.
    1. If they win then you are in great shape. You get power and integrity.
    2. If the lose this isn't so bad since you still have your integrity. And if they did better-than-expected (e.g, Mike Huckabee) then you may have some power.
  3. You endorse someone who you agree with and who you think will get the nomination.
    1. If you endorse after its obvious they will get the nomination then you don't get much. (Six Republican Govenors recently endorsed McCain. Too late to get any brownie points for that. Or the Vice Presidency.) If you endorse before its obvious then you could get power and keep your integrity.
    2. If they lose then hope that it is not thought that your endorsement caused the loss.
  4. You endorse someone who you disagree with and who you think won't get the nomination. You may be in the wrong business.
WMAP 5-year results: live lecture
from Michael Nielsen at 13:41 PM GMT

Yesterday, Sean Caroll wrote an informative post about the WMAP 5-year data release. This morning at 9:30am (local time) Perimeter Institute will be doing a live broadcast of a talk on the subject by Eiichiro
Komatsu of the WMAP team. A second talk will follow Saturday at 2:10pm.

On March 05, 2008

Visions in Theory Workshop (updated)
from Lance Fortnow at 17:49 PM GMT
I got this email and was NOT asked to blog about it, but should have been:
Visions for Theoretical Computer Science

Theoretical Computer Science (TCS) aims to understand the intrinsic capabilities and limitations of efficient computation. This subfield of computer science has a record of producing unexpected discoveries of high impact, such as public-key cryptography and quantum computation; and of raising deep scientific questions, such as the P vs. NP question.

On May 17, 2008, the TCS community will engage in a CCC-sponsored "visioning" workshop at the University of Washington in Seattle. The goals of the visioning workshop will be to:
  1. Identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future,
  2. Distill these research directions into compelling "nuggets" that can quickly convey their importance to a layperson.

The nuggets produced in the workshop will serve to highlight the importance of sustained support for long-term, fundamental computing research, and to inspire the TCS community in its future efforts.

All researchers interested in theoretical computer science are encouraged to provide input for the visioning process. Since space is limited, those interested in attending should apply as soon as possible. (Ideas are welcome even from those who cannot attend.) More information is available at the workshop's website http://theorymatters.org/pmwiki/pmwiki.php?n=Visioning

Organizing Committee: Bernard Chazelle (Princeton), Anna Karlin (U. Washington), Richard Ladner (U. Washington), Dick Lipton (Georgia Tech), Salil Vadhan (Harvard).

About the Computing Community Consortium

The National Science Foundation created the Computing Community Consortium with the goal of stimulating the computing research community to imagine, articulate, and pursue more audacious research visions-visions that will capture the imagination and change the world. The CCC is funded through an NSF award to the Computing Research Association (www.cra.org); the CCC's Council operates as a committee of CRA.
Long-dreaded politics post
from Scott Aaronson at 14:04 PM GMT

Until today, I have failed to uphold one of the most sacred responsibilities of the guild of bloggers: that of weighing in on the Democratic primary. This is not because of any desire to keep politics out of this blog: I’ve never succeeded in keeping anything out of this blog. Rather, it’s because I find the question genuinely difficult.

The general election is so damn easy by comparison. There, the only questions I need to ask myself are, “do I prefer the Enlightenment or the Dark Ages that preceded it? Is the Earth 4.6 billion years old or 10,000? Do anti-gay laws spring from a less repugnant part of human nature than Jim Crow laws?” While I look forward to the day when my answers to such questions won’t determine my vote, so far they unfailingly have — thereby eliminating the need for me to adjudicate more complicated social and economic issues that I don’t really understand.

In other words, my view of Democrats and Republicans couldn’t possibly be further from that of (say) Eliezer Yudkowsky, who sees the general election as a meaningless, Kang vs. Kodos popularity contest. Like Yudkowsky, I can easily imagine two political parties fighting over nothing — but what I see in reality is a clearly-identifiable neo-Union and neo-Confederacy, who every four years re-fight the Civil War. As many others have pointed out, even the geographic boundary between the two subcountries has barely changed since the 1860’s; the one real irony is that the “party of Lincoln” now represents the Confederate side. (And yes, if the free-market/libertarian wing of the Republican Party ever broke free of the medieval wing, then the correspondence would break down. I’m only talking about things as they currently stand.)

On the other hand, as Clinton and Obama debated their subtly-different proposals for healthcare, subprime lending reform, etc., I realized that, in a race between Democrats (or the general election in a more normal country), my “go with the Enlightenment” approach can only take me so far. Faced with two non-lunatic candidates, I might have to, like, know something about policy or economics before I could make a sensible choice.

So being an ignorant computer scientist, what can I say? Let’s start with the obvious: that after seven years of Bush, to ask whether I “prefer” Hillary or Obama is like asking a drowning person surrounded by sharks which of two lifeboats he prefers to be rescued by (and adding, in case it’s helpful, that one lifeboat is rowed by a woman and the other by a half-Kenyan). It’s a shame we can’t elect both of them, and then send one back in time to have been president for the last eight years. As the next best option, I wish the candidates would just agree right now to choose the winner by an Intrade-weighted coin flip, and thereby save their money for defeating the religious-right-courting hypocrite McCain.

But of course they won’t do that, and hence the question of which to prefer. Until recently I had a mild preference for Hillary, my reasons being as follows:

  1. Because she’s been despised for so many years by so many people who I despise (and the worse they say about her, the better she seems).
  2. Because she’s been doing better than Obama in crucial swing states like Florida.
  3. Because with her you get all the advantages of her husband but with considerably less chance of a sex scandal.
  4. Because on one issue that I actually follow — ending the Republicans’ “war on science” — her position paper is full of excellent specifics, whereas (so far as I know) Obama has only said much vaguer things in the same direction.

Recently, though, I’ve been tilting more toward Obama, for five reasons:

  1. Because he’s winning (still, after last night). This, of course, would be an important piece of evidence about his likelihood of winning the general election, even if it weren’t also a prerequisite to winning.
  2. Because unlike Hillary, he’s clearly stated his position on the inefficiency of bubblesort.
  3. Because I’m told that some Americans now supplement their reading of text by the viewing of “YouTubes” and “tele-vision boxes” — and in those settings, Obama does better. His jokes succeed where Hillary’s fall flat.
  4. Because the 2000 and 2004 elections suggest that experience is now a severe liability: it simply translates into more things that an opponent can turn against you.
  5. Because people whose judgment I respect, and who follow politics more closely than I do, seem to prefer Obama by a wide margin. As in Aumann’s Agreement Theorem, the mere fact of other people’s opinions ought to change my own opinion if I’m a rational agent; whether for rational reasons or not, it does.

Incidentally, so far as I can tell, the accusations of anti-Semitism against Obama that have filled the right-wing blogosphere are completely baseless. The assumption underlying these accusations is that admiration is a transitive predicate: that is, if x admires y and y admires z (where, say, z=Farakkhan), then x must admire z, even if x claims to reject and denounce z. But it’s easy to think of counterexamples: I admire Sakharov who admired Stalin (at least for part of his life), I admire Bertrand Russell who admired all sorts of thugs and poseurs, etc. Of course it’s impossible to know Obama’s heart about these matters, but I don’t think one needs to: it’s enough to know his brain.

In 6, no less, no more (updated)
from S. Muthu Muthukrishnan at 13:01 PM GMT
Here is another homage to NYer. People's biographies, each in 6 words. Six words can tell a story. Lizzie Widdicombe can too, in sixers! “Well, I thought it was funny.”
Even Out (updated)
from S. Muthu Muthukrishnan at 12:56 PM GMT
Some days the world puts a jinx on you. Things, small or big, don't go your way, and you can say it ain't so, but you can't pull yourself out. So, you take a break and read a note: Shouts and Murmurs discusses how things even out:
Try this simple test: flip a coin, over and over again, calling out “Heads!” or “Tails!” after each flip. Half the time people will ask you to please stop.

On March 04, 2008

Skipping Class (updated)
from Lance Fortnow at 11:43 AM GMT
Someone on the job market was wondering how many classes they could skip teaching in a typical term. As this is generally not a good question to ask during an interview, I was asked instead. Surprisingly the person wants to remain anonymous. I can't remain anonymous answering here, but then again I have tenure.

First a little math exercise that I have done since I was an undergrad. Let's take a student who take five courses per quarter. There are about 28 hours/quarter and 3 quarters. Northwestern University tuition is $35,064, coming to $83.49/hour. If you have 30 students that amounts to a bit over $25K of tuition spent on each hour you teach.

This is false math, but students are often paying the big bucks for college, including the opportunity to be taught by leading researchers in the field. You shouldn't deprive them on a regular basis.

Nevertheless sometimes you have a workshop or a conference that you don't want to miss. As a general rule you shouldn't skip enough classes that students feel cheated. There are many factors that should be taken into consideration.

  • Why are you missing the class? Do you have a family emergency? Are you a speaker at some conference? Are you visiting another university? Doing consulting work? Taking a vacation?
  • What level of class? Skipping an undergraduate class is different than skipping a graduate seminar.
  • Is there an easy make-up time that works well for the students? Can you find a replacement instructor?
  • What is the standard at your university? Could be different between schools and departments as well. My business school friends cannot miss classes. MBAs get upset easily.
  • What is your current status? Missing classes is a sign of irresponsibility. It can hurt your tenure case if you do it too much.
In the end follow your conscience. You owe it to your students to teach a good course and showing up matters.

On March 03, 2008

More things everyone should know about science
from Michael Nielsen at 18:31 PM GMT

Chad Orzel has a great response to Eva’s question for SciBarCamp, “What are the ten things everyone should know about science?”:

I have three suggestions, which are really all part of one big idea:

1) Science is a Process, Not a Collection of Facts The essence of science, broadly defined, is that it is a systematic approach to figuring out how the world works:

1. look at the world around you

2. come up with an idea for why it might work that way.

3. test your idea against reality.

… making sure you do everything in your power to prove your idea in 2 wrong. When it’s your own ideas you’re testing, the easiest person in the world to fool is yourself.

(I know Chad didn’t intend this as a complete description, and I feel like I’m being pedantic with my addition. I’m on a bit of a kick right now thinking about how biases, especially confirmation bias, affect our view of the world, and how important skepticism is to the conduct of science.)

4. tell everybody you know the results of the test.

Put those steps together, over and over, and you have the best method ever devised for increasing our store of reliable knowledge. The precise facts found by this method are not as important as the process for finding them– given the process, and enough time, you can reconstruct whatever facts you need. The facts without the process are worse than useless, they’re dangerous.

2) Science is an essential human activity. You’ll often hear people who study art and literature wax rhapsodic about how the arts are the core of what makes us human– Harold Bloom attributes it all to Shakespeare, but you can find similar arguments for every field of art. Great paintings, famous sculptures, great works of music (classical only, mind– none of that noise you kids listen to)– all of these are held to capture the essence of humanity.

You don’t hear that said about science, but you should. Science is essential to our nature, because at its most basic, science consists of looking at the world and saying “Huh. I wonder why that happened?” Science is applied curiosity, and there’s no more human quality than that. (”Bloody-mindedness” is a close second.)

(And, from a purely practical point of view, science and the products thereof are the reason why we have the free time to sit around making and appreciating works of art. Without science, we’d still be plains apes scavanging the kills of more efficient predators than us.)

3) Anyone can do science. Science doesn’t depend on race and it doesn’t depend on gender. You don’t need to be rich to do science. You don’t even need to be good at math.

And, I might add, you don’t need to be “smart”. Every 3 year old kid pretty much applies the scientific method as Chad describes (well, they don’t usually publish). Scientists are just a lot more systematic and dedicated than most people.

Science is, fundamentally, nothing more than a systematic approach to looking at the world around us and figuring out how it works. Money and mathematics are tools that can help with this process, but the core of the enterprise is nothing more than a habit of mind.

One of the most pernicious lies told by our culture is that science is an elite and exclusive activity only available to a few. It leads to scientists being stigmatized as “nerds” or “geeks,” set apart from the rest of humanity, and it leads to tenured professors with Ph.D.’s in the humanities to say with a laugh “I just don’t understand science.”

Science does not require innate abilities beyond the standard-issue human genome. If you have the full complement of senses and a brain, you can do science. In fact, the core business of humanities scholars– sifting through texts looking for evidence to support a particular argument– is not really any different than the business of science. You come up with a theory of what’s going on in a particular work of literature, and then you check to see whether that holds up by systematically evaluating the evidence found in the text. That’s one step removed from doing science.

You may not understand a particular set of facts produced by science, but see point #1 above: Science is a process, not a collection of facts. You won’t necessarily understand all the facts of a particular science outside your own field of expertise– I don’t understand microbiology worth a damn– but if you have the brain power necessary to function as an autonomous adult, the process is within your grasp.

And again, if you have the process, you have the ability to eventually understand the facts. I don’t understand microbiology, because I haven’t been trained in those facts, but I know that I could understand it, and if I ever need that understanding, I know the process by which to get it. For that matter, I don’t understand feminist literary criticism, but I know that I could if I needed to, using the same mental toolbox.

FYI: PODS08 (updated)
from S. Muthu Muthukrishnan at 16:38 PM GMT
PODS is a SODA-esque conference, seen from an Algorithmus's point of view. The accepted papers are listed here; there are papers on stream algorithms, clustering, cache-oblivious data structures and much more.
Playing to Win (updated)
from Lance Fortnow at 15:11 PM GMT
Consider the following game: A player starts with 0 points. For 100 rounds, a player picks one of the following three actions in each round.
  1. Gets 7 points with probability 1/2, 3 points with probability 1/2.
  2. Gets 4 points with probability 1.
  3. Gets 10 points with probability 2/5, 0 points with probability 3/5.
The player wins by having at least 500 points at the end of the game. An alternative is to have two or more players with the winner as the one who has the highest score at the end.

What is the right strategy? Initially play action 1 and towards the end possibly switch to action 2 if you are ahead and action 3 if you are behind.

Many sports have these kinds of actions to keep the game exciting even if one player has a lead. Action 2 corresponds to using a closing pitcher, or a prevent defense. Action 3 is using a pinch hitter, pulling the goalie or the "Hail Mary" pass.

Quidditch doesn't have these options rather having a final move that usually dominates the rest of the scoring. The scoring rules of Quidditch is J.K. Rowling's biggest blunder in the Harry Potter universe.

Sometimes you do see action 2 moves earlier in a game. For example in football, after a touchdown a team can either kick for an extra point or run a short play to try for two. Kicks are are rarely missed and the plays are successful slightly more than half the time. Yet most coaches just kick unless there is a significant advantage to go for two.

The choices above apply to many more arenas than just sports. Obama and Clinton have been following actions 2 and 3 respectively over the last few weeks. Which approach will work? We'll find out tomorrow.

Call for Eccentricities (updated)
from S. Muthu Muthukrishnan at 11:31 AM GMT
I heard about this mathematician who had a reputation for speaking fast, and was about to give his talk at the colloquium. The host requests him to define everything in English as well as in Russian, hoping to slow him down by a factor of 2. The mathematician says, "No problem. I was not going to define anything anyway."

We academics are eccentric (so are other professionals, but that is a different blog post). Eccentric in how we write papers, give talks, or just be. If you know good episodes of academic eccentricities, seen live or heard secondhand, let me know.
Biweekly links for 03/03/2008
from Michael Nielsen at 10:53 AM GMT

Click here for all of my del.icio.us bookmarks.

Penrose’s Gödel argument in rap
from Scott Aaronson at 03:39 AM GMT

About as logically sound as the original, and with a somewhat better backbeat (link to MP3).  From computer science grad student / hip-hop artist MC Plus+.

On March 02, 2008

Sports Laughs (updated)
from S. Muthu Muthukrishnan at 15:21 PM GMT
On the left is the oldie, Monty Python: greeks and germans talk it out on the soccer field. On the right is the newbie, ONN (Onion News Network), the "greatest export from Wisconsin": NASCAR secrets revealed (at the end of the video, there are links to more ONN gems).



John Francis on the value of silence
from Michael Nielsen at 01:50 AM GMT

John Francis decided to stop speaking for seventeen years. Here’s part of a remarkable interview with Mark Hertsgaard, where Francis talks about the personal effect of his decision to stop speaking:

Interviewer: I’m going to read a passage from your book about your decision to stop speaking: “Most of my adult life I have not been listening fully. I only listened long enough to determine whether the speaker’s ideas matched my own. If they didn’t, I would stop listening, and my mind would race ahead to compose an argument against what I believed the speaker’s idea or position to be.”

Francis: That was one of the tearful lessons for me. Because when I realized that I hadn’t been listening, it was as if I had locked away half of my life. I just hadn’t been living half of my life. Silence is not just not talking. It’s a void. It’s a place where all things come from. All voices, all creation comes out of this silence. So when you’re standing on the edge of silence, you hear things you’ve never heard before, and you hear things in ways you’ve never heard them before. And what I would disagree with one time, I might now agree with in another way, with another understanding.

On March 01, 2008

Mass scientific literacy
from Michael Nielsen at 16:34 PM GMT

Here’s Eva Amsen’s idea for a event at SciBarCamp:

My idea: find 4 or 5 volunteers from different backgrounds to sit on a 20 minute panel and (with audience feedback) make a list of Ten Things Everyone Should Know About Science. Since we have a wide audience, this hopefully would be a varied list. Actually, maybe we could just put up a large sheet of paper and have people write down what they think should be on the list and get back to it later.

It’s a really interesting idea, and relates to the question in my last post about finding ways to better incorporate science into public policy.

My number one suggestion for Eva’s list is a deep practical understanding of how science works: what it means to know something, how something comes to be known, the provisional nature of all knowledge, the need to be aware of our own biases, and so on.

A sign that this is curretly lacking is the enormous pressure climate scientists are under to present a clear and simple story to the public about climate change. If they admit to uncertainty or complexity, it is seized on by their opponents as evidence that climate change is not happening. Yet such uncertainty is an essential part of the scientific process. One must confront it head on to get at the truth, and a public discourse in which this uncertainy is absent cannot possibly reflect the underlying truth; in a democracy, this means that science can play at most an indirect role in decision making. In a letter Richard Feynman explains how a colleague once saw through to where the truth lay between two competing points of view, one simple and clear, the other complex:

He smiled and reminded me he was an expert on judging evidence in difficult physics experiments. In physics the truth is rarely perfectly clear, and that is certainly universally the case in human affairs. Hence, what is not surrounded by uncertainty cannot be the truth

In his wonderful review of Ed Hutchins’ book “Cognition in the Wild” (read the whole thing!), Cosma Shalizi writes of the amazing things enabled by mass literacy. I wonder what changes in civilization would be enabled by mass scientific literacy? Here’s Cosma:

The nineteenth century, and to a lesser degree this one, have witnessed a dramatic expansion in the numbers of us engaged in administration, bureaucracy, management, oversight - that is to say, in formally-organized tasks of collective cognition and control. We did not invent bureaucracy, the mainstay of the ancient empires, but we’re much, much better at it than they were. A random American town of 200,000 - Piffleburg, WI, let us say - will have police, a rescue squad, a fire department, a hospital, universal schooling, several large factories, insurance offices, banks, a community college, a public library with several thousand volumes at least, a post office, public utilities, political parties, garbage collection, paved and usable roads everywhere, mercantile connections stretching across the country, and, with some luck, unions. These are corrupt, inefficient institutions which work poorly; every election, Piffleburg’s citizens mutter something like “what do we pay taxes for anyway?” Yet to run any one of these institutions at the level of honesty, efficiency and efficacy which makes Piffleburg grumble would have demanded the full powers and attention of even the ablest Roman propraetor or T’ang magistrate. That all of those institutions, plus the ones not restricted to a single city, could be run at once, and while governed by a very ordinary slice of common humanity, would have seemed to such officials flatly impossible.

The immediate question this raises, of why we are so much better at collective endeavors than the ancients, can be answered fairly simply. To a first approximation, the answer is: brute force and massive literacy. We teach nearly everyone to read and write, and to do it, by historical standards, at a high level. This lets us staff large bureaucracies (by some estimates, over 40% of the US workforce does data-handling), which lets us run an industrial economy (the trains run on time), which makes us rich enough to afford to educate everyone and keep them in bureaucratic employment, with some surplus left over to expand the system. This would do us no good if our ideas of administration were as shabby as those of our ancestors in the dark ages, but they’re not: we inherited those of the ancient empires, and have had quite a while to improve upon them (and improvements are made easier and faster by the large number of administrators and the high standard of literacy). Among the improvements are many techniques (standardized procedures, standardized parts, standardized credentials and jobs, explicit qualifications for jobs and goods, files, standardized categories) and devices (forms, punch cards, punch card tabulators, adding machines, card catalogs, and, recently, computers) for making the administration of people and things easier.

Questions
from Michael Nielsen at 13:12 PM GMT

I’m really excited - in a couple of weeks I’ve got an opportunity to talk with and ask questions of an incredibly diverse and interesting group of 100+ people at SciBarCamp. So I’ve been thinking about what sorts of big picture questions I find most interesting, and trying to prime myself in preparation. I decided to write a few down, mostly outside the list of familiar standards - how did life begin, how did the Universe start, and so on. I’ve written the post with a view towards SciBarCamp, but I’d also be really interested in hearing people’s thoughts in comments or email.

What role can science play in public policy?

This question bugs the heck out of me, since loads of important public policy decisions are made without an appreciation of relevant scientific input. There’s a standard litany of solutions people offer to this problem - “more focus on science literacy”, “more outreach”, “educate the decision makers”, “run for office”, and so on. All these answers are worthwhile, but none seem to me to get to the core issue: either we need to find a system that works differently and better than democracy, or else we need to find some way of integrating science into the heart of the polity. I don’t know how to do either of these things, but I’d like to know what other people think about it.

What are the best ways to organize groups for collective creativity?

Kevin Kelly has a couple of mind-expanding stories about collective creativity:

In 1990 about 5,000 attendees at a computer graphics conference were asked to operate a computer flight simulator devised by Loren Carpenter. Each participant was connected into a network via a virtual joy stick. Each of the 5,000 copilots could move the plane’s up/down, left/right controls as they saw fit, but the equipment was rigged so that the jet responded to the average decisions of the swarm of 5,000 participants. The flight took place in a large auditorium, so there was lateral communication (shouting) among the 5,000 copilots as they attempted to steer the plane. Remarkably, 5,000 novices were able to land a jet with almost no direction or coordination from above. One came away, as I did, convinced of the remarkable power of distributed, decentralized, autonomous, dumb control.

About five years after the first show […] Carpenter returned to the same conference with an improved set of simulations, better audience input controls, and greater expectations. This time, instead of flying a jet, the challenge was to steer a submarine through a 3D under-sea world to capture some sea monster eggs. The same audience now had more choices, more dimensions, and more controls. The sub could go up/down, forward/back, open claws, close claws, and so on, with far more liberty than the jet had. When the audience first took command of the submarine, nothing happened. Audience members wiggled this control and that, shouted and counter-shouted instructions to one another, but nothing moved. Each person’s instructions were being canceled by another person’s orders. There was no cohesion. The sub didn’t budge.

Finally Loren Carpenter’s voice boomed from a loudspeaker in the back of the room. “Why don’t you guys go to the right?” he hollered. Click! Instantly the sub zipped of to the right. With emergent coordination the audience adjusted the details of sailing and smoothly set off in search of sea monster eggs.

Collective creativity is at the beginning of a long boom (look at Wikipedia go!), and it seems there are lots of new opportunities for collective creativity in science, the arts, and other areas. I’d love to hear good ideas about collective creativity at SciBarCamp, perhaps from a programmer like Reg Braithwaite, whose experiences seem to me to blend much of what it means to be creative in both science and art, or maybe from a Jazz musician like Isaac Ezer.

How is the web going to impact the process and institutions of science?

This is, of course, a question of great personal interest to me; I think we’re at the start of a major revolution in the processes and institutions of science. It seems like nearly all the participants are going to have interesting things to say about science and the web, including people like science blogger (and SciBarCamp co-conspirator) Eva Amsen, synthetic biologist (and promoter of open biology) Andrew Hessel, and Troy McConaghy, who does all sorts of amazing science-related stuff in Second Life.

I have about 50 other questions I’d like to add to my list, but if I do so this post will stop being a blog post, and will instead turn into a rather peculiar book, so perhaps I should stop there. One final question that I can’t resist because it’s so personally important for me: how do people manage their creative lives? This includes things like finding the discipline to do creative work, keeping the wolves of distraction and unfortunate obligation at bay, and managing all the information and decisions we seem to labour under. I’d sure like to hear other people’s experiences and ideas about all these things.

On February 29, 2008

How to run an unconference: 19 useful online resources
from Michael Nielsen at 15:14 PM GMT

As part of helping out with SciBarCamp, I’ve been studying other people’s experiences with unconferences. This post is a collection of some of the more useful links I’ve found.

ToCT is a Go (updated)
from Lance Fortnow at 13:22 PM GMT
The ACM Transactions on Computation Theory, with yours truly as Editor-in-Chief, is now accepting submissions.
ACM Transactions on Computation Theory will cover theoretical computer science complementing the scope of the ACM Transactions on Algorithms and the ACM Transactions on Computational Logic including, but not limited to, computational complexity, foundations of cryptography, randomness in computing, coding theory, models of computation including parallel, distributed and quantum and other emerging models, computational learning theory, theoretical computer science aspects of areas such as databases, information retrieval, economic models and networks.
The journal will be available online on the ACM Digital Library and to those who are SIGACT Members ($18/year which also gives you access to STOC proceedings, ACM Transactions on Algorithms and SIGACT News).

We have an excellent editorial board awaiting your papers. So either go to the ToCT web page or directly to the submission server, submit your papers, and come in on the ground floor of what will be one of the great theory journals.

Biweekly links for 02/29/2008
from Michael Nielsen at 10:53 AM GMT

Click here for all of my del.icio.us bookmarks.