News for hackers. Stuff that matters.
Re:‘We Kill People Based on Metadata’ by j2kun on Saturday May 10, 2014 @11:28PM (#7727639)
It could be because the only people who want to read an article that defines functions and expects them to be familiar with Big-O notation can reach these conclusions without reading the article in the first place.

That being said, it's generally believed to be (or measured) that the social network of the world is a sparse graph. So the fact that the sweep function is quadratic in the degree of a vertex is irrelevant. Using your notation, X is bounded by a constant for all intents and purposes.

In other words, there's nothing inherently bad about the quadratic behavior, and "knowing math" doesn't give you much except perhaps a false sense of intuition. The arithmetic (and your ad-hoc estimates) just works out in favor of your argument. Which is not all that surprising conditioned on the fact that you posted an argument :)

Re:‘We Kill People Based on Metadata’ by msandford on Sunday May 11, 2014 @11:21PM (#7731055)
Sure, I'm not suggesting that the author give it the kind of treatment I did. Simply that the notion "oh two hops is better right?!" isn't valid.

Yes social networks are sparse. With 300 million Americans and the capacity to know perhaps only a few thousand, yes, things will be sparse. But that doesn't mean you cannot construct a spanning tree of that sparse graph. My PC isn't directly connected to Amazon or Netflix or really anyone of interest. But in a couple of dozen hops I'm connected to just about anyone in the world. Sparse doesn't mean unconnected.

The "badness" of the quadratic is that the "two hops" restriction SEEMS like a real restriction when in reality, it's not. It's bad in that the "two" in "two hops" sounds linear but the effects are quadratic. The quadratic-ness isn't inherently bad, I would never argue that. But the deception is.

Re:‘We Kill People Based on Metadata’ by j2kun on Monday May 12, 2014 @10:00AM (#7732688)
I agree that your point is right, these policy makers are douchebags. I just think your analysis is not much more enlightening with the arithmetic. Change 40% to 10% and your final number goes up to over a million. It would be wonderful to have better estimates than "somewhere between 0% and 70%."
Re:‘We Kill People Based on Metadata’ by msandford on Monday May 12, 2014 @10:36AM (#7732903)
Hah you accidentally caught me in a math error!

Sweep(X) = 0.6 * X * 0.6 * X = 0.36 * X^2

I transposed the "percent of overlap" with "percent not overlapped" and viola problems.

If there's a 40% overlap from one person's social network to another that means that 60% of their social graph isn't included in the first person's and thus it's new for the sake of the two-hops strategy.

NumTargets(X,overlap) = 300mm / Sweep(X,overlap) = 300mm / ((1-overlap)*X)^2

NumTargets(100,99%) = 300mm

NumTargets(1000, 99%) = 3mm

NumTargets(100, 5%) = 33241

NumTargets(1000, 5%) = 332

So it's actually even worse then even I initially expected because the reach of the two hops method is doubly-quadratic. It's quadratic in terms of how much overlap there is from one person's social/business network to the next AND it's quadratic in how many connections each person has.

We're piling assumptions on top of assumptions here but lets suppose that at least 100k is the minimum number of targets we're comfortable with the NSA having to snoop on before they get everyone's data. It's not the right number but it's illustrative.

According to the spreadsheet I just put together we can satisfy this in a number of ways:

overlap = 99%, X just about all realistic numbers

overlap = 90%, X ~ 600 or less

overlap = 80%, X ~ 280 or less

overlap = 60%, X ~ 120 or less

overlap = 40%, X ~ 90 or less

overlap = 20%, X ~ 70 or less

overlap = 5%, X ~ 60 or less

There's no region that's got clearly reasonable assumptions where the NSA can't with a little bit of work get all the call records on all Americans again.

In other words, if it took overlap = 5% and X = 20,000 (to me not that realistic) in order to make it "easy" for the NSA to collect everyone's call records I might be less incensed. But the way this scales there's no reasonable assumptions that make it incredibly difficult for the NSA to vacuum up data on everyone.