Patent Reform modest proposal.

Companies over a certain size should be required to show that they have evaluated a patent claim from a small entity in good faith. That is, if they get a claim that they are infringing, they should be required to show in court that they looked at it seriously and tried to find out if they were infringing or not. Failure to do so would should trigger some financial penalties. The intent is to prevent a big company from relying on the cost of litigation and the resource mismatch to simply blow off legit patent assertions.

A basic design error in software

Suppose we didn’t know too much about bridge design, but were convinced that (a) the current design methods were too slow and unmodular to be useful, and (b) not knowing anything about structure other than what we could observe of completed bridges was no barrier to coming up with a new method. We might start by thinking, the bridge as a whole is too complex, let’s break it into parts to simplify. That seems sensible enough, so we decide to divide a bridge into modular sections  pilings, cabling, superstructure, and roadway. Then we divide our design team into parts and discover that the divisions make the design task harder. It turns out that the weight of the roadway makes a big difference to the design of the pilings and superstructure and, in fact, each of our components cannot be designed without deep information about the other components. We have transformed a hard problem into four harder problems.

Paying for music

Streaming services rely on a weird conceit, but it’s not a new one. Like record labels, these companies can’t exist—they literally have no product—without musicians. Yet hardly any musicians are pleased with the advent of digital streaming, and understandably so—they were already screwed by greedy record labels back when people went into actual brick-and-mortar stores and walked out with albums; so screwed in fact, that it’s entirely possible to sell four million albums and not make a cent. Meanwhile, record labels are happy to throw their weight behind anything that isn’t the old iTunes model, even if it’s Apple’s own Pandora copycat.

the terrible effect of Krohn-Rhodes

One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder (H_1 triangleleft H_2 ... triangleleft H_n=G)  to state machines, but it does it in a way that doesn’t get us very far in understanding the structure of state machines. The problem is that the “division” is too restrictive. In terms of state machines, KR requires us to turn M into M_1 rightarrow M_2 where the input of M_2 depends only on the system input and the output of M_1.  This is called a “loop free” decomposition and Hartmanis-Stearns worked on it before KR teased out the underlying math. You can build a ripple carry adder that way and it makes sense that the simple devices that concerned early CS researchers seemed amenable to such a decomposition, but a few steps down the path and we come to systems that do not want to be decomposed into loop-free series at all. Consider a queue – when a new element is inserted each element needs the output of its neighbor to the back to get its new value – very nicely loop free. But consider a stack. A push makes each element take an input from its neighbor to the right and a pop makes each element take an input from its neighbor to the left.

langle x_1, x_2 ... x_n rangle mapsto[push y] langle y, x_1 dots x_{n-1}rangle

langle x_1, x_2 ... x_n rangle mapsto[pop] langle x_2 dots x_{n},nullrangle

In fact the stack is serially loop free – it has a nice loop free ordering per operation – but Krohn-Rhodes doesn’t go there (you could get to loop free by adding a counter to each element).  Anyways, the result is a theory that bounces off the observed or designed structure of computational objects and, at least to me, that designed structure is the interesting structure.