Author Archives: howard

About howard

Wine, Physics and Song is my blog. Roughly speaking, I'm a quantum physicist, working mostly in the foundations of quantum theory, and in quantum computation and quantum information processing. My main focus recently has been understanding the nature of quantum theory by understanding how the possibilities it gives us for processing information compare to what might have been, by studying information processing in abstract mathematical frameworks, using tools like ordered linear spaces and category theory, in which not only quantum and classical theories, but all sorts of "foil" theories that don't seem to be realized in our physical world, but are illuminating to contrast with quantum theory, can be formulated. Sometimes I like to call this pursuit "mathematical science fiction".

Consensus on Deolalikar's P vs. NP proof-attempt (via Scott Aaronson)

Posted on by

Haven't been blogging much recently, but I certainly need to post this link on Deolalikar's claimed proof of P ? NP:  Scott Aaronson saying (nearly a month ago) that a consensus has developed that it's fatally flawed.  Scott's post is worth reading in part as a preliminary guide to what you'd need to learn about to really tackle this problem---and what to do to increase your --- and others' --- confidence you'd actually solved it.

I think I already linked Richard Lipton's less conclusive "Fatal Flaws...?" post.   Lipton wrote another good post a few days later (a week after the proof was posted).  These lack a definitive statement that "it's dead" (one section is labeled "it ain't over till it's over".  Scott seems to have concluded on the basis of most of the same evidence that it was almost certainly over.  The fact that googling "Deolalikar proof" turns up nothing later than Aug. 12 on the first page (I see a broken link from Aug. 18 on the second page) also suggests it's dead.

A weak link from Greg Mankiw on whether to extend the Bush tax cuts

Posted on by

Harvard economist Greg Mankiw says it "might be worth remembering" that 70% of economists who expressed an opinion in a Wall Street Journal poll last month thought that all the Bush tax cuts should be extended, 24% thought they should for households making under $250,000/year, 6% said they should all be allowed to expire.  Of rightish-leaning economists, Mankiw is one whose thoughts are often worth reading, but I'd much rather hear what he thinks on the issue (I suspect he's with the 70%) and why, than what 48 of 53 economists chosen by the right-leaning WSJ have to say.  I have three main points: (1) the Journal quotes four respondents by name---they are from Northern Trust, Standard & Poors, Perna Associates, and Pierpont Securities.  In other words, this is not a poll of academic economists, but of economists working for financial firms.  Maybe they're good at forecasting, maybe not.  I care more what people like Mankiw himself, Paul Krugman, Joe Stiglitz, Robert Barro, Barry Eichengreen, Thomas Sargent, Christina Romer, Laura Tyson, etc... think on these issues.  (2) It's not clear what the basis for the judgment is supposed to be---it thus likely mixes their values regarding inequality, taxes, etc... with issues of the economic effects of tax policy. (3) Much discussion currently centers around whether or not the cuts should be made permanent.  "Extended" is a very different thing; many would support extensions while we are still in a slump, but not necessarily permanent ones.  For example, I'd support (along with Obama and virtually everyone else) an extension for people making under $250,000 a year as providing fiscal stimulus (though government spending, especially direct aid to states and municipalities, would be more effective), but not necessarily a permanent extension for everyone in this group,

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.

Music of the 90's and 00's: Joe Strummer, Black Grape

Posted on by

Recently read Chris Salewicz' biography of Joe Strummer (titled "Redemption Song").  Good read.  Long swathes of quotes from Strummer's friends, family, and acquaintances are often illuminating, sometimes repetitive.  Interesting to have different people's perspectives, and insights.  In some ways, this gives a real "you are there" feel of how things really were that would be hard to get out of a more conventionally discursive authorial biography.  On the other hand, this also means that one doesn't get quite as coherent an image of how the man did what he did, and one is left with unanswered questions about, and contradictory perspectives on, some matters.  in some ways, a biography in which the author took more of a position, made clearer statements about the subject, might be more satisfying.  Or maybe just an easier read.  This biography makes you think about who this really was, and what his impact was on the people in his life---clearly intense, as was his impact on our culture and music.  And the choice to write it this way avoids the possibility of presenting a partly-false picture of Strummer as told by the author to himself.

I like to read biographies of artists to see how it's done, how it happens.  And yes, I'll admit that this is in part because I wonder if I can use these lessons to help me do something great, or at least satisfying.  My only real complaint about the book is that analysis of the music and especially, how it was made and the musical interaction between Strummer and the other Clash members, especially Mick Jones, is somewhat, though not totally, lacking.  It's clear Strummer and Jones needed each other artistically, were a fantastically synergetic combination, and it also seems clear that Strummer's decision to "fire" Jones, breaking up the Clash, deprived us of some fantastic music they still could have made.

Listening to the posthumous "Streetcore" by Joe Strummer and the Mescaleros, mixed by Martin Slattery and Scott Shields in part from guide vocals by Strummer and preliminary tracks.  Really excellent, even so.  Perhaps because some of the vocals weren't necessarily intended as the final versions, Strummer sounds relaxed, to good effect, but still reminiscent of the more discursive, rambling, poetic Clash lyrics at times.  "Coma girl" and "Arms Aloft" feature the kind of 16/8 or 8/8 even guitar chinking out the same chord that is almost an alt.cliche by this point (see Snow Patrol...)... but nice stuff.  Arms Aloft goes into a more bouncy guitar-rock chorus on "..arms aloft in Aberdeen".  No wonder I like this bit... I now realize that this is a close relative to the riff to which the Kinks set the words "I believe that you and me..." [last forever] in "All Day and All of the Night", i.e. one of the catchiest, most insistent guitar riffs of all time.  That in itself is a lesson about how musical creation can work---you don't necessarily need to be afraid when bits of something else find their way, perhaps transmuted, into your work...it happens to everyone, including the best of the best.  Of  course, "Arms Aloft" is no "All Day...", but it's nice, the Kinksy bit is tucked into the song naturally and the song doesn't sound like (and isn't) a Kinks ripoff at all.  Get Down Moses is an excellent reggae-drenched song; "Long Shadow" is like Neil Young and Leonard Cohen channeled through Joe.  Midnight Jam, mellow almost psychedelic, slowly swinging guitar-jam (the main hook reminiscent of a particular song from Jefferson Airplane's "Surrealistic Pillow", with a little dub influence on the vocals.  Silver and Gold is Joe doing an acoustic version of what sounds like a classic country/cowby song.  Nice closer.  Must check out his other albums with this configuration, I guess (there are two).

Another late-career Strummer endeavor was his collaboration with the sui generis kick-out-the-jams rave/soul/house/funk/jam band Black Grape (formed from crucial remnants Shaun Ryder and Bez of the Happy Mondays).  Typified by their hit single for the Euro 96 football tournament, the freaky anthem England's Irie, here live at Top of the Pops (Strummer's first appearance there; the Clash promised never to play the show).

Black Grape's first of two albums, It's Great to be Straight, Yeah! is weird but very good in a loose and slightly cheesy way.  Every track seems to be on Youtube.  Not-quite-randomly dipping into the craziness (warning, expect profanity and irreverence, and even (gasp!) bad taste), here's In the Name of the Father.  Prime candidate for any list of Top Ten Songs with Sitar Intro.  Another top track, the reggae-and-soul tinged Shake Your Money.  The Grapes take on a late 60's/early 70's guitar-jam kind of riff in Submarine (with allusions to A Day in the Life).   (If you can figure out what they mean when they sing "and the boy was so proud / of the crocodile on his sock / someone had to tell him / it was planet Reebok", you're thinking too hard.)  One of their better B-sides is Straight out of Trumpton.  But doesn't compare to It's a Big Day in the North... as near as they get to mellow, Balearic-isles house, a genre that I don't listen to much, but that I'm not surprised is improved by convex combination with something like the Grape's hyper-energetic punk/funk craziness.

Nice post by Brad DeLong on the Fed, Bernie Sanders, and Obama

Posted on by

Excellent post, that I agree with, by Brad DeLong on the Fed, Bernie Sanders' amendment to the Dodd financial regulation bill, calling for regular GAO audits of the Feds deliberations and communications related to setting and implementing, and transactions implementing, monetary policy.

Delong writes "...I am willing to defer to President Obama's judgment that the Federal Reserve's desire for a modicum of central banker privilege is worth respecting, and that the Sanders amendment is the wrong treatment for the disease. I am willing to do so, in large part, because I think the problems are not those that detailed routine investigations of staff communications would solve: the staff of the Federal Reserve do, it seems to me, overwhelmingly have a reality-based vision of the economy, conduct thorough and appropriate analyses of risks and scenarios, and understand the Federal Reserve's dual mandate."

The problem according to Brad is rather that "I do not think that the dominant views of monetary policy in the FOMC right now are informed by American values and a reality-based assessment of the state of the economy.  [...] a good many of the people speaking and voting in the FOMC are the wrong people".

And Obama hasn't done enough to fix this, with five of the seven seats on the Fed's Board of Governors that have opened up while he's been president still unfilled (and one filled by reappointing Ben Bernanke, a decent centrist choice who Brad thinks shouldn't be the left wing of the FOMC at this point.

Too much conventional supposedly-conservative "wisdom", in other words, too much coziness with financial institutions and, I guess, too much worry about inflation even in the depths of recession, from this Fed Board.

Weighing on the other side of the Sanders amendment issue, perhaps, is this via Paul Krugman.

Good recent quantum information, computation, foundations talks

Posted on by

I must store some references to good recent talks, in part so I don't forget them:

Two talks by Tsuyoshi Ito:  an IQC theory lunch talk about how the complexity class defined by interactive proof systems with two provers who may share *arbitrary non-signaling correlations* (rather than just quantum ones) with each other, turns out to be PSPACE.  Communication between verifier and provers is classical.  This is the same class as that defined by quantum interactive proof systems (for any fixed number of provers, but *without* shared correlations, quantum or otherwise)---a result due (at least the hard direction, that PSPACE is contained in QIP) to Jain, Ji, Upadhyay, and Watrous).  Very nice stuff.  (Note that as far as I know it doesn't imply that two-prover proof systems with classical communication between verifier and provers, but verifiers sharing quantum entanglement, is in PSPACE.  Although this latter model gives the verifiers, collectively, strictly less power, the reduction in their collective power could increase the power of the proof system:  crudely speaking, the provers might have less power to attempt to coordinate in bamboozling the verifier into wrongly accepting.

The really kooky, like me, might ask, what if we allow the communication between verifiers and provers to involve exchanging the kinds of systems involved in the provers' shared non-signaling correlations.  "Popescu-Rohrlich bits", or generalizations involving larger numbers of outcomes per measurement, and larger numbers of measurements.  (States of "semiclassical test spaces", in a different lingo.)

Tsuyoshi's other talk was an informal one at the quantum information group meeting at PI, about XOR games with more than two players.  More on it later.

A few weeks ago Stephanie Wehner gave us a lovely informal quantum foundations seminar on a recent paper she wrote with Jonathan Oppenheim, whose thesis is that if quantum theory were more nonlocal it would violate uncertainty relations.  The uncertainty relations involved are a new type she (and Andreas Winter?) introduced, called "finegrained uncertainty relations".  I'll try to summarize this talk in a later post, too.