Through the Lens of a Passionate Theoretician

When I was taking my very first CS class—almost three decades ago—the lecturer recommended David Harel's book Algorithmics: The Spirit of Computing:¹ "If you want your friends and family to know what you are doing here" he told us, "let them read this book." A wonderful piece of advice, still applicable today, which enabled me to share my budding love for CS with others, but also helped me further my own understanding of "what we are doing here."

Many years later, our understanding of the Theory of Computation (ToC) has dramatically grown and the field is thriving. I find myself yet again with the opportunity to share my love of the riveting notion of computation. Since Avi Wigderson's Mathematics and Computation: A Theory Revolutionizing Technology and Science,² was published recently, I have been recommending it to anyone who showed an interest in ToC. But I also recommend it to my fellow theoreticians, who study ToC, because Mathematics and Computation is a way for us too to better understand what it really is that "we are doing here."

My personal-perspective Viewpoint on Mathematics and Computation, should not be read as a comprehensive summary of the book, but rather as an invitation to read and investigate it for yourself. Throughout the chapters (and especially in the self-contained Chapters 13 and 20), Wigderson lays out a body of evidence demonstrating the intellectual reach of ToC. Despite its technical breadth, the book takes a conceptual perspective and aims to reach a wide audience. While not a popular science book, there is something in the book for many audiences: advanced students, researchers in variety of area,^a educators, and motivated non-academics.

Mathematics and Computation focuses on an important branch of ToC known as Complexity Theory. Wigderson leads the reader on a fascinating expedition through notions, results (many of which were discovered after Harel's book¹ appeared) and fundamental open problems. The book discusses sub-areas like randomized computations and derandomization, cryptography, learning theory, quantum computing as well as basic topics like the P vs. NP problem, the PCP Theorem, and Zero-Knowledge proofs. Wigderson tells the story of computation and leads the reader on a fascinating expedition through these topics and many more. But he also tells us the story of the rather small research community that studies ToC and its tremendous impact.

I will devote the remainder of this Viewpoint to the book's epilogue (Chapter 20), which may very well be its most widely appealing part. The epilogue takes a much more complete view of ToC and thoroughly examines the power of the so-called computational lens: Increasingly, natural and social phenomenon are viewed by scientists as being, or performing, computations. It is, therefore, natural for computer scientists to study computations, whether they take place in our smartphones or in our cells, in the structure of social networks as well as in the evolution of species. Indeed, in recent times questions traditionally viewed as part of biology, physics, economics, sociology, arts and more, have been approached through this "computational lens."

How can computation be so far-reaching and fundamental?

How can computation be so far-reaching and fundamental? To understand, we first need to see computation in its full generality as "the evolution process of some environment, by a sequence of simple, local steps."² This takes us far beyond digital computers, to all the places where computation can happen.

For starters, it would not be controversial to argue that the human mind computes (after all, identifying the letters, words, and meanings you are reading just now requires impressive computing power). But humans are not the only animals that compute, in the words of Cole Porter, "birds do it, bees do it, even educated fleas do it." Indeed, small or large tasks of small or large animals require evolved computations. If individual animals compute, the behavior of communities of animals, composed of countless parallel actions taken by individuals in these communities, can also be naturally viewed as elaborate algorithms. The colony of ants searching an environment for food by laying down and picking up pheromone trails perform an effective algorithm for finding short paths to available food (interestingly, these algorithms inspired optimization algorithms that are executed on digital computers). Another example is the marvelous maneuver of birds flocking and fish schooling, which is made up of individuals following their programming to give space but also align with others. But if communities of other animals compute, why not communities of humans? The behavior of individuals in economic markets (computing prices), or in social networks (computing influence), are very complex but still composed of many local (and comparatively simple) steps. Not only can we observe the social behavior of communities and species through the computational lens, but we can also view the process that created these species in the first place as algorithmic in nature. The evolution of species from single cells to the splendid organisms in existence follows local, incremental steps where genetic material transforms and survives as a probabilistic function of its fitness to the environment. While, so far, we zoomed out to examine increasingly larger instances of computations, we might as well zoom in and consider computations in tiny spaces: cellular processes, such as the folding of proteins, and intercellular interactions are some of the first phenomena to be studied algorithmically with basic operations being the chemical reactions between the molecules that comprise the cell. Finally, if the cellular or molecular level is not small enough, we can consider the atomic level, where the interactions of subatomic particles is the basis of the disruptive field of quantum computation.

The real question of course is not how many phenomena can be viewed as computations, but rather what can be gained from such a perspective. The secret here lies in the efficiency and the complexity of computation: When we study computation in the world around us, it is imperative that we understand not only what is possible but also what is feasible given existing resources. The role of the computer scientist is to investigate the rules that separate what is efficient from what is too complex; this way, computational insights offer a unique perspective on old questions. A model of evolution should justify not only that such evolution is possible in principle, but also that the mechanism—the algorithm—governing evolution is likely to have produced such an organism within the resources that were at the disposal of evolution (the number of generations, the number of organisms, the number of major environmental changes). If we want to predict the behavior of a market, it is not enough to prove an equilibrium exists but also that such an equilibrium could be efficiently computed by the market. Similar considerations refine the study of any natural and social process that could be understood as a computation and makes the tools of ToC particularly powerful. Assuming the various participants in a given interaction have limited resources (for example, time or space) revolutionizes the way we understand basic notions such as knowledge, randomness, entropy, learning, secrecy, fairness, and many more.

Studying computation is not new. After all, both algebra and geometry are algorithmic since birth (it is not a coincidence that both the names algebra and algorithms originate in the name and work of the great Persian mathematician and scientist Muhammad ibn Musa al-Khwarizmi). But the birth of ToC as a modern field of study can be pinpointed to the seminal work of Turing in 1936. Turing gave a definition of computation (anticipating the invention of digital computers by a decade) which is both simple and powerful, through what is now called a Turing Machine. Since then ToC has grown in sophistication and depth, but it preserves much of the magic and the values of Turing's work. The contemporary picture portrayed by Wigderson's book is that of a deep and insightful core of ToC, surrounded by application areas within ToC (learning, algorithmic game theory, verification, pseudorandomness, property testing, distributed computing, communication complexity, quantum computing, cryptography, and more), which interact with diverse fields including computer science, mathematics, statistics, social science, biology, physics, economics.

The journey to which Wigderson invites us goes very far and very deep: it immerses the reader into the magnificent world surrounding the notion of computation. Along with the wealth of accessible knowledge and understanding offered by this book, there is passion pouring from every page, a passion that is inspiring and difficult to resist: an admiring contemplation of the scientific riddles surrounding computation, together with a convincing, book-length argument that they are as essential to unraveling the mysteries of the universe as any other pursuit of knowledge. I therefore feel it is most appropriate to conclude by letting Mathematics and Computation speak for itself, in a passage that beautifully captures the heart of the story it tells.

"The theory of computation, since its inception by Turing in 1936, is as revolutionary, fundamental, and beautiful as the great 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. Moreover, the ubiquity of computation makes its theory central to all other disciplines. 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 human-made artifacts and underlies natural and artificial processes of all types. Its expanding connections and interactions with all sciences, integrating computational modeling, algorithms, and complexity into theories of nature and society, is at the heart of a new scientific revolution!"²