دانلود کتاب Mathematics and computation

فهرست مطالب :

Title......Page 4
Copyright......Page 5
Dedication......Page 6
Contents......Page 8
Acknowledgments......Page 14
1 Introduction......Page 18
1.1 On the interactions of math and computation......Page 19
1.2 Computational complexity theory......Page 22
1.4 Who is this book for?......Page 24
1.5 Organization of the book......Page 25
1.6 Notation and conventions......Page 29
2 Prelude: Computation, undecidability, and limits to mathematical knowledge......Page 31
3.1 Motivating examples......Page 36
3.2 Efficient computation and the class P......Page 38
3.2.1 Why polynomial?......Page 39
3.2.2 Why worst case?......Page 40
3.2.3 Some problems in P......Page 41
3.3 Efficient verification and the class NP......Page 43
3.4 The P vs. NP question: Its meaning and importance......Page 47
3.5 The class coNP, the NP vs. coNP question, and efficiently characterizable structures......Page 51
3.6 Reductions: A partial order of computational difficulty......Page 54
3.7 Completeness: Problems capturing complexity classes......Page 55
3.8 NP-completeness......Page 56
3.9 Some NP-complete problems......Page 57
3.10 The nature and impact of NP-completeness......Page 59
4.1 Other types of computational problems and complexity classes......Page 64
4.2 Between P and NP......Page 66
4.3.1 Exact solvability and the dichotomy conjecture......Page 69
4.3.2 Approximate solvability and the unique games conjecture......Page 70
4.4 Average-case complexity......Page 72
4.5 One-way functions, trap-door functions, and cryptography......Page 74
5.1 Diagonalization and relativization......Page 78
5.2 Boolean circuits......Page 79
5.2.1 Basic results and questions......Page 81
5.2.2 Boolean formulas......Page 82
5.2.3 Monotone circuits and formulas......Page 85
5.2.4 Natural Proofs, or, Why is it hard to prove circuit lower bounds?......Page 87
6 Proof complexity......Page 90
6.1 The pigeonhole principle|a motivating example......Page 93
6.2 Propositional proof systems and NP vs. coNP......Page 94
6.3.1 Algebraic proof systems......Page 95
6.3.2 Geometric proof systems......Page 98
6.3.3 Logical proof systems......Page 101
6.4 Proof complexity vs. circuit complexity......Page 104
7.1 The power of randomness in algorithms......Page 106
7.2 The weakness of randomness in algorithms......Page 109
7.2.1 Computational pseudo-randomness......Page 110
7.2.2 Pseudo-random generators......Page 111
7.3.1 Computational indistinguishability and cryptography......Page 113
7.3.2 Pseudo-random generators from hard problems......Page 115
7.3.3 Final high-level words on de-randomization......Page 120
8.1 Motivating examples......Page 122
8.2 General pseudo-random properties and finding hay in haystacks......Page 123
8.3 The Riemann hypothesis......Page 125
8.4 P vs. NP......Page 127
8.5 Computational pseudo-randomness and de-randomization......Page 128
8.6 Quasi-random graphs......Page 131
8.7 Expanders......Page 133
8.8 Structure vs. pseudo-randomness......Page 137
9 Weak random sources and randomness extractors......Page 141
9.1.1 Min-entropy: Formalizing weak random sources......Page 142
9.1.2 Extractors: Formalizing the purification of randomness......Page 143
9.2 Explicit constructions of extractors......Page 145
9.3 Structured weak sources, and deterministic extractors......Page 147
10 Randomness and interaction in proofs......Page 149
10.1 Interactive proof systems......Page 151
10.2 Zero-knowledge proof systems......Page 153
10.3 Probabilistically checkable proofs (PCPs), and hardness of approximation......Page 157
10.3.1 Hardness of approximation......Page 158
10.4 Perspective and impact......Page 160
11 Quantum computing......Page 163
11.1 Building a quantum computer......Page 167
11.2 Quantum proofs, quantum Hamiltonian complexity, and dynamics......Page 168
11.2.1 The complexity of ground state energy......Page 169
11.2.2 Ground states, entanglement, area law, and tensor networks......Page 170
11.2.3 Hamiltonian dynamics and adiabatic computation......Page 171
11.3 Quantum interactive proofs, and testing quantum mechanics......Page 172
11.4 Quantum randomness: Certification and expansion......Page 173
12.1 Motivation: Univariate polynomials......Page 177
12.2 Basic definitions, questions, and results......Page 178
12.3.1 Symmetric polynomials......Page 179
12.3.2 Matrix multiplication......Page 182
12.3.3 The determinant......Page 183
12.4 Reductions and completeness, VP and VNP......Page 184
12.5 Restricted models......Page 187
12.5.2 Multilinear circuits......Page 188
12.5.3 Bounded-depth circuits......Page 189
12.5.4 Non-commutative circuits......Page 190
13.1 Number theory......Page 191
13.2 Combinatorial geometry......Page 193
13.3 Operator theory......Page 194
13.4 Metric geometry......Page 196
13.5 Group theory......Page 198
13.6 Statistical physics......Page 200
13.7 Analysis and probability......Page 203
13.8 Lattice theory......Page 206
13.9 Invariant theory......Page 208
13.9.1 Geometric complexity theory......Page 210
13.9.2 Simultaneous conjugation......Page 211
13.9.3 Left-Right action......Page 213
14.1 Basic space complexity......Page 215
14.2 Streaming and sketching......Page 218
14.3 Finite automata and counting......Page 220
15.1 Basic definitions and results......Page 224
15.2.1 VLSI time-area trade-offs......Page 228
15.2.2 Time-space trade-offs......Page 229
15.2.3 Formula lower bounds......Page 230
15.2.4 Proof complexity......Page 232
15.2.5 Extension complexity......Page 234
15.2.6 Pseudo-randomness......Page 237
15.3 Interactive information theory and coding theory......Page 238
15.3.1 Information complexity, protocol compression, and direct sum......Page 239
15.3.2 Error correction of interactive communication......Page 243
16 On-line algorithms: Coping with an unknown future......Page 247
16.1 Paging, caching, and the k-server problem......Page 249
16.2 Expert advice, portfolio management, repeated games, and the multiplicative weights algorithm......Page 250
17 Computational learning theory, AI, and beyond......Page 255
17.1 Classifying hyperplanes: A motivating example......Page 256
17.2.1 Target class of functions......Page 259
17.2.4 Quality measures for identification algorithms......Page 260
17.3 Identification in the limit: A linguistic/recursion theoretic approach......Page 261
17.4 Probably, approximately correct (PAC) learning: A statistical approach......Page 264
17.4.1 Basics of the PAC framework......Page 265
17.4.3 Agnostic PAC learning......Page 269
17.4.4 Compression and Occam\'s razor......Page 270
17.4.5 Boosting: Making weak learners strong......Page 271
17.4.6 The hardness of PAC learning......Page 274
18.1 The ambitions of modern cryptography......Page 277
18.2 Information theory vs. complexity theory: Take 1......Page 278
18.3 The axioms of modern, complexity-based cryptography......Page 279
18.4 Cryptographic definitions......Page 281
18.5 Probabilistic encryption......Page 282
18.6 Basic paradigms for security definitions......Page 284
18.6.1 The simulation paradigm......Page 285
18.6.2 The ideal functionality paradigm......Page 286
18.7 Secure multi-party computation......Page 289
18.8 Information theory vs. complexity theory: Take 2......Page 292
18.9.1 Homomorphic encryption......Page 293
18.9.2 Delegation of computation......Page 294
18.9.3 Program obfuscation......Page 295
18.10 Physical attacks......Page 296
18.11 The complexity of factoring......Page 297
19 Distributed computing: Coping with asynchrony......Page 298
19.1 High-level modeling issues......Page 299
19.2 Sharing resources and the dining philosophers problem......Page 301
19.3 Coordination: Consensus and Byzantine generals......Page 303
19.4 Renaming, k-set agreement, and beyond......Page 306
19.4.1 Sperner\'s lemma and Brouwer\'s fixed-point theorem......Page 308
19.4.2 Proof sketch of the impossibility theorem......Page 310
19.4.3 General input-output problems and simplicial homology......Page 312
19.5 Local synchronous coloring......Page 313
20 Epilogue: A broader perspective of ToC......Page 316
20.1 Close collaborations and interactions......Page 317
20.1.1 Computer science and engineering......Page 318
20.1.3 Optimization......Page 319
20.1.4 Coding and information theory......Page 320
20.1.5 Statistical physics......Page 322
20.2 What is computation?......Page 324
20.3 ToC methodology......Page 326
20.4 The computational complexity lens on the sciences......Page 330
20.4.1 Molecular biology......Page 332
20.4.2 Ecology and evolution......Page 334
20.4.3 Neuroscience......Page 336
20.4.4 Quantum physics......Page 337
20.4.5 Economics......Page 339
20.4.6 Social science......Page 343
20.5 Conceptual contributions; or, algorithms and philosophy......Page 344
20.6 Algorithms and technology......Page 346
20.6.1 Algorithmic heroes......Page 347
20.6.3 Algorithmic gems vs. deep nets......Page 348
20.7.1 Certifying intractability......Page 350
20.7.2 Understanding heuristics......Page 351
20.7.3 Resting cryptography on stronger foundations......Page 353
20.7.4 Exploring physical reality vs. computational complexity......Page 354
20.8 K-12 education......Page 357
20.9 The ToC community......Page 359
20.10 Conclusions......Page 362
References......Page 366