It runs in the family

So at dinner on Wednesday, I noticed that my younger brother (age 14, non-Honors Algebra II, smart but unmotivated, pretty much what I would have been had I had an academically overachieving older sibling) was filling out 16-man brackets. But these weren't NCAA basketball brackets (what he would have been doing with those in December is beyond me anyway), or fantasy NCAA football playoffs, or any of the above. They were 16 competitors labeled from "A" to "P."

So I asked him: What are you doing?
Him: Filling out brackets.
Me: Why?
(Silence).
(A little later)
Me: Chris, why are you filling out brackets all over your paper?
(Silence).
(Later still)
Him: Harrison, I have a question.
Me: Shoot.
Him: If you have 16 people and you know their initial positions in a bracket, what's the minimum number of spots you have to fill in so you can fill in the rest of the bracket?

I'm pretty sure I've been more proud of a member of my family than I was of him at that moment. But I'm having trouble thinking of an example.

[PS: I told him he should guest-post the problem on this blog. He politely declined.]

The (Complexity) Theory of NCLB

So, one of the biggest complaints we hear these days about the No Child Left Behind Act is the possibility, with "high-stakes testing," of teachers "teaching to the test." If students aren't actually learning the material, critics argue, then NCLB is hurting, not helping, these kids.

But the Atlanta Journal-Constitution yesterday wrote the following:

But why's that ["teaching to the test"] so terrible? If a test is an accurate measure of what should have been learned, teaching to the test is fine.

The AJC's editorial board makes a good point, but I thought I'd go ahead and state it a little more formally. So here we go:

A state Department of Education ("Dean") wishes to write a test satisfying NCLB requirements. Furthermore, Dean has to write the test in limited (i.e., polynomial) time; after all, we have to test new students at least every year! An overworked teacher ("Olivia") has to pass all her students, but wants to spend as little time teaching as possible. So if she can save time and effort by "teaching to the test," she'll do so.

Now, let's say that the time complexity for Olivia of actually teaching the material is O(f(n)) (where n is the length of the test, in problems). (She can talk as fast or as slow as she likes, which is why the implicit constant doesn't make a difference in this case.) Then Dean's goal is as follows: He wants to write a test T such that, for any probabilistic "teaching algorithm" with o(f(n)) time complexity that Olivia might use and any constant $\epsilon$ > 0, there exists a constant N such that, for a test T of length n > N,

Pr[J. Random Student passes test T after being taught by Olivia] < $\epsilon$.


If this reminds you of the formal definition of a one-way function, well, you should probably look up the formal definition of a one-way function, 'cause there's some pretty key differences. But actually, the analogy isn't all that bad. We certainly have some good candidates for OWFs, and it's not unreasonable to think that similar methods exist for creating tests that can't be "taught to."

OK, so my analogy's pretty weak. But I don't think it's unsaveable. Therefore, I'm willing to shell out $15 to anyone who can suitably formalize high-stakes testing in such a way that they can show that the existence of (trapdoor) one-way functions (perhaps relative to some sort of "curriculum oracle?") implies the existence of tests that aren't "teachable to."

If, on the other hand, you can convince me that it's always possible to cheat the system in any good formalization of HST, I'll pay you $25 (yeah, I'm cheap. I'm a student, get over it) and write a letter to my Congressman.


What I'm more concerned about with NCLB -- and, by the way, I'm shocked that complexity theorists aren't already up in arms about this -- is the requirement that, by 2014, all children will test at the "proficient" level on state tests. Look, the "pencil drop" is a classic element of standardized testing, and while I'm happy that Congress is so convinced that P = BPP, I think mandating full derandomization by 2014 -- while simultaneously providing so little funding -- is just insane.