Monthly Archives: August 2010

Link on paper on profiling/importance sampling in context of screening for terrorists

Posted on by

Mainly storing a link to this interesting paper that raises some questions:

William Press, "Strong profiling is not mathematically optimal for discovering rare malfeasors".  Weak profiling apparently is---under the assumptions of his model, which seem to me a rather imperfect fit, but not wholly irrelevant, to most real-world terrorist-screening scenarios.   No implied view from me on the correctness or relevance of these results, pending more careful reading and thought.

Aha, just realized it's that Bill Press--former (pre-2004) deputy director for Science and Technology at LANL (curently at UT Austin, on leave from LANL).

Oh yeah, link is from The Yorkshire Ranter, who got it from Bruce Schneier.

Breadth and depth

Posted on by

Nice point by Seth Godin on how to see if someone really knows what they're talking about.  I see it in my field too---people judging by the extent to which one can carry on an extemporaneous conversation about the subject at hand, revealing months of thought about the topic at hand, years of study of the background issues.  On the other hand, we also need --- sorely, and in my opinion, even in technical fields --- people with breadth---non-superficial breadth, to be sure.  How does one spot that?

Links: on Fed decision not to shrink its balance sheet; to Dallas Fed President Richard Fisher's recent speech. Rant: on the latter.

Posted on by

Jon Hilsenrath article on the Fed's deliberations over the recent decision not to let its balance sheet shrink.

No time now to do a detailed analysis of FOMC member and Dallas Fed president Richard Fisher's speech, which is posted on the Dallas Fed website, though containing the disclaimer "The views expressed by the author do not necessarily reflect official positions of the Federal Reserve System."  Of course there is something in the idea that regulatory and other policy uncertainty can have an inhibiting effect on business investment, but I really, really do not think that is much of what is going on with the recovery here.  Fisher's speech looks to me---after a couple of readings, but not a thorough analysis---like he is peddling the current Republican line on why the economy isn't recovering better, and I think this line is ludicrous.  Yeah, I think the length of the financial reform bill is maybe an issue (but you could probably say this about any serious policy legislation these days, and probably could have said it when the economy was booming,  e.g. during the Clinton presidency).  Business and banks have loads of bigger worries right now than uncertainty over policy reform or future deficits.  Like uncertainty about, and low expectations for, near-term demand for their products.   Fisher worries that the regulatory discretion being given to the Fed creates uncertainty;  you might hope some of the length of the bill is caused by trying to specify things enough to remove some of this uncertainty, and for the rest---well, there isn't really any substitute for well-excecuted regulation in some matters.  Ludicrous to think *this* is the issue in the protraction of the current slump. First mention, though is given to "Fiscal Policy Uncertainty".  Fisher:

By latest accounts, under the least felicitous conditions (what the Congressional Budget Office recently called an “alternative fiscal scenario”), publicly held debt bests the all-time high of 109 percent of GDP around 2025 and reaches a staggering 185 percent of GDP by 2035—more than twice the level of debt at which some economists believe significant crowding-out of private-sector economic activity occurs. This is not the baseline scenario. But the possibility of it occurring, however remote, frightens business operators, for they are uncertain not only about whether fiscal authorities will actually mitigate this risk, but also how they might go about doing so.

Okay, the mechanism of crowding-out in that remote eventuality will be higher interest rates on corporate borrowing, caused by government borrowing having driven up interest rates more generally; but we hardly see the markets anticipating that in long-term government bond rates.   It's true Fisher prefaces this with "Let me turn to what I hear from businesses, the players on the field."  And it's true local Fed branches try to keep in touch with local economic reality, including business sentiment.  But it seems to me pretty likely you might hear many businesspeople, especially right-leaning ones (of which there are a few, I think) parroting whatever blame-the-government line the right-wing media feeds them, and one would hope that a local Fed president would do more, even in a speech to the local business community, than parrot that back.

The issue is uncertainty about --- and perhaps even more, pessimistic expectations about--- demand over the next few years.

When Fisher says:

our political leaders should muster the courage to pull up their socks and strike a better balance between the long-term need to keep government debt low and the short- to medium-term need for an appropriate level of fiscal stimulus.

could this mean he's realizing the need for a higher level of short-term fiscal stimulus, combined with assurances (which the bond markets seem to believe they have) that potential long-term deficit problems will be dealt with soon enough?  Somehow, I don't think so.  The fact that the phrasing is ambigous enough to permit this among other interpretations seems to me to stem from the need to restrain himself, just a bit, from seeming too nakedly partisan, or perhaps just too prescriptive, but the Greater San Antonio Chamber of Commerce can probably read the lightly-coded message just fine, and it ain't that we need more stimulus.

Uncertainty about whether the Bush tax cuts will be continued is cited as another biggie holding back the economy.  Again, somehow I don't think the message is "kill 'em now, so we can stop worrying about what will happen and invest".  Or even "kill 'em now, so we can worry less about future deficits and invest."  I do believe tax cuts can provide fiscal stimulus, and ones targeted at lower income brackets can probably provide more; because the highest income taxpayers have a higher marginal propensity to save, tax cuts primarily benefiting them are one of the least effective fiscal instruments for boosting aggregate demand, and let me say it again, we are in a primarily aggregate-demand-limited situation here.

More than I intended on Fisher; not a full analysis, since I haven't dealt with his comments on the main Fed bailiwick, monetary policy.  But overall: either some decent but in my opinion not central to the current situation, observations on policy uncertainty, plus some mush; or worrisome code for some dubious partisan points.

Claimed proof of P not equal to NP by Vinay Deolalikar is being taken seriously

Posted on by

Via Richard Lipton, news that HP research scientist Vinay Deolalikar has put online a 102 page draft of a paper purporting to prove that P is not equal to NP.  (Follow the link to Deolalikar's page, and the paper is the first one linked under "Selected Publications".)  It is being taken seriously by serious people  (like Lipton)--- in the sense that they are trying to understand it and understand whether or not it is correct.   The length, of course, increases the likelihood of a so-far unspotted error.  Lipton thinks Deolalikar's use of finite model theory is an interesting and promising twist.  I have only just downloaded the paper, and am not a complexity theory expert, but what leaps out at me from the abstract is that it involves graphical models for sets of interacting random variables, an area that interests me.  Not that surprising, I guess, as lots of difficult problems---as well as ones that are easy but perhaps not obviously so, because of structure described by a graphical model of the dependencies between variables---are naturally described in graphical terms, and the relation between graphical models and complexity is a well-studied---though mostly relatively recently studied---topic.  I can no longer find the link to the online draft of Marc Mezard and Andrea Montanari's book on the subject (and its relations to physics and coding theory), perhaps because it's been published.  [Correction:  it's still online here.   Thanks to commenter Kristal Cantwell for the link.]  One key notion in such models is conditional independence---independence of two subsets of the random variables in question, when conditioned on a third set.  A really nice paper on a quantum notion of conditional independence, relating it to the equality conditions for the strong subadditivity inequality for quantum entropy, is by Hayden, Jozsa, Petz, and Winter.  Matt Leifer and David Poulin, and others, have described quantum graphical models.

You can bet that if Deolalikar's proof looks good, a slew of people will be applying the research strategy I like to call the "quantization functor" to it.

For those for whom P and NP are not their bread and butter, to give you an idea of how big this would be: I just goofed by telling my wife that if this pans out, it will be one of the most important results of twentieth century mathematics.  Well, it would have been if done in the twentieth century.  But I'll say more: although we're only 10 years in, I think it will be one of the most important results of twenty-first century mathematics.  I haven't said what it really means but that's what Wikipedia is for.

I should point out that Scott Aaronson is dubious, though not based on close perusal of the proof.  He has pledged to personally supplement the million dollars the Clay Mathematics Institute will pay Deolalikar if the proof is correct, with two hundred grand of his own.