In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanicsCongratulations ! For getting the award, and demonstrating that hard-core complexity theory CAN get funded...
Update: Sanjeev Arora comments...
I wonder about the value of such large grants to a small group of theoreticians unless it is to set up a new center such as DIMACS that helps bring together many people.
ReplyDeleteTheoretical breakthroughs mostly happen because of inspired individuals working at many diverse places. This is in contrast to system building efforts which benefit from having a single large and capable group making a systematic effort over some given time horizon to make use of existing knowledge and some new stuff. Having one (or a few) group helps in managing and streamlining the choices and trade offs that have to be made in building any large and complex system.
Of course the group at Princeton is outstanding and they will produce high quality stuff. However, I am not convinced that the 10 million is going to substantially change what they already do.
Actually one of the mandates in the proposal is to create a new center for complexity theory at Princeton.
ReplyDeleteIt's true that breakthroughs often happen in the way you mention, but don't underestimate the power of a center to draw researchers together, have workshops where people interact, etc. This is all part of what will happen as part of this grant, I believe, and one only need look at the success of venues like DIMACS, Dagstuhl, and others to feel confident that good things will come of this.
Also, it's in a sense a statement: departments watch closely to see what the NSF is funding as a way of guiding their own growth efforts, and this is a strong validation of efforts in an area that traditionally gets short shrift at hiring time.
(Also posted at Mitzenmacher's blog)
ReplyDeleteSomebody sent me a link to this discussion. As Michael knows, I am also the chair for the Sigact committee for advancement of TCS, and our efforts are also leading to expansion of funding for theory in general.
Unfortunately (or fortunately) the trend towards giving larger grants seems irreversible, and there is no way for a specific field to "opt out" of such a cross-cutting program in exchange for increases in that field only.
If we hadn't got this grant, some other group in CS would have. It is not the same pot of money.
Our proposal was actually quite specific and broke up the larger complexity/algorithms agenda into short and medium term goalposts. (By the way, this is an important part of writing theory grants for cross-cutting programs; I'm happy to talk to anybody who plans to apply to such programs about and needs some tips).
"Business as usual"...
Believe me, we got a lot of grilling over this at all stages of this multistage process. There were almost no theory people on the final panel, and I am amazed that they were so receptive to our project. In fact, I think 3 out of 4 funded projects (out of 75 that entered the competition) are somewhat related to theory or algorithms.
BTW, our project is a bit broader than just complexity theory. And Princeton is one of 4 participating institutions.
Sanjeev Arora