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.

If you want to see various important (so people are already working on them) problems in math solved, and you have LOTS of money, what is more effective:

ReplyDelete(1) Prize money, or (2) sponsoring workshops, or (3) funding grad students, (4) funding professors, (5) funding others (HS students, Ugrads).

Prize money gets the problems out there and is good for the very long term.

(Many more kindergardeners know about the Hodge Conjecture because of the

Mil prizes.) All the ways to spend the money are good, though I would try to make

the grants easy to apply for. Whats better? I would guess you need all of the above.

Other fields seem to make progress while P vs NP remains unsolved. Oh well.

Great post and an exciting event! Are there videos from the talks?

ReplyDeletePer the

ReplyDeleteProceedings of SAT Competition 2013:------------

PREFACE: The area of Boolean satisfiability (SAT) solving has seen tremendous progress over the last years. Many problems (e.g., in hardware and software verification) that seemed to be completely out of reach a decade ago can now be handled routinely.

------------

If we adopt a pragmatical/engineering perspective,then the key question in complexity theory is not "How can we rigorously decide PvNP?" (or alternatively, show that this question is undecidable for oracle-decided complexity-class membership), but rather "For how many years/decades/generations will solvers & simulators continue to demonstrate Moore's Law improvements in capability"?

In this regard, please let me commend Scott Aaronson's just-opened question on

TCS StackExchangeOverarching reasons why problems are in P or BPP.Better answers to Scott's implicit question would help substantially in foreseeing means for sustaining (and even accelerating?) the present-day burgeoning of solver & simulator capabilities.Also recommended is the ongoing discussion of the complexity of BosonSampling simulation & verification that Scott has been

hosting onRecent BosonSampling investigations extend and deepen the much-discussed complexity theory question that Scott introducedShtetl Optimized.Are Quantum States Exponentially Long Vectors?(2005):--------------

QWhat criterion separates the quantum states we’re sure we can prepare, from the states that arise in Shor’s factoring algorithm?I call such a criterion a “Sure/Shor separator.”

--------------

Nowadays it is natural to replace in Scott's question "Shor’s factoring algorithm" with "BosonSampling experiments". As an aside, the sardonic temptation to similarly replace “Sure/Shor separator states" with "Sure/BS separator states" should (as it seems to me) be adamantly resisted, if only because these lines of investigation have substantial implications for lines of medical research in which the utmost feasible rapidity of progress is desirable; progress that sardonic rhetoric serves only to impede.

With broader regard to the crucial role of both complexity theory and systems engineering in enabling new 21st century enterprises, more valuable than a working/scalable BosonSampling experiment, and more valuable even a working/scalable quantum computer, would be working/scalable techniques for simulating verification-passing BosonSampling datasets (and many other real-world quantum dynamical systems) with resources in P.

ConclusionIt is well to keep in mindGeorge Dantzig's maxim:"In brief, one's intuition in higher dimensional space is not worth a damn!"HUGE APPRECIATION to landon clay re his decision to fund mathematics and the P vs NP problem prize in particular. [I too was inspired by wiles and had toyed with FLT significantly prior to the proof.] green with envy at the historic meeting of minds going on. is it being videotaped? if not, maybe the next one?

ReplyDelete"In complexity, we're still searching for that true path towards P ≠ NP."

I would argue "we" have made major progress toward P vs NP but the community is highly self-critical, but also diffuse and unable to coalesce around certain promising directions...

Elementary today one-upped Numb3rs with the Season 2 episode 2 Solve for X which has P vs NP as a fundamental piece of the plot. They even explain the problem well, though confuse its solution with proving P=NP, whose consequences they do get somewhat right. Some cringe-worthy moments but much better than I expected.

ReplyDelete@John, i luv ur long responses, though it'll be nice if they come in a more digestable fashion for readers. #comments #keepITshort

ReplyDeleteAnonymous, I agree with you regarding the virtue of concision … and yet the tide of modern mathematics flows strongly against us both.

DeleteConsider for example the page upon which the mathematical notion of "smoothness" is defined:

• John Milnor's (lucid; classic) monograph

Singular Points of Complex Hypersurfaces(1968): page 3.• Ravi Vakil's (justly praised; free-as-in-freedom; often-hilarious) monograph

(2013): page 321.Foundations of Algebraic GeometryTo paraphrase Mark Twain: "Any calm person, who is not blind or idiotic, can see that the mathematical notion of 'smoothness' is hundreds of times more subtle and complicated than we conceived it fifty years ago!"

Given the ubiquity of mathematics in engineering, it's amazing that engineering degree programs finish in four short years, both then and now. It is natural to wonder:

How does that work exactly?But we may learn something about how NOT to prove that P ≠ NP here:

ReplyDeletehttp://gowers.wordpress.com/2013/10/03/how-not-to-prove-that-p-is-not-equal-to-np/

Anonymous, thank you for that link to Tim Gowers' mathematical essay. Students, in particular, may enjoy too Tim Gowers' remarks — along with remarks by Martin Rees and Steven Hawking — in the video essay

Delete.The Isaac Newton Institute for Mathematical Scienceshttp://mathoverflow.net/q/160099/34859 Any views

ReplyDelete