My father, in different conditions would have been an intellectual. He would have been maybe an academic, I don't know, it's very hard to say but he was just forced to find a job when he arrived. Then he had a family and he supported it.

We grew up, me and my two brothers, in a tiny apartment in a block in a neighbourhood on the beach in Haifa. It is very different if I look at it now than I did as a kid. For a child it was heaven because up till the age of fifteen pretty much all I did was play around the beach and play soccer. They were the only two activities we were engaged in like most kids.

There is a famous high school, the Reali High School, in Haifa which was a semi-private place which was a rare thing in Israel, it still is a rare thing in Israel. It was a very good high school. In it there were some excellent teachers, in particular I had a maths teacher [Kaplan] who had just come from Ukraine in my last year of high school and he was phenomenal. His teaching was rigorous but it was also inspiring - his love, his passion for mathematics. He had written textbooks in Russian which I had copies of even though I couldn't read them but they taught me something. He gave extra-curricular classes, going beyond the syllabus, so some of us took these classes learning about some college material.

We had, in particular, a very inspiring teacher, Shimon Even, at the Technion. His courses on algorithms and complexity were extremely inspiring. When I applied to graduate school I applied for continuing to do this sort of stuff. This was how I was drawn into theoretical computer science.

Shimon Even received a B.Sc. degree in Electrical Engineering from the Technion in 1959, an M.A. in Mathematics from the University of Northern Carolina in 1961, and a Ph.D. in Applied Mathematics from Harvard University in 1963. He held positions at the Technion (1964-67 and 1974-2003), Harvard University (1967-69), the Weizmann Institute (1969-74), and the Tel-Aviv Academic College (2003-04). ... In 1974 he joined the newly formed computer science department at the Technion and shaped its academic development for several decades. ... Shimon Even was a superb teacher, and his courses deeply influenced many of the students attending them. His lectures, at numerous international workshops and schools, inspired a great number of students and researchers. His books, especially his celebrated Graph Algorithms, carried his educational message also to computer scientists who were not fortunate enough to meet him in person. As a mentor to aspiring researchers, Shimon was almost without peer, nurturing numerous junior researchers and advising many graduate students, who went on to have their own successful research careers.

My connections with the Technion are deep and numerous. It's my alma mater. It inspired and prepared me for my career. I met my wife here. We even got married here. Israeli universities, and the Technion in particular, have been beacons of excellence, contributing to Israel's economy and security. The Technion is dedicated to the pursuit of knowledge and truth. Openness, inclusivity, free speech - these are the necessary foundations of this search; without them, there can be no truth and no science.

Lipton did complexity; he became my advisor. So this attracted me more. He is a man of amazing creativity and broad interests so we kept switching research areas. I moved with him and I learned various things. He would ask me questions about many of the areas and I became interested in lots of things so now I don't think of myself as working in one area; maybe I got his bug of thinking about mathematical questions about computing and its very broad.

I wrote papers with classmates on different subjects and my thesis was just a collection of a few papers. It was not really a cohesive topic but my advisor was happy with it, so I was happy too. In the meantime my wife and I also had our first child, which is maybe a more impressive production than a Ph.D.

In a career that has spanned more than 40 years, Wigderson has resolved longstanding open problems, made definitions that shaped entire fields, built unexpected bridges between different areas, and introduced ideas and techniques that inspired generations of researchers. A recurring theme in Wigderson's work has been uncovering the deep connections between computer science and mathematics. His papers have both demonstrated unexpected applications of diverse mathematical areas to questions in computer science, and shown how to use theoretical computer science insights to solve problems in pure mathematics.

Here is just one tip of the iceberg we'll explore in this book: How much time does it take to find the prime factors of a 1,000-digit integer? The facts are that (1) we can't even roughly estimate the answer: it could be less than a second or more than a million years, and (2) practically all electronic commerce and Internet security systems in existence today rest on the belief that it takes more than a million years!

Digesting even this single example begins to illuminate the conceptual revolution of computational complexity theory, to which this book is devoted. It illustrates how a pure number theoretic problem, which has been studied for millennia by mathematicians, becomes a cornerstone of a trillion-dollar industry, on which practically all people, companies, and countries crucially depend. Extracting this novel meaning and utility relies on making the above problem precise, and on transforming the informal statement of (2) into a mathematical theorem. This in turn requires formal definitions of such concepts as algorithm, efficiency, secret, and randomness, among others, including several new notions of proof. The difficulty of resolving (the now all-important) challenge (1), namely, proving the hardness of factoring or suggesting alternatives to it, is intimately related to the great conundrum of P vs. NP. And as a final twist in this plot, a fork appeared in our computational path, by which the answer to (1) may radically depend on whether we allow classical or quantum physics to power our computers. This new possibility has propelled huge investments in academia and industry to attempt to physically realise the potential of quantum computers. It also demands revisiting and redefining the very concepts mentioned above, as well as many physical ones like entanglement and decoherence, interacting with quantum mechanics and proposing novel ways of testing its foundations.

The book you are reading will explore the mathematical and intellectual aspects of this goldmine. It will explain computational complexity theory, the concepts this theory created and revolutionised, and its many connections and interactions with mathematics. In its half-century of existence, computational complexity theory has developed into a rich, deep, and broad mathematical theory with remarkable achievements and formidable challenges. It has forged strong connections with most other mathematical fields and at the same time is having a major practical impact on the technological revolution affecting all aspects of our society (of which Internet security and quantum computing above are "mere" examples).

Computational complexity theory is a central subfield of the theory of computation (ToC), and is playing a pivotal role in its evolution. This theory stands with the great ones of physics, biology, maths, and economics, and is central to a new scientific revolution informed by computation. I have devoted the final chapter of this book (which can be read first) to a panoramic overview of ToC. That chapter describes the intellectual supernova that the theory of computing has created and continues to shape. It reveals the broad reach of ToC to all sciences, technology, and society, and discusses its methodology, challenges, and unique position in the intellectual sphere.

Far too many mathematical papers and texts fall short on explanations (I'm tempted to say that the non-readability property in the universe of such papers is pseudo-random, or even that too many zero-knowledge proofs make their way into the literature). While one does see some attention paid to such issues, we are left wanting more: Why do we define things a certain way? Why is this theorem interesting? How might one come up with this proof? What is the intuition behind it? How did people come to study these concepts, where do they come from, and where are they going? This book fills in this gap for an enormous swath of ToC, largely but not exclusively as regards computational complexity, and how it interacts with mathematics. ... "Mathematics and Computation" is a truly outstanding book. One could hardly find a more expert and capable field guide than Avi Wigderson.

... contributions to theoretical computer science and mathematics.

... for fundamental and lasting contributions to the foundations of computer science in areas including randomised computation, cryptography, circuit complexity, proof complexity, parallel computation, and our understanding of fundamental graph properties.

... for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.

Can you play poker on the telephone with people you don't trust? Amazingly, you can! ... the ideas involved, and related ones, also underlie internet security and e-commerce.

The general public is well aware of the essential role cryptography plays in underlying security and privacy of all digital communications. Much less known are the beautiful ideas and concepts underlying cryptography, and the amazing impact they had on many other developments in computer science.

Perhaps even less known is how cryptography arose from mind games and toy problems (see below) which predated the Internet, and whose magical solutions enabled the many applications which drove its fast development.

Can two people who never met create a secret language, in the presence of others, which no one but them can understand? Can you convince others that you have solved a really difficult puzzle, without giving them the slightest hint of your solution? Can a group of people play a (card-less) game of poker on the telephone, without anyone being able to cheat? Can they collectively toss a fair coin so that no subset can bias it?

Such questions (and their remarkable answers) kick-started the theory of modern cryptography.