ck113

Seth Roberts has made his entire reputation on self-experimentation. (Partly on the strange things he claims to have learned by doing it, and also partly on his defense of it as a methodology.)

He's written some papers that talk about the methodological concerns. Here are two that Google churned up:

http://sethroberts.net/articles/2010%20The%20unreasonable%20...

http://escholarship.org/uc/item/2xc2h866

I can't honestly claim that he has successfully made n=1 experiments respectable, but I think it's safe to say he's very well aware of the criticism on these grounds and is not ignoring it.

All due respect, I don't think you're getting what Robin Hanson is about. (Which is understandable if this is the only post of his you've ever read.)

The point of this post isn't to criticize Alex Grass's choices, it's to point out that our social system has a rather bizarre bias. We applaud Grass's spending money on these charities -- presumably because it's an ostensibly selfless act -- despite the fact that he actually did more social good by making the money than he did by giving it away. (Not saying I agree, just trying to clarify.)

A running theme, maybe the primary theme, in this blog is that people make deeply suboptimal choices (whether measured by social interest or self interest) because they're really more interested in sending signals than they are in achieving optimal outcomes.

The blog is worth a longer look; for me, I don't know how much I agree with Hanson's signaling-centric view of the world, but I'm impressed with how deeply he thinks about these things, and how he manages to talk about these topics without devolving into misanthropically simplified "people are dumb" conclusions.

I think it's interesting. Not so much the ultimate question of whether they can find him, but rather the things we learn along the way about exactly how much a reader base with no special (e.g., law enforcement) privileges can dig up about someone they've never met. Not just general character facts about him (he's left handed), but also time- and date-stamped activities (he took a picture of his cat at this time and this place).

It would be a lot more interesting if each bullet point of information came with a link to a 'trail' describing how that factoid was uncovered. (For example, I'd be particularly interested in learning how we know about his ATM activity. Assuming no one got a court order, how we anyone get access to that info?)

Ok, I know it's violently tangential and pretty silly, but I noticed this in the article too. I thought it was interesting because (I'm guessing) it's not a case of the author not knowing the grammatical rules you've just described, but of his not knowing the saying he's quoting.

The phrase is "no wine before its time." Not as in "before it is time", but as in "before that wine's appointed time." It was the slogan of the Paul Masson winery, though I can't find a great source for that. (Maybe this one: http://wineeconomist.com/2009/02/10/no-wine-before-its-time/)

So we do want the possessive here, not the contraction.

It's mostly just a technicality of the definition. NP (and P for that matter) can only contain "decision problems," i.e., problems for which the answer must be Yes or No.

So the NP formulation of the Traveling Salesman problem is "does this graph admit a route of length less than K?" For any constant K, that's an NP-complete problem.

Sure, of course. I'm not out to convince anyone that P != NP here, especially not using Proof By Obviousness. I just meant to underline one of the intuitions that makes so many people believe they must be different.

Also, like so many terms in computer science, "harder" has different meanings in different subspecialities. To a complexity theorist, a problem that takes O(n^127) time to solve is not any harder than one that takes O(n) to solve -- they're both in the same hardness class. Just one of the many warpings in perspective that staring too long at P and NP can give you.

Ooh! Ooh! I just remembered another cool thing about the "polynomial-time verifier" formulation of NP. It makes it possible to phrase the P vs. NP question much more starkly.

The standard formulation of P vs. NP is something like "do deterministic polynomial-time Turning machines have the same power as nondeterministic polynomial-time Turing machines?" A deep question, but not a very snappy sentence.

But the alternate formulation is something like: "is it always as easy to find a correct answer as it is to check if a given answer is correct?" Really brings home why it seems so painfully obvious that P is not equal to NP (of course it's easier to check an answer than to find one), and makes it seem that much more profoundly strange that we haven't found a way to prove this.

From the article: "Another interesting feature of NP problems is that a solution can be checked in polynomial time by a deterministic Turing machine. So, checking a solution of a NP problem is a P problem."

That's not just an interesting feature of NP problems, it's an alternate definition. You can define NP as the class of problems that have polynomial-time "verifiers". That is, the class of problems for which, given a candidate solution, you can determine in polynomial time whether that solution is correct.

Examples: given a proposed assignment to the variables of a boolean formula, you can check in P-time whether that assignment satisfies the formula. Given a proposed route through a set of cities, you can check in polynomial time whether that route has length less than K. Given a set S of integers, a subset of S, and a target T, you can check in P-time whether that subset sums up to T. Etc.

I find the "polynomial time verifier" definition of NP to be much clearer than the "solvable by a polynomial-time nondeterministic Turing machine" definition. They're exactly equivalent -- I don't know why the latter is so much more common.

I thought this was the most telling line of the article: "Ultimately the first factor of performance is the maturity of the implementation."

That supports a common conviction held by fans of functional programming: if all of the years of arduous optimization that have been poured into GCC had instead been poured into (say) GHC, then Haskell would be even faster today than C is.

That is, to many people functional programming languages seem to have more potential for performance than lower-level procedural languages, since they give the compiler so much more to work with, and in the long run a compiler can optimize much better than a programmer. But so much more work has been put into the C-style compilers that it's hard to make a fair comparison. It's still hard, but this experiment seems to give some solace to the FP camp.

To make it even more abstruse, it's not usually results that we describe as "relativizing", but proofs and proof techniques.

For example, the proof technique we call "diagonalization" relativizes. If I prove that complexity class A is contained in complexity class B, what I'm formally proving is that a Turing machine obeying the resource constraints of class B (e.g., polynomial time) can solve any problem that can be solved by a TM obeying the resource constraints of class A (e.g., logarithmic space). If I prove this by diagonalization, then I've also proved that this inclusion holds even if the Turing machines are granted access to an "oracle" that can solve problems that the machines themselves could not solve.

Here's an example of where this gets interesting: it's been proven that there are oracles relative to which P=NP, and other oracles relative to which P != NP. This means that no relativizing proof (in particular, no proof by diagonalization) can ever resolve the P vs. NP question. (See why?)

So, oracle results don't tell us too much about the actual relationships between complexity classes, but they tell us about what kind of proofs we should and shouldn't bother trying to use to prove those relationships. It's a sign of just how hard complexity theory is that it's often considered a big achievement just to get an oracle result that tells you that the other proofs you were trying will never solve your problem.

If you're really interested, this line of research now goes beyond relativization. There's another barrier to proving complexity separations called "Natural Proofs" (http://en.wikipedia.org/wiki/Natural_proof), and more recently a third has been proposed called "Algebrization", which (far as I can tell) generalizes relativization to the case where we get access not only to oracles but to low-degree polynomial extensions of oracles. (Unfortunately, if you know what that means, you were probably already aware of the new results.)

I don't have an opinion about the Scheme -> Python switch, but I didn't find this a very compelling objection.

The author seems to assume that a CS degree is meant to teach you to write software. (E.g., "how exactly do you write software if you don't start with small working primitives (like unit tested classes, PLT scheme modules, or a PHP library script)? Isn't taking a complex problem and breaking it down into testable/reliable chunks a fundamental principal of writing software?") But who said anything about writing software? Certainly many CS grads do go on to write a fair amount of it, but it's hardly the only goal of the curriculum, especially at a place like MIT, where a CS grad is as likely to go on to a career in research as in programming.

The priorities here seem frankly bizarre; the author derides learning about "electricity whizzing through CPUs", but the principles governing how CPUs work are way more core to computer science than is unit testing, which is more of an industry best-practice than a deep principle.

Looking at it another way, a full education in CS is going to have to cover everything from processor hardware to programming techniques to theoretical foundations. Intro courses at most schools have tended to focus almost exclusively on programming. The old SICP-based intro course at MIT blended programming with a taste of theory, and the new intro course sounds like it will switch to blending programming with a taste of hardware and a crash course in real-world problems like faulty and undocumented libraries. I wouldn't say that's obviously a good move, but it's not obviously wrong, and it doesn't seem any less true to the soul of computer science.

If you're interested in wild speculation (I have no idea how Twitter's database works), here's how I interpreted Biz's explanation:

With the new system, say user Foo writes "@Bar lol me too!". Then Twitter can take Foo's follower list, join it with Bar's follower list, and send the message to everyone in the resulting list. Relational databases are very good at joins.

On the other hand, with the old system, they'd have to do a deep inspection of the record for each of Foo's followers to know if they should send the message to that follower. Relational databases are much less good at this.

But, as you and others have pointed out, if the number of users that use the "all @-replies" feature is really so small, it would be fairly inexpensive to cache the list of all of Foo's followers who use that feature, and join them in as well. I don't know why they don't do that -- maybe it adds up (like, if only 3% of users use the feature, but those users follow a lot of other users, they'll each end up in a lot of other users' caches).