Sunday Morning Insight: Watching P vs NP

Last year, I somehow argued that it would be difficult for Quantum Computing to compete with the Steamrollers even if it meant they could solve NP problems (which we don't really know if they can [6]). This time, it is a little different. See, if you recall, sharp phase transitions are now part of our landscape. By landscape, I do not only mean their discovery [3], but also their use starting with [1] in 2010 and as recently as last week [4]. We collectively yearn for those limits to move (see The Wall in Sunday Morning Insight: Game of Thrones and the History of Compressive Sensing [5]

From Manjhi's Myth

And like we said last week [2]

"...yes, we expect the mathematicians to clear the waters there..."

or like in the case of Manjhi, move a mountain.

Go read Tim Gowers' What I did in my summer holidays on TiddlySpace and his proposal for Polymath9 and Terry Tao's G+ post on Gilles Pisier's paper on Grothendieck's Theorem, past and present [7] (a more recent version of that paper is here) set up on the SelectedPapers network. 

It might happen right in front of our eyes.

[1] Compressive Radar Imaging Using White Stochastic Waveforms by Mahesh C. Shastry, Ram M. Narayanan and Muralidhar Rangaswamy [Published in 2010]

[2] Implementation: EM-NN-AMP: Recovering Linearly-Constrained Non-Negative Sparse Signals

[3] Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing by Jared Tanner and David Donoho

[4] Compressed sensing and genomes and on Nuit Blanche ( Application of compressed sensing to genome wide association studies and genomic selection )

[5] Sunday Morning Insight: Game of Thrones and the History of Compressive Sensing

[6] Randomized Thoughts and Around the Blogs in 78 hours

[7] Grothendieck's Theorem, past and present by Gilles Pisier

Probably the most famous of Grothendieck's contributions to Banach space theory is the result that he himself described as "the fundamental theorem in the metric theory of tensor products". That is now commonly referred to as "Grothendieck's theorem" (GT in short), or sometimes as "Grothendieck's inequality". This had a major impact first in Banach space theory (roughly after 1968), then, later on, in $C^*$-algebra theory, (roughly after 1978). More recently, in this millennium, a new version of GT has been successfully developed in the framework of "operator spaces" or non-commutative Banach spaces. In addition, GT independently surfaced in several quite unrelated fields:\ in connection with Bell's inequality in quantum mechanics, in graph theory where the Grothendieck constant of a graph has been introduced and in computer science where the Grothendieck inequality is invoked to replace certain NP hard problems by others that can be treated by "semidefinite programming" and hence solved in polynomial time. In this expository paper, we present a review of all these topics, starting from the original GT. We concentrate on the more recent developments and merely outline those of the first Banach space period since detailed accounts of that are already available, for instance the author's 1986 CBMS notes.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.