1. **Thinking Plague: “The Aesthete”**: Thinking Plague is just plain *odd*. They’re

a hard-to-classify group. It’s got vocals, but instead of the vocals being the lead,

they treat voice as just another instrument. They’re often atonal, and when they’re

tonal, the chords are often very dissonant. They *sound* like they’re very influenced

by Robert Fripp’s guitar craft, and there’s a persistent rumour that their guitarist

is a crafty, but after the last time they came up in a FRT, he showed up in the

comments to say that he wasn’t. They’re definitely not a group that I’d recommend to

everyone, but if you’ve got the right kind of taste, they’re really quite remarkable.

2. **The Tap Room Trio, “The Blackberry Blossom/THe Ballina Lass”**: very traditional

Irish music by a trio including my favorite traditional flutist, the great Harry

Bradley. Very simple traditional arrangements of classic Irish tunes.

3. **Tortoise, “It’s All Around You”**: Tortoise is a very influential post-rock

band. Given how much I like post-rock, and how much of what I listen to is

supposedly influenced by Tortoise, I expected to really like them. I find this

to be incredibly dull – downright trite.

4. **Gentle Giant, “A Reunion”**: Progressive rock with strong madrigal influences.

GG is brilliant.

5. **Sigur Rós, “Andvari”**: Post-rock from a mellow Icelandic band. This is more like what postrock is supposed to be to me. It’s very mellow and subdued, but it’s got a

real depth and sophistication. Beautiful track.

6. **King Crimson, “The Howler”**: a track off of Beat, the second-album by Discipline-era KC. Very typical of the vocal tracks from that phase of KC: lots of

Fripp’s tape loops setting the structure of the track; Belew doing his crooning voice.

7. **Naftule’s Dream, “Something is There”**: Brilliant neo-Klezmer, for lack of a better word. Naftule’s Dream is named after Naftule Brandwine, the genius of Klezmer clarinet; they’re a modern band that plays stuff clearly inspired by Klezmer, but filtered

through a lens of modern jazz and some rock. There’s some Ornette Coleman and Some Robert Fripp in here, mixed with the klez. Highly recommended.

8. **Sonic Youth, “Mildred Pierce”**: If you know what Sonic Youth sounds like, this

is absolutely typical of their sound. If you don’t know, you should check it out.

They’re strange, harsh, loud, and very, very good.

9. **Dirty Three, “Dream Evie”**: one of my favorite postrock groups, playing in the

more classically inspired vein of PR; Dirty Three is always wonderful.

10. **Mogwai, “With Portfolio”**: another favorite PR band; this one comes from the more

rock-oriented side of things

# Monthly Archives: June 2007

# Graph Coloring Algorithms

Graph coloring is deceptively simple. The idea of coloring a graph is very straightforward, and it seems as if it should be relatively straightforward to find a coloring. It turns out to not be – in fact, it’s extremely difficult. A simple algorithm for graph coloring is easy to describe, but potentially extremely expensive to run.

# That Silly 8-Facts Thing

So that 8-facts thing is going around, and I got tagged. I’ve stalled long enough that everyone I read was already tagged, and I’m sure you’ve all seen it by now, so I’m not going to waste time repeating the rules or tagging anyone else.

1. One of my favorite things to do is cook. In fact, during grad school, when

I was particularly frustrated with my (then) advisor, I considered dropping out

of grad school and opening a restaurant.

2. It took three advisors for my to do my PhD. I started grad school with an offer

to work with one professor who did network protocol specification; by the end of my

first year, I was pretty sure that I didn’t want to keep working on that. I switched

to work with a theoretician on a strange computer architecture problem. He was a

total lunatic, and he really wasn’t interested in what I was working on – it was

work that he really wanted someone to do, but he didn’t really want to spend his time

thinking about it. Thank goodness, right around the time I became totally fed up,

the department hired a new faculty member, Lori Pollock, and within days of her

accepting the job, I was in her office asking her to be my advisor. I spend the next

four years working with her, and I still think she’s amazing. Best advisor ever!

(And I don’t even think she reads my blog!)

3. I can’t read maps. Not at all. They’re utterly meaningless to me. I’m a bit

learning disabled – I’ve got what’s called a perceptive impairment. One of the

problems that that’s caused me is the total inability to read maps, or catch balls.

4. I’m a musical instrument nut. I’ve got about 30 different tinwhistles, including

at least one in every key, two top-grade hand-made D whistles, and two giant low-D

whistles, two wooden flutes, 3 bamboo flutes, a magnificent selmer signature B-flat

clarinet, an old no-name A clarinet, 3 different antique albert clarinets,

a bluegrass banjo, and 2 Irish tenor banjos.

5. The first time I ever saw a real computer was in 6th grade. A classmate’s parent

brought it in to show my class. I was fascinated *instantly* by the idea of this thing

that I could teach to do math.

6. I like to build model airplanes out of paper. Not folded flying airplanes, but

very accurate, detailed scale models. For example, I’ve got a model of SpaceShipOne

which is about 5 inches long, made entirely of paper, down to the open landing gear

covers and struts.

7. I’m a huge fan of sculptor [Alexander Calder][calder]. Calder is best known for his

wonderful mobiles. The way that I discovered Calder was… the cover of my grad school

algorithms textbook. (My office mates and I just bought a replica of a Calder piece

to decorate our space.)

8. My wife and I got engaged one month to the day after we started dating. We didn’t

tell anyone except a few close friends for quite a while, because we didn’t think

her parents would accept it that quickly. We’d been friends for quite a while before

we started dating, but I’d never even considered asking her out, because she was

seeing someone else. Then she broke up with her ex-boyfriend, and showed up on my

doorstep the next morning, and pretty much never left.

[calder]: http://www.calder.org/

# Sewell's (not exactly a-) Law

In light of [my recent demolition of a purported improvement on the second law of thermodynamics][2l], an alert reader sent me [a link to this really boneheaded piece of work at Uncommon Descent by Granville Sewell][sewell].

[sewell]: http://www.uncommondescent.com/intelligent-design/introducing-sewells-law/

[2l]: http://scienceblogs.com/goodmath/2007/06/dembskis_buddy_part_2_murphys.php

Sewell is, yet again, trying to find some way of formulating IDist anti-evolution garbage in terms of the second law of evolution. Sewell’s been doing this for ages, and it’s been a

wretched failure. Naturally, according to Sewell that has *nothing* to do with the fact that his argument is a pile of rubbish – it’s all because people have been distracted by

arguments that came about because people don’t understand the second law of thermodynamics. It’s their confusion of 2LOT, *not* any flaw in Sewell’s argument.

So, he’s proposing a new law which he claims subsumes the 2LOT, and which he modestly names after himself:

# Get out your crayons: it's graph coloring time!

One kind of graph problem that’s extremely widely used in computer science is called *graph coloring*. There’s two versions of it, *vertex coloring*, and *face coloring*.

Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?

The variants of the vertex coloring problem are things like:

* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)

that can be used to color a graph?

* Given an integer N, can you find an N-coloring of the graph?

The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.

# Wonderful Mobius Transformation Video

Via The Art of Problem-Solving, a great video on Mobius transformations. I never really got how the inversion transformation fit in with the others before seeing this!

# Basic Graphs

Let’s talk a bit about graphs, being a tad more formal about them.

# The First Graph Theory Problem

Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.

My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.

Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around

the city, there were seven bridges connecting the parts of the city. Is it possible to

take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?

# PZ Has a Question: Is George Gilder Wrong About Network Theory?

PZ wrote about the latest nonsense from IDiot George Gilder. In this interview, Gilder tries to make some really horrible arguments about how everything is really hierarchical, and he uses “information theory, computer science, and network theory” as examples.

I believe that the universe is hierarchical, with creation at the top – the idea that there’s a creator and that we, at our best, act in his image. This top-down model is what all of my work has in common. I sensed that the basic flaw and failure of feminism was its gradient toward pure animal passion with no procreative purpose. In economics, I believed that it was the supply that created the demand. In my examination of computers and telecom, and subsequently biology, I saw the same thing. That’s really how I came into the intelligent design movement – through the recognition of this same structure that I’d previously examined in sexuality and economics, information theory, computer science and network theory.

PZ does a great job of tearing him down, but also asks:

Computer science and network theory: Gilder knows nothing about either, and has no training in the subjects. I suspect there are readers who know far more about the subject than Gilder: is network theory all about setting up strict hierarchies of top-down control?

And hey golly, that’s right smack dab in my area.

Network theory is seriously nifty stuff. It’s a sub-area of graph theory, which is one

of my favorite areas of computer science. And the short answer to PZs question is: “Hell no: in fact, if that *were* the case, it wouldn’t be an interesting subject at all. What makes it so interesting and difficult is precisely the fact that things aren’t hierarchical”.

# Simple Pathology: Betterave

Sorry for the missed weeks of friday pathological programming language columns. To be honest, I’m running out of languages. I’m sure there must be more, but my usual sources (dealers?) are running out – so send links!

Anyway, today I’m going to look at a really simple one, which I find fun. It’s

not an overly exciting language, but it is a language which is has semantics almost as

trivially simple as [BrainFuck][bf], but which ends up looking almost as much like line-noise as [TECO][teco]. It’s called [Betterave][betterave].

[betterave]: http://www.esolangs.org/wiki/Betterave

[teco]: http://scienceblogs.com/goodmath/2006/09/worlds_greatest_pathological_l_1.php

[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php