Reductions in practice: Semantic interpretation

So: last time, we talked about reductions in computer science. We certainly didn't exhaust the topic, but we at least got a definition on the board.

Now, there was one misleading thing that I didn't quite come out and say, but pretty strongly implied: I made it sound like the reason we would find a reduction of problem \(P\) to problem \(Q\), is that we have (or pretend we have for the purposes of proving something) a solution to problem \(Q\), and use that solution to give a solution to problem \(P\).

That is certainly one way to use a reduction. But, and this may come as a surprise, it's far more common to use reductions in another way: to show that problem \(Q\) is hard, because we can reduce problem \(P\) to problem \(Q\) and we somehow already know that \(P\) is hard to solve.

If this sounds like nonsense, I have a different way to describe this idea. The original explanation I gave can be thought of as saying

if there's a reduction from problem \(P\) to problem \(Q\), then the difficulty of problem \(Q\) is an upper bound for the difficulty of problem \(P\)

(whatever we precisely mean by "difficulty"). This new way of thinking about it then becomes

if there's a reduction from problem \(P\) to problem \(Q\), then the difficulty of problem \(P\) is a lower bound for the difficulty of problem \(Q\)

So they really aren't different ideas.

But one of the really annoying things about theoretical computer science is that a lot of problems lend themselves to having lower bounds proved about them in a very pretty, abstract way, while the way to show an upper bound is, basically, to write down the actual algorithm that achieves some upper bound on difficulty (again, whatever that word actually means).

Please proceed, Senator

Shorter Mitch McConnell: If Harry Reid makes the Senate a functional body on the matter of Executive and Judicial nominations, I hereby threaten to make the Senate a functional body on all matters, as soon as the American people hand us back the majority in that august deliberative body.

Oddly absent from Reid's response: Please, please don't throw us into that briar patch!

All are hereby instructed to refer to Chris Christie...

... as Taft.0.

The things I miss...

... when out of the country and neck-deep in work. K-Thug:

I feel for Barro; really I do. But he has no home in today’s GOP, which simply has no room for the non-derpy, and to all appearances never will.

and, with much win, Noah Smith:

English has no word for "the constant, repetitive reiteration of strong priors". Yet it is a well-known phenomenon in the world of punditry, debate, and public affairs. On Twitter, we call it "derp".
So "derp" is a unique and useful English word. Let's keep using it.

On reduction

I have a legitimate excuse for being an absent blogfather, I swear. It involves most recently a five-day mathematics conference, and before that at least a week of putting off writing my slides.

In honor of this excuse, however, I think I'll do a post, or maybe more, on some of the ideas that I have bouncing around now. In particular, I'd like to say enough that a dedicated reader (of which I have, I think, precisely zero) could follow two proofs that I really should have known coming into the conference -- though I really can't blame myself, since as far as I know they both only appear in the literature in far more complicated form. Until now, nobody bothered to say "Oh, what's actually going on here is not that complicated, here's the paradigmatic example". Something like Feynmann's hairy handlebodies.

This is, I suppose, what conferences are for: getting free use of a lot of people's bounce-off-the-wall capabilities.

But before I can do that, I have to say a little bit about the mathematical tool being used. Tool? Tools? Eh, who cares. There's one main tool, and one smaller one that is really just a very, very helpful definition; then lastly we'll build a special version of the first tool.

No, Marc Ambinder, spamming me with ads is not the worst thing a private corporation can do to me

So I've been out of the country for a week, i.e. ye olde DVR has a serious backlog of Hayes, Maddow, Kornacki, and MHP. I'll probably delete most of those (though Ms Heelfilcher tells me I would find last Monday's TRMS a good watch), but did get to this Monday's All In yesterday. Since Southern Beale made some good points about a segment on Monday's show, I thought I'd pile on.

Hayes had a panel of three on to talk about surveillance/metadata: Amy Goodman, Karen Finney, and Marc Ambinder. SB:

Marc Ambinder then jumped in with his notion that there’s a big difference between corporations and the government having this information, the worst a corporation can do is send you coupons in the mail, but the government can actually put you in jail. That’s an extraordinarily dumb argument, and Ambinder should know better. First of all, being deluged with advertising messaging is incredibly invasive (I wrote about it here). But also, we live in an era when corporations are polluting our elections with dark money and trying to hide their true agenda behind shadowy groups like Americans For Prosperity and FreedomWorks. So to say the worst thing a corporation can do is send you some unwanted ads is extraordinarily obtuse. They’re trying to undermine our entire democratic process, Ambinder. They’re unraveling the very fabric of our democracy. You goddamn fool.

All of what Southern Beale says here is true, but I don't think it cuts nearly to the heart of the matter.

I leave for other posts the questions of whether it is or should be legal for the feds to demand customer data from companies in the absence of a specific criminal investigation and warrants specifically naming upon probable cause the items to be sought or turned over (short version: probably legal, definitely shouldn't be). Ambinder's position is that since the government holds the monopoly on publicly sanctioned force, the fact that data tracing out individuals' private lives in stunning detail lies in private hands should only be worrisome to the extent that that information is available to the government.

Here are some thought-experiments, Marc: imagine that you are, oh, a journalist. And that you have a story that embarrasses some powerful entity. Now, "powerful" is all relative: if you're one of the 3.5 fulltime employees at the tri-county newspaper, "powerful" doesn't mean the senator or the governor. "Powerful" means the president of the local bank (or regional manager of the national bank). "Powerful" means the biggest employer in the county, whether that's a college, or a car dealership, or Walmart. And writing something embarrassing about whoever that powerful entity is doesn't mean exposing yourself to prosecution or libel suit[1]; the problems you'd face don't for the most part involve the sanctioned use of public force. Instead, do you, like most humans, have any areas in your life you'd rather not have aired publicly? Do you drink more than is considered prudent? Have you recently stepped outside the socially accepted parameters of sexual behavior? Is there anything in your life that a little bit of connectivity analysis could hand your private enemies as a weapon?

And it gets much, much worse if you drop the "journalist" part of the just-so-story I've been telling, because journalists get professional kudos for making powerful people's lives miserable. Regular schmoes, on the other hand... don't. Regular schmoes find themselves fired and unable to find work in their field (if they have a field) or at all (if they do not have specialized skills) when what they do personally or professionally embarrasses the powerful, or cuts into their bottom line.

Seriously, Marc, I know that as a dedicated reader of the internet you have already thought through the difficult question of whether coercion from a private entity can exist, or whether definitionally only the state can coerce, but in case you haven't, we had a whole big symposium on it not that long ago.

TL/DR: Government is not the only one who can do harm, especially assuming access to broad tracking and associational data which only lightly hides information that, in the view of most people, should be stringently access-controlled rather than for sale to all private comers and available for free to the government upon request.

[1] I mean, sure, they might sue you, but at least you'd know you had the law on your side while you're being bankrupted by the costs of the case.