Mathematics and Computation - Institute for Advanced Study

1 Mathematics and ComputationMathematics and ComputationA Theory Revolutionizing Technology and ScienceAvi WigdersonPrinceton University PressPrinceton and OxfordCopyrightc 2019 by Avi WigdersonRequests for permission to reproduce material from thiswork should be sent to by Princeton University Press,41 William Street, Princeton, New Jersey 08540In the United Kingdom: Princeton University Press,6 Oxford Street, Woodstock, Oxfordshire OX20 Rights ReservedLibrary of Congress Control Number: 2018965993 ISBN: 978-0-691-18913-0 British Library Cataloging-in-Publication Data is availableEditorial: Vickie Kearn, Lauren Bucca, and Susannah ShoemakerProduction Editorial: Nathan CarrCover design: Sahar Batsry and Avi WigdersonProduction: Jacquie PoirierPublicity: Matthew Taylor and Kathryn StevensCopyeditor: Cyd WestmorelandThis book has been composed in LATEXThe publisher would like to acknowledge the author of this volume forproviding the camera-ready copy from which this book was on acid-free paper Printed in the United States of America10 9 8 7 6 5 4 3 2 1 Dedicated to the memory of my father, Pinchas Wigderson (1921 1988),who loved people, loved puzzles, and inspired , Turkmenistan, 1943 ContentsAcknowledgmentsxiii1 the interactions of math and Computation .

2 Complexity theory .. nature, purpose, and style of this book .. is this book for? .. of the book .. and conventions ..102 Prelude: Computation , undecidability, and limits to mathematical knowledge113 Computational complexity 101: The basics,P, examples .. Computation and the classP.. polynomial? .. worst case? .. problems inP.. verification and the classNP.. : Its meaning and importance .. class coNP, theNPvs. coNPquestion, and efficiently characterizable structures .. : A partial order of computational difficulty .. : Problems capturing complexity classes .. problems .. The nature and impact ofNP-completeness ..334 Problems and classes inside (and around) types of computational problems and complexity classes .. satisfaction problems (CSPs) .. solvability and the dichotomy conjecture .. solvability and the unique games conjecture .. complexity .. functions, trap-door functions, and cryptography ..445 Lower bounds, Boolean circuits, and attacks and relativization.

3 Circuits .. results and questions .. formulas .. circuits and formulas .. Proofs, or, Why is it hard to prove circuit lower bounds? ..556 Proof pigeonhole principle a motivating example .. proof systems andNPvs. coNP.. proof systems .. proof systems .. proof systems .. proof systems ..66viiAvi WigdersonMathematics and ComputationDraft: August 6, complexity vs. circuit complexity ..687 Randomness in power of randomness in algorithms .. weakness of randomness in algorithms .. pseudo-randomness .. generators .. pseudo-randomness and pseudo-random generators .. indistinguishability and cryptography .. generators from hard problems .. high-level words on de-randomization ..808 Abstract examples .. pseudo-random properties and finding hay in haystacks .. Riemann hypothesis .. pseudo-randomness and de-randomization .. graphs .. vs. pseudo-randomness ..939 Weak random sources and randomness and randomness extractors .. : Formalizing weak random sources.

4 : Formalizing the purification of randomness .. constructions of extractors .. weak sources, and deterministic extractors .. 10210 Randomness and interaction in Interactive proof systems .. Zero-knowledge proof systems .. Probabilistically checkable proofs (PCPs), and hardness of approximation .. Hardness of approximation .. Perspective and impact .. 11111 Quantum Building a quantum computer .. Quantum proofs, quantum Hamiltonian complexity, and dynamics .. The complexity of ground state energy .. Ground states, entanglement, area law, and tensor networks .. Hamiltonian dynamics and adiabatic Computation .. Quantum interactive proofs, and testing quantum mechanics .. Quantum randomness: Certification and expansion .. 12212 Arithmetic Motivation: Univariate polynomials .. Basic definitions, questions, and results .. The complexity of basic polynomials .. Symmetric polynomials.

5 Matrix multiplication .. The determinant .. 129viiiAvi WigdersonMathematics and ComputationDraft: August 6, The permanent .. Reductions and completeness,VPandVNP.. Restricted models .. Monotone circuits .. Multilinear circuits .. Bounded-depth circuits .. Non-commutative circuits .. 13413 Interlude: Concrete interactions between math and computational Number theory .. Combinatorial geometry .. Operator theory .. Metric geometry .. Group theory .. Statistical physics .. Analysis and probability .. Lattice theory .. Invariant theory .. Geometric complexity theory .. Simultaneous conjugation .. Left-Right action .. 15214 Space complexity: Modeling limited Basic space complexity .. Streaming and sketching .. Finite automata and counting .. 15815 Communication complexity: Modeling information Basic definitions and results .. Applications.

6 VLSI time-area trade-offs .. Time-space trade-offs .. Formula lower bounds .. Proof complexity .. Extension complexity .. Pseudo-randomness .. Interactive information theory and coding theory .. Information complexity, protocol compression, and direct sum .. Error correction of interactive communication .. 17516 On-line algorithms: Coping with an unknown Paging, caching, and thek-server problem .. Expert advice, portfolio management, repeated games, and the multiplicative weights algorithm18117 Computational learning theory, AI, and Classifying hyperplanes: A motivating example .. Classification/Identification: Some choices and modeling issues .. Target class of functions .. Hypothesis class .. Admissible presentation of data .. Quality measures for identification algorithms .. Identification in the limit: A linguistic/recursion theoretic approach .. 189ixAvi WigdersonMathematics and ComputationDraft: August 6, Probably, approximately correct (PAC) learning:A statistical approach.

7 Basics of the PAC framework .. Efficiency and optimization .. Agnostic PAC learning .. Compression and Occam s razor .. Boosting: Making weak learners strong .. The hardness of PAC learning .. 19918 Cryptography: Modeling secrets and lies, knowledge and The ambitions of modern cryptography .. Information theory vs. complexity theory: Take 1 .. The axioms of modern, complexity-based cryptography .. Cryptographic definitions .. Probabilistic encryption .. Basic paradigms for security definitions .. The simulation paradigm .. The ideal functionality paradigm .. Secure multi-party Computation .. Information theory vs. complexity theory: Take 2 .. More recent advances .. Homomorphic encryption .. Delegation of Computation .. Program obfuscation .. Physical attacks .. The complexity of factoring .. 21719 Distributed computing: Coping with High-level modeling issues.

8 Sharing resources and the dining philosophers problem .. Coordination: Consensus and Byzantine generals .. Renaming,k-set agreement, and beyond .. Sperner s lemma and Brouwer s fixed-point theorem .. Proof sketch of the impossibility theorem .. General input-output problems and simplicial homology .. Local synchronous coloring .. 23020 Epilogue: A broader perspective of Close collaborations and interactions .. Computer science and engineering .. Mathematics .. Optimization .. Coding and information theory .. Statistical physics .. What is Computation ? .. ToC methodology .. The computational complexity lens on the sciences .. Molecular biology .. Ecology and evolution .. Neuroscience .. Quantum physics .. Economics .. 249xAvi WigdersonMathematics and ComputationDraft: August 6, Social science .. Conceptual contributions; or, algorithms and philosophy.

9 Algorithms and technology .. Algorithmic heroes .. Algorithms and Moore s law .. Algorithmic gems vs. deep nets .. Some important challenges of ToC .. Certifying intractability .. Understanding heuristics .. Resting cryptography on stronger foundations .. Exploring physical reality vs. computational complexity .. K 12 education .. The ToC community .. Conclusions .. 266 References270xiAcknowledgmentsIn this book I tried to present some of the knowledge and understanding I acquired in my four decades inthe field. The main source of this knowledge was the Theory of Computation community, which has beenmy academic and social home throughout this period. The members of this wonderful community, especiallymy teachers, students, postdocs and collaborators, but also the speakers in numerous talks I attended, havebeen the source of this knowledge and understanding often far more than the books and journals I is a generous and interactive community, whose members are happy to share their own knowledge andunderstanding with others, and are trained by the culture of the field to do so well.

10 These interactions made(and still makes) learning a greatly joyful experience for me!More directly, the content and presentation in this book benefited from many who carefully read earlierdrafts, and responded with valuable constructive comments at all levels; this made the book much better. Forthis I am grateful to Scott Aaronson, Dorit Aharonov, Morteza Alimi, Noga Alon, Sanjeev Arora, Boaz Barak,Zeb Brady, Mark Braverman, Bernard Chazelle, Neil Chriss, Tom Church, Geoffroy Couteau, Dennis Dolan,Andy Drucker, Ron Fagin, Yuval Filmus, Michael Forbes, Ankit Garg, Sumegha Garg, Oded Goldreich,Renan Gross, Nadia Heninger, Gil Kalai, Vickie Kearn, Pravesh Kothari, James Lee, Alex Lubotzky, AssafNaor, Ryan O Donnell, Toni Pitassi, Tim Randolph, Sasha Razborov, Tim Roughgarden, Mike Saks, PeterSarnak, Susannah Shoemaker, Amir Shpilka, Alistair Sinclair, Bill Steiger, Arpita Tripathi, Salil Vadhan,Les Valiant, Thomas Vidick, Ben Lee Volk, Cyd Westmoreland, Edna Wigderson, Yuval Wigderson, Ronaldde Wolf, Amir Yehudayoff, Rich Zemel and David special thanks go to Sahar Batsry for many days of meticulous work on many evolving ideas I hadfor the cover design, to Edna and Yuval Wigderson for great help with all aspects of LATEX, English.