Lance Fortnow's Blog, page 118

P vs NP is Elementary? No-- P vs NP is ON Elementary

As I am sure you all know, the TV show Elementary  (Premise- Sherlock Homes in Modern Day NY. He emails and Texts!  Watson is a female! and...) had an episode that involved P vs NP in a big way. I think they would have been better off with a fictional problem (Bourbaki's conjecture in Recursive Algebraic Topology?) rather than a real problem that they could say rather odd things about.


Sherlock Holmes doesn't know what the Mill. Prizes are. I thought most educated people did. Everyone I know knows about them. Could be the company I keep.
The show indicates that `Solving P vs NP' means `showing P=NP' It never seems to dawn on them that maybe P is NOT NP.  
The show  assumes that once P=NP is proven it will take a very short time to write a program to  use it.  If P=NP is true then I suspect taking the proof and making it work on real world problems would take several years.
The show focuses on P=NP's implications for crypto. As Lance has pointed out in his book if P=NP then the benefits for society are GINORMOUS, and would dwarf the relatively minor problem of having to switch to private key  (I agree with Lance for the long term, but I think the short term would be chaotic for security).
The show refers to seven Mill problems. While this is technically correct they really should mention that one of them (Poincare's conj.) was already solved. 
They seem to think that algebraic geom would be used on P vs NP. If they were claiming it was being use to prove P NE NP then I would think of the Geometric Complexity Theory Program and be impressed. Since they were using it to work on P=NP I'm less impressed. If Alg Geom really is used to prove P=NP then I'll be impressed.
How was the episode- I am a fan of the show in general, and this was a solid but not outstanding episode. I wonder if I knew less about P vs NP would I enjoy it more.
They are talking about P vs NP on National TV! That's kind-of nice. Only danger is the overhype. If  P NE NP is shown and this has no real world applications then the public may be confused.  I suspect we won't have to worry about that for at least 300 years.

Celebrating Maths in Oxford

This week I'm in Oxford for the opening of the new Andrew Wiles Mathematical Institute building and the Clay Research Conference including on workshop on New Insights on Computational Intractability.



The building is beautiful with two small towers, one each for pure and applied math, and a common room joining them. The downstairs, where the talks are being held, is separated from the tower by its own glass dome, so, I was told, that the noise of the students don't disturb the great thinkers above.



The Clay Math Institute, best known in our circles for the millenium prize problems, has moved to Oxford from Cambridge (Massachusetts) and will take up residence in this new building. Unlike Jim Simons, Landon Clay didn't have a particular math background but was looking for a purpose for a charitable foundation. He met Andrew Wiles and loved the story of his proof of Fermat's last theorem and Clay realized the need for basic math research. Besides the millenium problems, the institute sponsors a number of research fellows and the move to Oxford reflects a transition to funding American mathematicians to a more international base.



What about the new insights into intractability? Lots of great talks on connections to physics and economics, on proof complexity, information theory, algebraic and circuit complexity. On the other hand I watched some talks on other millenium prizes and while difficult to follow, it looks like they have measured progress towards resolving their problems. In complexity, we're still searching for that true path towards P ≠ NP.

Long Tails and Fat Heads

Sometimes words or phrases are used in MATH and then spread to the REAL WORLD. I have blogged about how the terms Prisoner's Dilemma has become a real-world-phrase here and speculated about the terms Venn Diagram, Zeno's Paradox, and n+1 here.



I recently came across a pair of words that are related--- one of them seems to be (like Prisoner's Dilemma) going from MATH to THE REAL WORLD. The other one is very odd in that I've seen it in the REAL WORLD but it SHOULD be in MATH.



Long Tail: A Probability distribution has a long tail if there are MANY items that have a SMALL but NON-ZERO prob of happening. This is a term in probability. However, I have seen it used in the REAL WORLD as in Amazon has a long-tail strategy meaning that they will sell LOTS of DIFFERENT things even if the number of people buying some of them is small (like this which is ranked 9,578,520- though I doubt they can be that precise). This article from the Atlantic Monthly points out that ESPN used to have a long tail strategy (e.g., showing Billiards and others sports that are not that popular, but ALOT of them) but then abandoned it for... see next definition. Note that the term Long Tail is used for both a type of Prob Dist and a marketing strategy related to it. How common a word is Long Tail? It gets 66,500,000 hits on Google. The first page has the definition above only. The 10th page had about half of the hits with the def above.



Fat Head: A strategy where you concentrate on just a few items. ESPN is doing that by covering just a few sports, but the most-watched ones (too bad, I was hoping they would cover my favorite sport, chess boxing). This SHOULD be a math term for a Prob Dist with just a few points of high prob. I asked my friends in the ML community and he assures me that NO its not a math term--- but it SHOULD be! How common a word is this? It gets 2,300,000 hits on Google. The first page seems to have NOT have ANY reference to the definition above.



SO- this COULD be a case where a term used in the REAL WORLD migrates to MATH with essentiallythe same meaning. This isn't that uncommon (the term Continuity comes to mind) but this timeI will have predicted it! Maybe I should do Machine Learning.

Complexity and FOCS

The Conference on Computational Complexity Call for Papers is out, deadline November 27.



The deadline for early registration and hotel for the FOCS conference in Berkeley is October 4. Student travel support is available.

Dealing with Death

Mary Jean Harrold, a professor of software engineering at Georgia Tech, passed away last week. Mary Jean was 67 and still quite active before the cancer struck.



Computer science is still a relatively young field and most of even the early computer scientists remain quite alive. So a death in the field, particularly a colleague, makes a mark because it typically is happening at a young age. I've lost five co-authors (Avner Magen, Steve Mahaney, Andrej Muchnik, Nick Reingold, Carl Smith) all well before their time. Each death is a stark reminder of what's important in life, what does the next theorem mean when life seems so short?



We're nearing a time in computer science that many of our ranks will die after living to a ripe old age. Those remembrances will be of a life well lived. But there will always be lives cut short. The best we can do is remember them and move on and continue to build on the research tradition they left behind.

Crystal Math- What NUMB3RS and BREAKING BAD both get wrong

The TV show Numb3rs  had as a premise that a GENIUS mathematician

could help solve crimes. Is this true? I rather doubt you need a GENIUS-

though of course some prob, state, data mining,  the math behind forensics, and a few other things help. And it may help to know some number theory if a mathematician who is working on the Reimann hypothesis has his daughter kidnapped.  But I don't think you need someone on the level of Charles Eppes.



The TV show Breaking Bad  (see Honest Trailor for Breaking Bad and/or

Idiots Guide to Breaking Bad if you've seen the first 4.5 seaons at least)

has as a premise that a GENIUS chemist can make really good crystal meth. And as a by product it's blue. I know nothing about the crystal meth business; however a chemist friend of mine (who has never made the stuff) tells me that YES, being a careful chemist is good, and certainly better than a meth-head who is more likely to blow up his lab than to produce any, a GENIUS chemist would not be any better than a good chemist.



The TV show Elementary  (Sherlock Holmes in modern day New York) and many other shows (Monk, Perception, Psyche, The Mentalist, Columbo, and others I am sure) has as a premise that a GENIUS observer could help solve crimes. This may be more true then the above, but there are other tools available today (e.g., DNA).



All of these shows, and others, make the  FALLACY OF EXTRAPOLATION. Taking a good idea and extrapolating it to absurdity.



Here is a non-TV example: If blogging is part of my job, and I can deduct job expenses for Tax purposes, then I should be able to deduct the cost of the DVD's for Numb3rs that I bought because of this post.

STOC CFP still delayed- but I was asked to pass this along

Since there were comments on the blog about the STOC and CCC CFP not being out yet I mailed various people who are in-the-know. I got email from David Shmoys  (STOC PC chair 2014) telling me

(1)  The  STOC the call is still delayed,

(2)  There is a website about it, here, that is INCORRECT - the REAL deadline for submission will be Nov 11, 2013 (4PM east coast time.)

(3) Please post this correction on complexity blog.

(So I just did.)



Note that Lance and I are NOT involved with the organization of STOC or CCC. The blog entry is just passing along information.

tl;dr

Every now and then we need new words and phrases come into our lexicon, like the unfortunate "twerking", but here's another "tl;dr", short for "too long; didn't read". I'm guessing it started as an insult/excuse not to read a long document, blog post or email. Respond "tl;dr" and you've put the blame on the writer for being too loquacious to the tweet-friendly generation.



Now I see tl;dr used as a short synopsis sometimes by the author themselves, the new executive summary if the executive has six seconds to read. Maybe I should tl;dr my class lectures: "Finite Automata: Easy to analyze but too weak to do much interesting".



Are we really moving to this brave new world of micro-attention spans? Is this just another reason that newspapers are dying and blogs are passé? When I write email should I keep it short and be misunderstood, make it long and have it not be read or add a tl;dr summary and get the worst of both worlds?

Did YOU think the NSA could factor fast?

Before the recent revelations about the NSA (see Lances Post and Scott's post )I would tell my class, when teaching P and NP,

We have very good reasons to think that Factoring is NOT NP-complete. As for P--- much murkier. People have tried to get it into P because of crypto and have not succeeded, hence many people think that Factoring is NOT in P. But there is so much math there that perhaps could be exploited to show it IS in P. Another very odd possibility is that it is KNOWN to be in P but only by the NSA. Crytpo has had this before- where some concepts were known to governments before they were known to the public,  even the academic public.

I will need to revise that now. BEFORE the recent revelations there were

the following points of view on factoring:


The NSA cannot factor any better than what is known in the literature. Maybe a bit better because they use more parallelism.
The NSA has taken the known algorithms and found the right parameters and has special purpose hardware so can do them better than anyone else, but nothing of interest mathematically. Perhaps some very interesting subtle points of math and hardware. What they have would not get into STOC/FOCS/CRYPTO (though maybe it should- that's another debate). This is the one I believed.
The NSA has an algorithm that is better than the literature (e.g., exponential in (log n)^{1/5}).  But not in P. This would surely get into STOC/FOCS/CRYPTO and win a prize.
The NSA has factoring in P through some very interesting and new mathematics. If this was public then perhaps a Turing Award.  Some serious number theorists do think that Factoring IS in P, so this one is not quite so implausible.
The NSA has a quantum computer that factors quickly. I do not now of anyone serious who believed this. Of course, this could be a case of the No True Scotsman Paradox--- if someone really believed this I would (perhaps unfairly) declare them non-serious.
The NSA does not have a better algorithm, but has managed to put trapdoors in stuff so that they and only they could break certain codes.(A covert version of Clipper Chip.) So they can break codes but not in a way that is interesting mathematically.



There may be more but I don't know them off hand. Item 6 I never heard people say, though that might be a function of the company I keep. I do not know what the most common view was, but I would guess item 2.This reminds me of  Karmarkar's Algorithm which I've heard runs fast because of the implementation- the algorithm is not a secret but exactly how they implement it is. (Note- just because I've heard this does not mean it's true.)



The truth seems to be that the truth is between 1 and 2, closer to 1, and also item 6.

In particular, the NSA does not seem that much ahead of academics.



In the past governments were way  ahead of academics in crypto. This no longer seems to be the case (at least in America). I speculate that this is because there is now a large community  of people doing research in crypto openly, publishing openly, so the government is no longer the only (or almost the only) game in town. Also, many non-government industries use crypto and some do research in it. This also helps the NSA- they can use results in the open literature, but they can't get that much ahead of it.



Are there other fields where the government is ahead of academics and industry? On a guess stuff with weapons and weapon detection, since not many academics work on that. Maybe sociology since the government has  census data and other data that is not available to the public.

Cryptography and the NSA

Back at Northwestern I occasionally taught an undergraduate cryptography class since I was the local expert in the field (a statement not even remotely true at Georgia Tech). I would cover the Advanced Encryption Standard, an implementation of a one-way key-based permutation. AES had many components included an S-Box that seems like a random shuffle but is actually based on the inverse of a polynomial. One sentence in the textbook of Trappe and Washington made the following point (page 161).

The S-box was constructed in an explicit and simple algebraic way so as to avoid any suspicions of trapdoors built into the algorithm. 

Really? Can't we trust the government not to put back doors into our standardized cryptographic algorithms?



After reading last week's New York Times article on the NSA, I realize my naivety. The NYT article doesn't go into how and which protocols the NSA has their hand in but I now understand the concern.



It doesn't look like the NSA has actually broken cryptographic protocols, have a secret quantum-like computer in their basement or polynomial-time algorithms for SAT. I could go on for pages but Scott has done an excellent job talking about the complexity issues involved. They've more likely found ways to access your information before it has been encrypted or after its been decrypted.



Matthew Green wrote a nice post speculating on what the NSA might be able to do, so nice that it caused some controversy at Johns Hopkins.



The whole Snowden affair gives us a glimpse into the NSA but they hide their capabilities well and we'll never know the full extent of their knowledge.