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.

2 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 .. complexity theory .. nature, purpose, and style of this book .. is this book for? .. of the book .. and conventions.

3 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.

4 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 .. 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.

5 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.

6 : Formalizing weak random sources .. : 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.

7 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 .. Matrix multiplication .. The determinant .. 129viiiAvi WigdersonMathematics and ComputationDraft: August 6, The permanent .. Reductions and completeness,VPandVNP.. Restricted models .. Monotone circuits.

8 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.

9 Finite automata and counting .. 15815 Communication complexity: Modeling information Basic definitions and results .. Applications .. 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.

10 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.