دانلود کتاب Mathematics and Computation: A Theory Revolutionizing Technology and Science

فهرست مطالب :

Title
Copyright
Dedication
Contents
Acknowledgments
1 Introduction
1.1 On the interactions of math and computation
1.2 Computational complexity theory
1.3 The nature, purpose, and style of this book
1.4 Who is this book for?
1.5 Organization of the book
1.6 Notation and conventions
2 Prelude: Computation, undecidability, and limits to mathematical knowledge
3 Computational complexity 101: The basics, P, and NP
3.1 Motivating examples
3.2 Efficient computation and the class P
3.2.1 Why polynomial?
3.2.2 Why worst case?
3.2.3 Some problems in P
3.3 Efficient verification and the class NP
3.4 The P vs. NP question: Its meaning and importance
3.5 The class coNP, the NP vs. coNP question, and efficiently characterizable structures
3.6 Reductions: A partial order of computational difficulty
3.7 Completeness: Problems capturing complexity classes
3.8 NP-completeness
3.9 Some NP-complete problems
3.10 The nature and impact of NP-completeness
4 Problems and classes inside (and around) NP
4.1 Other types of computational problems and complexity classes
4.2 Between P and NP
4.3 Constraint satisfaction problems (CSPs)
4.3.1 Exact solvability and the dichotomy conjecture
4.3.2 Approximate solvability and the unique games conjecture
4.4 Average-case complexity
4.5 One-way functions, trap-door functions, and cryptography
5 Lower bounds, Boolean circuits, and attacks on P vs. NP
5.1 Diagonalization and relativization
5.2 Boolean circuits
5.2.1 Basic results and questions
5.2.2 Boolean formulas
5.2.3 Monotone circuits and formulas
5.2.4 Natural Proofs, or, Why is it hard to prove circuit lower bounds?
6 Proof complexity
6.1 The pigeonhole principle|a motivating example
6.2 Propositional proof systems and NP vs. coNP
6.3 Concrete proof systems
6.3.1 Algebraic proof systems
6.3.2 Geometric proof systems
6.3.3 Logical proof systems
6.4 Proof complexity vs. circuit complexity
7 Randomness in computation
7.1 The power of randomness in algorithms
7.2 The weakness of randomness in algorithms
7.2.1 Computational pseudo-randomness
7.2.2 Pseudo-random generators
7.3 Computational pseudo-randomness and pseudo-random generators
7.3.1 Computational indistinguishability and cryptography
7.3.2 Pseudo-random generators from hard problems
7.3.3 Final high-level words on de-randomization
8 Abstract pseudo-randomness
8.1 Motivating examples
8.2 General pseudo-random properties and finding hay in haystacks
8.3 The Riemann hypothesis
8.4 P vs. NP
8.5 Computational pseudo-randomness and de-randomization
8.6 Quasi-random graphs
8.7 Expanders
8.8 Structure vs. pseudo-randomness
9 Weak random sources and randomness extractors
9.1 Min-entropy and randomness extractors
9.1.1 Min-entropy: Formalizing weak random sources
9.1.2 Extractors: Formalizing the purification of randomness
9.2 Explicit constructions of extractors
9.3 Structured weak sources, and deterministic extractors
10 Randomness and interaction in proofs
10.1 Interactive proof systems
10.2 Zero-knowledge proof systems
10.3 Probabilistically checkable proofs (PCPs), and hardness of approximation
10.3.1 Hardness of approximation
10.4 Perspective and impact
11 Quantum computing
11.1 Building a quantum computer
11.2 Quantum proofs, quantum Hamiltonian complexity, and dynamics
11.2.1 The complexity of ground state energy
11.2.2 Ground states, entanglement, area law, and tensor networks
11.2.3 Hamiltonian dynamics and adiabatic computation
11.3 Quantum interactive proofs, and testing quantum mechanics
11.4 Quantum randomness: Certification and expansion
12 Arithmetic complexity
12.1 Motivation: Univariate polynomials
12.2 Basic definitions, questions, and results
12.3 The complexity of basic polynomials
12.3.1 Symmetric polynomials
12.3.2 Matrix multiplication
12.3.3 The determinant
12.3.4 The permanent
12.4 Reductions and completeness, VP and VNP
12.5 Restricted models
12.5.1 Monotone circuits
12.5.2 Multilinear circuits
12.5.3 Bounded-depth circuits
12.5.4 Non-commutative circuits
13 Interlude: Concrete interactions between math and computational complexity
13.1 Number theory
13.2 Combinatorial geometry
13.3 Operator theory
13.4 Metric geometry
13.5 Group theory
13.6 Statistical physics
13.7 Analysis and probability
13.8 Lattice theory
13.9 Invariant theory
13.9.1 Geometric complexity theory
13.9.2 Simultaneous conjugation
13.9.3 Left-Right action
14 Space complexity: Modeling limited memory
14.1 Basic space complexity
14.2 Streaming and sketching
14.3 Finite automata and counting
15 Communication complexity: Modeling information bottlenecks
15.1 Basic definitions and results
15.2 Applications
15.2.1 VLSI time-area trade-offs
15.2.2 Time-space trade-offs
15.2.3 Formula lower bounds
15.2.4 Proof complexity
15.2.5 Extension complexity
15.2.6 Pseudo-randomness
15.3 Interactive information theory and coding theory
15.3.1 Information complexity, protocol compression, and direct sum
15.3.2 Error correction of interactive communication
16 On-line algorithms: Coping with an unknown future
16.1 Paging, caching, and the k-server problem
16.2 Expert advice, portfolio management, repeated games, and the multiplicative weights algorithm
17 Computational learning theory, AI, and beyond
17.1 Classifying hyperplanes: A motivating example
17.2 Classification/Identification: Some choices and modeling issues
17.2.1 Target class of functions
17.2.2 Hypothesis class
17.2.3 Admissible presentation of data
17.2.4 Quality measures for identification algorithms
17.3 Identification in the limit: A linguistic/recursion theoretic approach
17.4 Probably, approximately correct (PAC) learning: A statistical approach
17.4.1 Basics of the PAC framework
17.4.2 Efficiency and optimization
17.4.3 Agnostic PAC learning
17.4.4 Compression and Occam\'s razor
17.4.5 Boosting: Making weak learners strong
17.4.6 The hardness of PAC learning
18 Cryptography: Modeling secrets and lies, knowledge and trust
18.1 The ambitions of modern cryptography
18.2 Information theory vs. complexity theory: Take 1
18.3 The axioms of modern, complexity-based cryptography
18.4 Cryptographic definitions
18.5 Probabilistic encryption
18.6 Basic paradigms for security definitions
18.6.1 The simulation paradigm
18.6.2 The ideal functionality paradigm
18.7 Secure multi-party computation
18.8 Information theory vs. complexity theory: Take 2
18.9 More recent advances
18.9.1 Homomorphic encryption
18.9.2 Delegation of computation
18.9.3 Program obfuscation
18.10 Physical attacks
18.11 The complexity of factoring
19 Distributed computing: Coping with asynchrony
19.1 High-level modeling issues
19.2 Sharing resources and the dining philosophers problem
19.3 Coordination: Consensus and Byzantine generals
19.4 Renaming, k-set agreement, and beyond
19.4.1 Sperner\'s lemma and Brouwer\'s fixed-point theorem
19.4.2 Proof sketch of the impossibility theorem
19.4.3 General input-output problems and simplicial homology
19.5 Local synchronous coloring
20 Epilogue: A broader perspective of ToC
20.1 Close collaborations and interactions
20.1.1 Computer science and engineering
20.1.2 Mathematics
20.1.3 Optimization
20.1.4 Coding and information theory
20.1.5 Statistical physics
20.2 What is computation?
20.3 ToC methodology
20.4 The computational complexity lens on the sciences
20.4.1 Molecular biology
20.4.2 Ecology and evolution
20.4.3 Neuroscience
20.4.4 Quantum physics
20.4.5 Economics
20.4.6 Social science
20.5 Conceptual contributions; or, algorithms and philosophy
20.6 Algorithms and technology
20.6.1 Algorithmic heroes
20.6.2 Algorithms and Moore\'s law
20.6.3 Algorithmic gems vs. deep nets
20.7 Some important challenges of ToC
20.7.1 Certifying intractability
20.7.2 Understanding heuristics
20.7.3 Resting cryptography on stronger foundations
20.7.4 Exploring physical reality vs. computational complexity
20.8 K-12 education
20.9 The ToC community
20.10 Conclusions
References