Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.)

The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0?  what is GCAAG?GTAACTC ?  TACGTTC ?  I only figured out the first.)

Avi Wigderson’s book  “Mathematics and computation, a theory revolutionizing technology and science” is about to be published by Princeton University Press. The link is to a free copy of the book which will always be available on Avi’s homepage. (See also this re-blogged post here of Boaz Barak.)

One main theme of the book is the rich connection between the theory of computing and other areas (in fact, most areas) of mathematics. See also this self contained survey (based on Chapter 13 of the book) by Avi Interactions of Computational Complexity Theory and Mathematics, which in 27 pages overviews relations to number theory, Geometry, Operator Theory, Metric Geometry, Group Theory, Statistical Physics, Analysis and Probability, Lattice Theory and Invariant Theory. Of course, Avi himself is among the main heroes in finding many paths between mathematics and the theory of computing over the last four decades.

Another theme of the book and of several talks by Avi is that the theory of computing has revolutionary connections with many fields of science and technology. Again, this theme is present in the entire book and is emphasized in Chapter 20, which also appeared as a self contained paper  “On the nature of the Theory of Computation (ToC).”  Let me quote one sentence from Avi’s book that I propose for discussion. (For the complete quote see the end of the post.)

The intrinsic study of computation transcends human-made artifacts, and its expanding connections and interactions with all sciences, integrating computational modeling, algorithms,  and complexity into theories of nature and society, marks a new scientific revolution!

Of course, similar ideas were also expressed by several other prominent scientists, and let me mention Bernard Chazelle’s essay: The Algorithm: Idiom of Modern Science. (Feel free to give further examples and links in the comment section.)

Let’s discuss:  Integrating computational modeling, algorithms,  and complexity into theories of nature, marks a new scientific revolution!

I propose to discuss in the comment section the idea that the theory of computing offers a scientific revolution. Very nice cases to examine are the computational study of randomness and connections to statistics, connections with economy and connections with biology. Comments on the relations between the theory of computation and other areas of mathematics are also very welcome.

Avi’s concluding slide compared these three great theories of human understanding.

 (Previous attempts of open discussions were made in the following posts on this blog: 10 Milestones in the History of Mathematics according to Nati and Me; Why is mathematics possible? (and a follow up post); When it rains it pours;  Is it Legitimate/Ethical for Google to close Google+?; An Open Discussion and Polls: Around Roth’s Theorem; Is Mathematics a Science?)

Avi promotes the idea of the central place of the theory of computing in his talks and writings

And at the same time he is also humorously skeptical about it. (And mainly emphasizes that his far reaching claim requires careful discussion and ample evidence.)   

The full quote of Avi:

The Theory of Computation is as revolutionary, fundamental and beautiful as major theories of mathematics, physics, biology, economics… that are regularly hailed as such. Its impact has been similarly staggering. The mysteries still baffling ToC are as challenging as those left open in other fields. And quite uniquely, the theory of computation is central to most other sciences. In creating the theoretical foundations of computing systems ToC has already played, and continues to play a major part in one of the greatest scientific and technological revolutions in human history. But the intrinsic study of computation transcends man-made artifacts. ToC has already established itself as an important mathematical discipline, with growing connections to nearly all mathematical areas. And its expanding connections and interactions with all sciences, naturally integrating computational modeling, algorithms and complexity into theories of nature and society, marks the beginning of another scientific revolution!

More related material:

1. Avi’s talk Scientific revolutions, ToC and PCP  at the Tel Aviv PCP meeting and an interview of Avi by Alon Rosen.
2.  A talk by Avi on the Stepanov method
3. The recent works on polytopes arising from moment maps and related optimization problems and algorithmic aspects.  Avi’s Knuth prize videotaped lecture; Avi’s lecture  Complexity, Optimization and Math (or, Can we prove that P != NP by gradient descent?) in the recent conference honoring Bill Cook. (I plan to come back to this fascinating topic.)
4. An essay by Oded Goldreich and Avi Wigderson (essentially from 1996) “The theory of computing –  a scientific perspective.”

The volume of comments in the first decade of this blog was modest. I recently read, however, wordpress’s advice on how to reply to blog comments like a pro. 

And finally, EGDE L WONK 0 is 0-knowledge.