« January 2006 | Main | March 2006 »

February 21, 2006

Pirates off the Coast of Paradise

At the beginning of graduate school, few people have a clear idea of what area of research they ultimately want to get into. Many come in with vague or ill-informed notions of their likes and dislikes, most of which are due to the idiosyncrasies of their undergraduate major's curriculum, and perhaps scraps of advice from busy professors. For Computer Science, it seems that most undergraduate curricula emphasize the physical computer, i.e., the programming, the operating system and basic algorithm analysis, over the science, let alone the underlying theory that makes computing itself understandable. For instance, as a teaching assistant for an algorithms course during my first semester in grad school, I was disabused of any preconceptions when many students had trouble designing, carrying-out, and writing-up a simple numerical experiment to measure the running time of an algorithm as a function of its input size, and I distinctly remember seeing several minds explode (and, not in the Eureka! sense) during a sketch of Cantor's diagonalization argument. When you consider these anecdotes along with the flat or declining numbers of students enrolling in computer science, we have a grim picture of both the value that society attributes to Computer Science and the future of the discipline.

The naive inference here would be that students are (rightly) shying away from a field that serves little purpose to society, or to them, beyond providing programming talent for other fields (e.g., the various biological or medical sciences, or IT departments, which have a bottomless appetite for people who can manage information with a computer). And, with programming jobs being outsourced to India and China, one might wonder if the future holds anything but an increasing Dilbert-ization of Computer Science.

This brings us to a recent talk delivered by Prof. Bernard Chazelle (CS, Princeton) at the AAAS Annual Meeting about the relevance of the Theory of Computer Science (TCS for short). Chazelle's talk was covered briefly by PhysOrg, although his separate and longer essay really does a better job of making the point,

Moore's Law has fueled computer science's sizzle and sparkle, but it may have obscured its uncanny resemblance to pre-Einstein physics: healthy and plump and ripe for a revolution. Computing promises to be the most disruptive scientific paradigm since quantum mechanics. Unfortunately, it is the proverbial riddle wrapped in a mystery inside an enigma. The stakes are high, for our inability to “get” what computing is all about may well play iceberg to the Titanic of modern science.

He means that behind the glitz and glam of iPods, Internet porn, and unmanned autonomous vehicles armed with GPS-guided missles, TCS has been drawing fundamental connections, through the paradigm of abstract computation, between previously disparate areas throughout science. Suresh Venkatasubramanian (see also Jeff Erickson and Lance Fortnow) phrases it in the form of something like a Buddhist koan,

Theoretical computer science would exist even if there were no computers.

Scott Aaronson, in his inimitable style, puts it more directly and draws an important connection with physics,

The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They're a great way to illustrate the point, they were probably essential for discovering the point, but they're not the point. The best definition of complexity theory I can think of is that it's quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods.

Actually, that last bit may be overstating things a little, but the idea is fair. Just as theoretical physics describes the physical limits of reality, theoretical computer science describes both the limits of what can be computed and how. But, what is physically possible is tightly related to what is computationally possible; physics is a certain kind of computation. For instance, a guiding principle of physics is that of energy minimization, which is a specific kind of search problem, and search problems are the hallmark of CS.

The Theory of Computer Science is, quite to the contrary of the impression with which I was left after my several TCS courses in graduate school, much more than proving that certain problems are "hard" (NP-complete) or "easy" (in P), or that we can sometimes get "close" to the best much more easily than we can find the best itself (approximation algorithms), or especially that working in TCS requires learning a host of seemingly unrelated tricks, hacks and gimmicks. Were it only these, TCS would be interesting in the same way that Sudoku puzzles are interesting - mildly diverting for some time, but eventually you get tired of doing the same thing over and over.

Fortunately, TCS is much more than these things. It is the thin filament that connects the mathematics of every natural science, touching at once game theory, information theory, learning theory, search and optimization, number theory, and many more. Results in TCS, and in complexity theory specifically, have deep and profound implications for what the future will look like. (E.g., do we live in a world where no secret can actually be kept hidden from a nosey third party?) A few TCS-related topics that John Baez, a mathematical physicist at UC Riverside who's become a promoter of TCS, pointed to recently include "cryptographic hash functions, pseudo-random number generators, and the amazing theorem of Razborov and Rudich which says roughly that if P is not equal to NP, then this fact is hard to prove." (If you know what P and NP mean, then this last one probably doesn't seem that surprising, but that means you're thinking about it in the wrong direction!) In fact, the question of P versus NP may even have something to say about the kind of self-consistency we can expect in the laws of physics, and whether we can ever hope to find a Grand Unified Theory. (For those of you hoping for worm-hole-based FTL travel in the future, P vs. NP now concerns you, too.)

Alas my enthusiasm for these implications and connections is stunted by a developing cynicism, not because of a failure to deliver on its founding promises (as, for instance, was the problem that ultimately toppled artificial intelligence), but rather because of its inability to convince not just the funding agencies like NSF that it matters, but its inability to convince the rest of Computer Science that it matters. That is, TCS is a vitally important, but a needlessly remote, field of CS, and is valued by the rest of CS for reasons analogous to those for which CS is valued by other disciplines: its ability to get things done, i.e., actual algorithms. This problem is aggravated by the fact that the mathematical training necessary to build toward a career in TCS is not a part of the standard CS curriculum (I mean at the undergraduate level, but the graduate one seems equally faulted). Instead, you acquire that knowledge by either working with the luminaries of the field (if you end up at the right school), or by essentially picking up the equivalent of a degree in higher mathematics (e.g., analysis, measure theory, abstract algebra, group theory, etc.). As Chazelle puts it in his pre-talk interview, "Computer science ... is messy and infuriatingly complex." I argue that this complexity is what makes CS, and particularly TCS, inaccessible and hard-to-appreciated. If Computer Science as a discipline wants to survive to see the "revolution" Chazelle forecasts, it needs to reevaluate how it trains its future members, what it means to have a science of computers, and even further, what it means to have a theory of computers (a point CS does abysmally on). No computer scientist likes to be told her particular area of study is glorified programming, but without significant internal and external restructuring, that is all Computer Science will be to the rest of the world.

posted February 21, 2006 12:06 AM in Scientifically Speaking | permalink | Comments (0)

February 13, 2006

Sampling science

Three things that recently caught my attention in my web-trawling:

The first is newly published work by a team of MIT neuroscientists who study rats and memory. They discovered that the neurons in rat brains have an instant-replay behavior that kicks-in during the idle periods between actions. Except, this is not the replay that many of us experience just after learning a new task, when we play the events over in our mind sequentially. No, rats think about things in reverse and at high-speed!

D. J. Foster and M. A. Wilson Nature, advance online publication 10.1038/04587 (2006)

The second is a recent posting on arxiv.org by three Argentinian mathematicians on the quality of fits to power-law distributions using the standard least-squares method. Given my own interest in power laws, and my own work on statistical methods for characterizing them, this paper confirms what many of us in the field have known in practice for some time: least-squares is a horrible way to measure the scaling exponent of a power law. From the abstract:

In this work we study the condition number of the least square matrix corresponding to scale free networks. We compute a theoretical lower bound of the condition number which proves that they are ill conditioned. Also, we analyze several matrices from networks generated with the linear preferential attachment model showing that it is very difficult to compute the power law exponent by the least square method due to the severe lost of accuracy expected from the corresponding condition numbers.

And finally, although touch-sensitive screens are (almost) everywhere today, they are merely single-touch interfaces. That is, you can only touch them in one place at a time. Enter multi-touch interfaces (direct link to the video), developed by a team at NYU. Reminscient of the interfaces seen in Minority Report and The Island, in which table-top or wall-sized displays interact with users via "gestures". I can't wait until I can get one of these things.

posted February 13, 2006 04:34 AM in Scientifically Speaking | permalink | Comments (1)

February 09, 2006

What intelligent design is really about

In the continuing saga of the topic, the Washington Post has an excellent (although a little lengthy) article (supplementary commentary) about the real issues underlaying the latest attack on evolution by creationists, a.k.a. intelligent designers. Quoting liberally,

If intelligent design advocates have generally been blind to the overwhelming evidence for evolution, scientists have generally been deaf to concerns about evolution's implications.

Or rather, as Russell Moore, a dean at the Southern Baptist Theological Seminary puts it in the article, "...most Americans fear a world in which everything is reduced to biology." It is a purely emotional argument for creationists, which is probably what makes it so difficult for them to understand the rational arguments of scientists. At its very root, creationism rebels against the idea of a world that is indifferent to their feelings and indifferent to their existence.

But, even Darwin struggled with this idea. In the end, he resolved the cognitive dissonance between his own piety and his deep understanding of biology by subscribing to the "blind watchmaker" point of view.

[Darwin] realized [his theory] was going to be controversial, but far from being anti-religious, ... Darwin saw evolution as evidence of an orderly, Christian God. While his findings contradicted literal interpretations of the Bible and the special place that human beings have in creation, Darwin believed he was showing something even more grand -- that God's hand was present in all living things... The machine [of natural selection], Darwin eventually concluded, was the way God brought complex life into existence.

(Emphasis mine.) The uncomfortable truth for those who wish for a personal God is that, by removing his active involvement in day-to-day affairs (i.e., God does not answer prayers), evolution makes the world less forgiving and less loving. It also makes it less cruel and less spiteful, as it lacks evil of the supernatural caliber. Evolution cuts away the black, the white and even the grey, leaving only the indifference of nature. This lack of higher meaning is exactly what creationists rebel against at a basal level.

So, without that higher (supernatural) meaning, without (supernatural) morality, what is mankind to do? As always, Richard Dawkins puts it succinctly, in his inimitable way.

Dawkins believes that, alone on Earth, human beings can rebel against the mechanistic indifference of nature. Understanding the pitiless ways of natural selection is precisely what can make humans moral, Dawkins said. It is human agency, human rationality and human law that can create a world more compassionate than nature, not a religious view that falsely sees the universe as fundamentally good and benevolent.

Isn't the ideal put forth in the American Constitution one of a secular civil society where we decide our own fate, we decide our own rules of behavior, and we decide what is moral and immoral? Perhaps the Christian creationists that wish for evolution, and all it represents, to be evicted from public education aren't so different from certain other factions that are hostile to secular civil society.

posted February 9, 2006 11:17 PM in Thinking Aloud | permalink | Comments (0)

February 07, 2006

Dodgeball

Dodgeball is social software done right: an easy interface, sensible (and voluntary) rules of participation and convenient for the mobile world of youth. (Would you be surprised to know that Google bought Dodgeball in 2005? Didn't think so.) Why isn't this ubiquitous? Probably because it needs a critical mass of users before it becomes a valuable experience to them all. Thus, their tag line should instead be "Dodgeball - it's everywhere you want to be."

posted February 7, 2006 12:21 AM in Self Referential | permalink | Comments (0)

February 06, 2006

A perfect monster

This is so on the mark that it's a bit scary. (Tip to Terry.)

posted February 6, 2006 12:25 AM in Humor | permalink | Comments (0)

February 01, 2006

Defending academic freedom

Michael Bérubé, a literature and culture studies professor at Penn. State University, has written a lecture (now an essay) on the academic freedom of the professoriat and the demands by (radical right) conservatives to demolish it, through state-oversight, in the name of... academic freedom. The Medium Lobster would indeed be proud.

As someone who believes deeply in the importance of the free pursuit of intellectual endeavors, and who has a strong interest in the institutions that facilitate that path (understandable given my current choice of careers), Bérubé's commentary resonated strongly with me. Primarily, I just want to advertise Bérubé's essay, but I can't help but editorialize a little. Let's start with the late Sidney Hook, a liberal who turned staunchly conservative as a result of pondering the threat of Communism, who wrote in his 1970 book Academic Freedom and Academic Anarchy that

The qualified teacher, whose qualifications may be inferred from his acquisition of tenure, has the right honestly to reach, and hold, and proclaim any conclusion in the field of his competence. In other words, academic freedom carries with it the right to heresy as well as the right to restate and defend the traditional views. This takes in considerable ground. If a teacher in honest pursuit of an inquiry or argument comes to a conclusion that appears fascist or communist or racist or what-not in the eyes of others, once he has been certified as professionally competent in the eyes of his peers, then those who believe in academic freedom must defend his right to be wrong—if they consider him wrong—whatever their orthodoxy may be.

That is, it doesn't matter what your political or religious stripes may be, academic freedom is a foundational part of having a free society. At it's heart, Hook's statement is simply a more academic restatement of Voltaire's famous assertion: "I disapprove of what you say, but I will defend to the death your right to say it." In today's age of unblinking irony (e.g., Bush's "Healthy Forests" initiative) for formerly shameful acts of corruption, cronyism and outright greed, such sentiments are depressingly rare.

Although I had read a little about the radical right's effort to install affirmative action for conservative professors in public universities (again, these people have no sense of irony), what I didn't know about is the national effort to introduce legislation (passed into law in Pennsylvania and pending in more than twenty other states) that gives the state oversight ability of the contents of the classroom, mostly by allowing students (non-experts) to sue professors (experts) for introducing controversial material in the classroom. Thus, the legislature and the courts (non-experts) would be able to define what is legally permissible classroom content, by clarifying the legal term "controversial", rather than professors (experts). Bérubé:

When [Ohio state senator Larry Mumper] introduced Senate Bill 24 [which allows students to sue professors, as described above] last year, he was asked by a Columbus Dispatch reporter what he would consider 'controversial matter' that should be barred from the classroom. "Religion and politics, those are the main things," he replied.

All I can say in response is that college is not a kind of dinner party. It can indeed be rude to bring up religion or politics at a dinner party, particularly if you are not familiar with all the guests. But at American universities, religion and politics are two of the hundreds of things we discuss on a daily basis. It really is part of our job, even — or especially — if some of us have unpopular opinions on those subjects.

How else do we learn but by having our pre- and misconceptions challenged by those people who have studied these things, been trained by other experts and been recognized by their peers as an authority? Without academic freedom as defined by Hook and defended by Bérubé, a university degree will signify nothing more than having received the official State-sanctioned version of truth. Few things would be more toxic to freedom and democracy.

posted February 1, 2006 10:45 PM in Simply Academic | permalink | Comments (0)