Friday Random Ten, June 29

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

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.

Continue reading Graph Coloring Algorithms

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.

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

Continue reading Sewell's (not exactly a-) Law

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.

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