Computational complexity: a modern approach

About this book......Page 3
Introduction......Page 17
I Basic Complexity Classes......Page 25
The computational model ---and why it doesn\'t matter......Page 27
Representing objects as strings......Page 28
Big-Oh notation......Page 29
Modeling computation and efficiency......Page 30
The Turing Machine......Page 31
Robustness of our definition.......Page 35
Machines as strings and the universal Turing machines.......Page 38
The Universal Turing Machine......Page 39
The Halting Problem......Page 41
On the philosophical importance of P......Page 43
Criticisms of P and some efforts to address them......Page 44
Chapter notes and history......Page 45
Exercises......Page 47
Proof of Theorem 1.13: Universal Simulation in O(TlogT)-time......Page 51
NP and NP completeness......Page 55
The class NP......Page 56
Relation between NP and P......Page 57
Non-deterministic Turing machines.......Page 58
Reducibility and NP-completeness......Page 59
The Cook-Levin Theorem: Computation is Local......Page 60
The Cook-Levin Theorem......Page 61
Warmup: Expressiveness of boolean formulae......Page 62
Proof of Lemma 2.12......Page 63
More thoughts on the Cook-Levin theorem......Page 65
The web of reductions......Page 66
Coping with NP hardness.......Page 70
Decision versus search......Page 71
coNP......Page 72
EXP and NEXP......Page 73
NP and mathematical proofs......Page 74
Chapter notes and history......Page 75
Exercises......Page 77
Diagonalization......Page 81
Space Hierarchy Theorem......Page 82
Nondeterministic Time Hierarchy Theorem......Page 83
Ladner\'s Theorem: Existence of NP-intermediate problems.......Page 84
Oracle machines and the limits of diagonalization?......Page 86
Chapter notes and history......Page 88
Exercises......Page 89
Space complexity......Page 91
Configuration graphs.......Page 92
Some space complexity classes.......Page 94
PSPACE completeness......Page 95
The essence of PSPACE: optimum strategies for game-playing.......Page 98
NL completeness......Page 100
Certificate definition of NL: read-once certificates......Page 102
NL =coNL......Page 103
Exercises......Page 104
The classes 2p and 2p......Page 107
Properties of the polynomial hierarchy.......Page 109
Complete problems for levels of PH......Page 110
Alternating Turing machines......Page 111
Time versus alternations: time-space tradeoffs for SAT.......Page 112
Defining the hierarchy via oracle machines.......Page 114
Chapter notes and history......Page 115
Exercises......Page 116
Boolean circuits......Page 117
Turing machines that take advice......Page 121
Karp-Lipton Theorem......Page 122
Circuit lowerbounds......Page 123
Finer gradations among circuit classes......Page 124
Parallel computation and NC......Page 125
P-completeness......Page 126
Circuits of exponential size......Page 127
Chapter notes and history......Page 128
Exercises......Page 129
Randomized Computation......Page 131
Probabilistic Turing machines......Page 132
Probabilistic Primality Testing......Page 133
Polynomial identity testing......Page 134
Testing for perfect matching in a bipartite graph.......Page 135
One-sided and zero-sided error: RP, coRP, ZPP......Page 136
Role of precise constants, error reduction.......Page 137
Allowing more general random choices than a fair random coin.......Page 140
Randomness efficient error reduction.......Page 141
BPPP/poly......Page 142
BPP is in PH......Page 143
Complete problems for BPP?......Page 144
Randomized space-bounded computation......Page 145
Chapter notes and history......Page 146
Exercises......Page 148
Distributions as vectors and the parameter (G).......Page 151
Analysis of the randomized algorithm for undirected connectivity.......Page 154
The Algebraic Definition......Page 155
Combinatorial expansion and existence of expanders.......Page 157
Error reduction using expanders.......Page 159
Warmup: Interactive proofs with a deterministic verifier......Page 163
The class IP......Page 165
Proving that graphs are not isomorphic.......Page 166
Public coins and AM......Page 167
Set Lower Bound Protocol.......Page 168
Tool: Pairwise independent hash functions.......Page 169
The lower-bound protocol.......Page 171
Some properties of IP and AM......Page 172
IP = PSPACE......Page 173
Interactive protocol for #SATD......Page 174
Sumcheck protocol.......Page 175
Protocol for TQBF: proof of Theorem 8.17......Page 176
The power of the prover......Page 177
Program Checking......Page 178
Languages that have checkers......Page 179
Chapter notes and history......Page 180
Exercises......Page 182
Interactive proof for the Permanent......Page 183
The protocol......Page 185
Complexity of counting......Page 187
The class #P......Page 188
The class PP: decision-problem analog for #P.......Page 189
Permanent and Valiant\'s Theorem......Page 190
Approximate solutions to #P problems......Page 194
The class P and hardness of satisfiability with unique solutions.......Page 195
Step 1: Randomized reduction from PH to P......Page 197
Step 2: Making the reduction deterministic......Page 199
Chapter notes and history......Page 200
Exercises......Page 201
Cryptography......Page 203
Hard-on-average problems and one-way functions......Page 204
Discussion of the definition of one-way function......Page 206
What is a random-enough string?......Page 207
Blum-Micali and Yao definitions......Page 208
Equivalence of the two definitions......Page 210
Goldreich-Levin hardcore bit......Page 212
Pseudorandom functions......Page 215
Private-key encryption: definition of security......Page 216
Derandomization......Page 217
Secure multiparty computations......Page 218
Chapter notes and history......Page 219
Exercises......Page 220
II Lowerbounds for Concrete Computational Models......Page 223
Decision Trees......Page 227
Certificate Complexity......Page 229
Lowerbounds on Randomized Complexity......Page 231
Some techniques for decision tree lowerbounds......Page 233
Exercises......Page 234
Chapter notes and history......Page 235
Definition......Page 237
Fooling set......Page 238
The tiling lowerbound......Page 239
Rank lowerbound......Page 240
Discrepancy......Page 241
A technique for upperbounding the discrepancy......Page 242
Comparison of the lowerbound methods......Page 243
Multiparty communication complexity......Page 244
Discrepancy-based lowerbound......Page 245
Overview of other communication models......Page 246
Exercises......Page 247
Chapter notes and history......Page 248
AC0 and Håstad\'s Switching Lemma......Page 251
The switching lemma......Page 252
Proof of the switching lemma (Lemma 13.2)......Page 253
Circuits With ``Counters\'\':ACC......Page 255
Clique Indicators......Page 258
Approximation by clique indicators.......Page 259
Circuit lowerbounds using diagonalization......Page 261
Status of ACC versus P......Page 262
Branching Programs......Page 263
Connection to ACC 0 Circuits......Page 264
Karchmer-Wigderson communication games and depth lowerbounds......Page 265
Chapter notes and history......Page 266
Exercises......Page 268
Algebraic computation models......Page 271
Algebraic circuits......Page 272
Algebraic Computation Trees......Page 274
The Blum-Shub-Smale Model......Page 278
Complexity Classes over the Complex Numbers......Page 279
Decidability Questions: Mandelbrot Set......Page 280
Chapter notes and history......Page 281
III Advanced topics......Page 283
Average Case Complexity: Levin\'s Theory......Page 285
Distributional Problems......Page 286
Formalizations of ``real-life distributions.\'\'......Page 287
Polynomial-Time on Average......Page 288
Reductions......Page 289
Proofs using the simpler definitions......Page 292
Polynomial-Time Samplability......Page 294
Chapter notes and history......Page 295
Derandomization, Expanders and Extractors......Page 297
Pseudorandom Generators and Derandomization......Page 299
Hardness and Derandomization......Page 301
Proof of Theorem 16.10: Nisan-Wigderson Construction......Page 303
Extending the input by one bit using Yao\'s Theorem.......Page 304
Extending the input by two bits using the averaging principle.......Page 305
The NW Construction......Page 306
Conditions on the set systems and function.......Page 307
Putting it all together: Proof of Theorem 16.10 from Lemmas 16.18 and 16.19......Page 308
Derandomization requires circuit lowerbounds......Page 309
Explicit construction of expander graphs......Page 312
The matrix/path product......Page 313
The tensor product......Page 314
The replacement product......Page 315
The actual construction.......Page 317
Deterministic logspace algorithm for undirected connectivity.......Page 318
Min Entropy......Page 321
Statistical distance and Extractors......Page 322
Extractors based upon hash functions......Page 323
An extractor based upon Nisan-Wigderson......Page 324
Graph constructions......Page 327
Running randomized algorithms using weak random sources......Page 328
Pseudorandom generators for spacebounded computation......Page 329
Chapter notes and history......Page 332
Exercises......Page 334
Hardness and Hardness Amplification.......Page 337
Mild to strong hardness: Yao\'s XOR Lemma.......Page 338
Proof of Yao\'s XOR Lemma using Impagliazzo\'s Hardcore Lemma.......Page 339
Proof of Impagliazzo\'s Lemma......Page 340
Error correcting codes: the intuitive connection to hardness amplification......Page 344
Local decoding......Page 346
Walsh-Hadamard Code.......Page 348
Reed-Solomon Code......Page 349
Concatenated codes......Page 350
Reed-Muller Codes.......Page 351
Berlekamp-Welch Procedure: the case of < (m-d)/(2m)......Page 352
Local decoder for Walsh-Hadamard.......Page 353
Local decoder for Reed-Muller......Page 354
Local decoding of concatenated codes.......Page 355
Putting it all together.......Page 356
List decoding......Page 357
List decoding the Reed-Solomon code......Page 358
Local list decoding: getting to BPP =P.......Page 359
Local list decoding of the Reed-Muller code......Page 360
Chapter notes and history......Page 362
Exercises......Page 364
PCP and Hardness of Approximation......Page 367
PCP and Locally Testable Proofs......Page 368
PCP and Hardness of Approximation......Page 371
Gap problems......Page 372
Constraint Satisfaction Problems......Page 373
An Alternative Formulation of the PCP Theorem......Page 374
Hardness of Approximation for 3SAT and INDSET.......Page 375
n--approximation of independent set is NP-hard.......Page 377
Tool: Linearity Testing and the Walsh-Hadamard Code......Page 379
Proof of Theorem 18.21......Page 381
PCP\'s of proximity......Page 383
Proof of the PCP Theorem.......Page 385
Gap Amplification: Proof of Lemma 18.29......Page 387
Alphabet Reduction: Proof of Lemma 18.30......Page 393
Exercises......Page 395
Parallel Repetition of PCP\'s......Page 401
Håstad\'s 3-bit PCP Theorem......Page 403
Fourier transform over GF(2)n......Page 404
Analysis of the linearity test over GF(2)......Page 406
Coordinate functions, Long code and its testing......Page 407
Proof of Theorem 19.5......Page 409
Learning Fourier Coefficients......Page 413
PCP\'s with sub-constant soundness parameter.......Page 414
Exercises......Page 415
Quantum Computation......Page 417
The 2-slit experiment......Page 418
Quantum entanglement and the Bell inequalities.......Page 419
A new view of probabilistic computation.......Page 421
Quantum superposition and the class BQP......Page 424
Spooky coordination and Bell\'s state......Page 429
Quantum programmer\'s toolkit......Page 431
Grover\'s search algorithm.......Page 432
The algorithm......Page 437
Shor\'s algorithm: integer factorization using quantum computers.......Page 438
Definition of the Fourier transform over ZM.......Page 439
Quantum Fourier transform: proof of Lemma 20.20......Page 440
The Order-Finding Algorithm.......Page 441
The case that r|M......Page 442
Reducing factoring to order finding.......Page 444
Chapter notes and history......Page 445
Exercises......Page 447
Rational approximation of real numbers......Page 448
Logic in complexity theory......Page 449
Fagin\'s definition of NP......Page 450
Resolution......Page 451
Is P = NP unproveable?......Page 452
Formal Complexity Measures......Page 453
Natural Properties......Page 455
Limitations of Natural Proofs......Page 457
My personal view......Page 458
Appendices......Page 459
Mathematical Proofs......Page 463
Sets, Functions, Pairs, Strings, Graphs, Logic.......Page 465
Probability theory......Page 466
Random variables and expectations.......Page 467
The averaging argument......Page 468
Deviation upperbounds......Page 469
Approximating the binomial coefficient......Page 471
Finite fields and groups......Page 472
Groups.......Page 473
Polynomials......Page 474