You are previewing Computational Complexity.
O'Reilly logo
Computational Complexity

Book Description

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.

Table of Contents

  1. Cover
  2. Half-title
  3. Title
  4. Copyright
  5. Dedication
  6. Contents
  7. About this book
  8. Acknowledgments
  9. Introduction
    1. Computability versus complexity
    2. QUANTIFYING COMPUTATIONAL EFFICIENCY
    3. PROVING NONEXISTENCE OF EFFICIENT ALGORITHMS
    4. SOME INTERESTING QUESTIONS ABOUT COMPUTATIONAL EFFICIENCY
  10. Chapter 0 Notational conventions
    1. Standard notation
    2. Strings
    3. Additional notation
    4. 0.1 Representing Objects as Strings
      1. Representation
      2. Representing pairs and tuples
      3. Computing functions with nonstring inputs or outputs
    5. 0.2 Decision Problems/Languages
    6. 0.3 Big-Oh Notation
    7. Exercises
  11. Part ONE Basic Complexity Classes
    1. CHAPTER 1 The computational model—and why it doesn't matter
      1. 1.1 Modeling Computation: What You Really Need to Know
      2. 1.2 The Turing Machine
        1. Scratch pad
        2. Finite set of operations/rules
        3. 1.2.1 The expressive power of Turing machines
      3. 1.3 Efficiency and Running Time
        1. 1.3.1 Robustness of our definition
      4. 1.4 Machines as Strings and the Universal Turing Machine
        1. 1.4.1 The universal Turing machine
          1. Universal TM with time bound
      5. 1.5 Uncomputability: An Introduction
        1. 1.5.1 The Halting problem (first encounter with reductions)
        2. 1.5.2 Gödel's Theorem
      6. 1.6 The Class P
        1. 1.6.1 Why the model may not matter
        2. 1.6.2 On the philosophical importance of P
        3. 1.6.3 Criticisms of P and some efforts to address them
        4. 1.6.4 Edmonds's quote
      7. 1.7 Proof of Theorem 1.9: Universal Simulation in O(TlogT)-time
        1. Encoding M’s tapes on U’s tape
        2. Performing a shift
      8. Chapter Notes and History
      9. Exercises
    2. CHAPTER 2 NP and NP completeness
      1. 2.1 The Class NP
        1. 2.1.1 Relation between NP and P
        2. 2.1.2 Nondeterministic Turing machines
      2. 2.2 Reducibility and NP-Completeness
      3. 2.3 The Cook-Levin Theorem: Computation is Local
        1. 2.3.1 Boolean formulas, CNF, and SAT
        2. 2.3.2 The Cook-Levin Theorem
        3. 2.3.3 Warmup: Expressiveness of Boolean formulas
        4. 2.3.4 Proof of Lemma 2.11
        5. 2.3.5 Reducing SAT to 3SAT
        6. 2.3.6 More thoughts on the Cook-Levin Theorem
      4. 2.4 The Web of Reductions
      5. 2.5 Decision Versus Search
      6. 2.6 CONP, EXP, and NEXP
        1. 2.6.1 coNP
        2. 2.6.2 EXP and NEXP
      7. 2.7 More thoughts about P, NP, and all that
        1. 2.7.1 The philosophical importance of NP
        2. 2.7.2 NP and mathematical proofs
        3. 2.7.3 What if P =NP?
        4. 2.7.4 What if NP =coNP?
        5. 2.7.5 Is there anything between NP and NP-complete?
        6. 2.7.6 Coping with NP hardness
        7. 2.7.7 Finer explorations of time complexity
      8. Chapter Notes and History
      9. Exercises
    3. CHAPTER 3 Diagonalization
      1. Machines as strings and the universal TM
      2. 3.1 Time Hierarchy Theorem
      3. 3.2 Nondeterministic Time Hierarchy Theorem
      4. 3.3 Ladner's Theorem: Existence of NP-intermediate problems
      5. 3.4 Oracle Machines and the Limits of Diagonalization
        1. Construction of B
        2. 3.4.1 Logical independence versus relativization
      6. Chapter Notes and History
      7. Exercises
    4. CHAPTER 4 Space complexity
      1. 4.1 Definition of Space-Bounded Computation
        1. 4.1.1 Configuration graphs
        2. 4.1.2 Some space complexity classes
        3. 4.1.3 Space Hierarchy Theorem
      2. 4.2 PSPACE Completeness
        1. 4.2.1 Savitch's Theorem
        2. 4.2.2 The essence of PSPACE: Optimum strategies for game playing
      3. 4.3 NL Completeness
        1. 4.3.1 Certificate definition of NL: Read-once certificates
        2. 4.3.2 NL =coNL
      4. Chapter Notes and History
      5. Exercises
    5. CHAPTER 5 The polynomial hierarchy and alternations
      1. 5.1 The Class…
      2. 5.2 The Polynomial Hierarchy
        1. 5.2.1 Properties of the polynomial hierarchy
        2. 5.2.2 Complete problems for levels of PH
      3. 5.3 Alternating Turing Machines
        1. 5.3.1 Unlimited number of alternations
      4. 5.4 Time versus alternations: time-space tradeoffs for sat
      5. 5.5 Defining the Hierarchy via Oracle Machines
      6. Chapter Notes and History
      7. Exercises
    6. CHAPTER 6 Boolean circuits
      1. 6.1 Boolean Circuits and P/poly
        1. 6.1.1 Relation between P/poly and P
        2. 6.1.2 Circuit satisfiability and an alternative proof of the Cook-Levin Theorem
      2. 6.2 Uniformly Generated Circuits
        1. 6.2.1 Logspace-uniform families
      3. 6.3 Turing Machines that Take Advice
      4. 6.4 P/poly and NP
      5. 6.5 Circuit Lower Bounds
      6. 6.6 Nonuniform Hierarchy Theorem
      7. 6.7 Finer Gradations Among Circuit Classes
        1. 6.7.1 The classes NC and AC
        2. 6.7.2 P-completeness
      8. 6.8 Circuits of Exponential Size
      9. Chapter Notes and History
      10. Exercises
    7. CHAPTER 7 Randomized computation
      1. 7.1 Probabilistic Turing Machines
      2. 7.2 Some Examples of PTMs
        1. 7.2.1 Finding a median
        2. 7.2.2 Probabilistic Primality Testing
        3. 7.2.3 Polynomial identity testing
        4. 7.2.4 Testing for perfect matching in a bipartite graph
      3. 7.3 One-Sidedand "Zero-Sided'' Error: RP, coRP, ZPP
      4. 7.4 The Robustness of Our Definitions
        1. 7.4.1 Role of precise constants: Error reduction
          1. Randomness-efficient repetitions
        2. 7.4.2 Expected running time versus worst-case running time
        3. 7.4.3 Allowing more general random choices than a fair random coin
      5. 7.5 Relationship between BPP and other classes
        1. 7.5.1 BPPP…/poly
        2. 7.5.2 BPP is in PH
        3. 7.5.3 Hierarchy theorems and complete problems?
          1. Complete problems for BPP?
      6. 7.6 Randomized Reductions
      7. 7.7 Randomized Space-Bounded Computation
      8. Chapter Notes and History
      9. Exercises
    8. CHAPTER 8 Interactive proofs
      1. 8.1 Interactive Proofs: Some Variations
        1. 8.1.1 Warmup: Interactive proofs with deterministic verifier and prover
        2. 8.1.2 The class IP: Probabilistic verifier
        3. 8.1.3 Interactive proof for graph nonisomorphism
      2. 8.2 Publiccoins and AM
        1. 8.2.1 Simulating private coins
        2. 8.2.2 Set lower bound protocol
          1. Tool: Pairwise independent hash functions
          2. The lower-bound protocol
        3. 8.2.3 Sketch of proof of Theorem 8.12
        4. 8.2.4 Can GI be NP-complete?
      3. 8.3 IP = PSPACE
        1. 8.3.1 Arithmetization
        2. 8.3.2 Interactive protocol for #SATD
          1. Sumcheck protocol
        3. 8.3.3 Protocol for TQBF: proof of Theorem 8.19
      4. 8.4 The Power of the Prover
      5. 8.5 Multiprover Interactive Proofs (mip)
      6. 8.6 Program Checking
        1. 8.6.1 Languages that have checkers
        2. 8.6.2 Random self-reducibility and the permanent
      7. 8.7 Interactive Proof for the Permanent
        1. 8.7.1 The protocol
      8. Chapter Notes and History
      9. Exercises
    9. CHAPTER 9 Cryptography
      1. 9.1 Perfect Secrecy and its Limitations
      2. 9.2 Computational Security, One-Way Functions, and Pseudorandom Generators
        1. 9.2.1 One way functions: Definition and some examples
        2. 9.2.2 Encryption from one-way functions
        3. 9.2.3 Pseudorandom generators
      3. 9.3 Pseudorandom Generators from One-Way Permutations
        1. 9.3.1 Unpredictability implies pseudorandomness
        2. 9.3.2 Proof of Lemma 9.10: The Goldreich-Levin Theorem
          1. Recovery for success probability 0.9
          2. Recovery for success probability 1/2 + epsilon/2
          3. Getting arbitrarily large stretch
      4. 9.4 Zero Knowledge
      5. 9.5 Some Applications
        1. 9.5.1 Pseudorandom functions and their applications
        2. 9.5.2 Derandomization
        3. 9.5.3 Tossing coins over the phone and bit commitment
        4. 9.5.4 Secure multiparty computations
        5. 9.5.5 Lower bounds for machine learning
      6. Chapter Notes and History
      7. Exercises
    10. CHAPTER 10 Quantum computation
      1. 10.1 Quantum Weirdness: The Two-Slit Experiment
      2. 10.2 Quantum Superposition and Qubits
        1. 10.2.1 EPR paradox
          1. The parity game
          2. The parity game with sharing of quantum information
      3. 10.3 Definition of Quantum Computation and BQP
        1. 10.3.1 Some necessary linear algebra
        2. 10.3.2 The quantum register and its state vector
        3. 10.3.3 Quantum operations
        4. 10.3.4 Some examples of quantum operations
        5. 10.3.5 Quantum computation and BQP
          1. Quantum versus probabilistic computation
        6. 10.3.6 Quantum circuits
        7. 10.3.7 Classical computation as a subcase of quantum computation
        8. 10.3.8 Universal operations
      4. 10.4 Grover's Search Algorithm
        1. Reflecting around e
        2. Reflecting around u
      5. 10.5 Simon's Algorithm
        1. Simon’s problem
        2. 10.5.1 Proof of Theorem 10.14
      6. 10.6 Shor's Algorithm: Integer Factorization Using Quantum Computers
        1. Shor’s ideas in nutshell
        2. 10.6.1 The Fourier transform over ZM
          1. Fast Fourier transform
        3. 10.6.2 Quantum fourier transform over ZM
        4. 10.6.3 Shor's order-finding algorithm
          1. Analysis: the case that r|M
          2. The general case
        5. 10.6.4 Reducing factoring to order finding
        6. 10.6.5 Rational approximation of real numbers
      7. 10.7 BQP and Classical Complexity Classes
        1. 10.7.1 Quantum analogs of NP and AM
      8. Chapter Notes and History
      9. Exercises
    11. CHAPTER 11 PCP theorem and hardness of approximation: An introduction
      1. 11.1 Motivation: approximate solutions to NP-hard optimization problems
      2. 11.2 Two views of the PCP Theorem
        1. 11.2.1 PCP Theorem and locally testable proofs
        2. 11.2.2 PCP and hardness of approximation
      3. 11.3 Equivalence of the Two Views
        1. 11.3.1 Equivalence of Theorems 11.5 and 11.9
        2. 11.3.2 Review of the two views of the PCP Theorem
      4. 11.4 Hardness of Approximation for Vertex Cover and Independent Set
      5. 11.5 NP .o PCP(poly(n), 1): PCP FROM THE WALSH-HADAMARD CODE
        1. 11.5.1 Tool: Linearity testing and the Walsh-Hadamard code
          1. Local testing of Walsh-Hadamard code
          2. Local decoding of Walsh-Hadamard code
        2. 11.5.2 Proof of Theorem 11.19
          1. The PCP verifier
      6. Chapter Notes and History
      7. Exercises
  12. Part TWO Lower bounds for Concrete computational models
    1. CHAPTER 12 Decision trees
      1. 12.1 Decision Trees and Decision Tree Complexity
      2. 12.2 Certificate Complexity
      3. 12.3 Randomized Decision Trees
      4. 12.4 Some Techniques for Proving Decision Tree Lower Bounds
        1. 12.4.1 Lower Bounds on Randomized Complexity
        2. 12.4.2 Sensitivity
        3. 12.4.3 The degree method
      5. Chapter Notes and History
      6. Exercises
    2. CHAPTER 13 Communication complexity
      1. 13.1 Definition of Two-Party Communication Complexity
      2. 13.2 Lower Bound Methods
        1. 13.2.1 The fooling set method
        2. 13.2.2 The tiling method
        3. 13.2.3 The rank method
        4. 13.2.4 The discrepancy method
        5. 13.2.5 A technique for upper bounding the discrepancy
        6. 13.2.6 Comparison of the lower bound methods
      3. 13.3 Multiparty Communication Complexity
        1. Discrepancy-based lower bound
      4. 13.4 Overview of Other Communication Models
      5. Chapter Notes and History
      6. Exercises
    3. CHAPTER 14 Circuit lower bounds Complexity theory’s Waterloo
      1. 14.1 AC0 AND HÅSTAD’S SWITCHING LEMMA
        1. 14.1.1 Håstad’s Switching Lemma
          1. Proving Theorem 14.1 from Lemma 14.2
        2. 14.1.2 Proof of the Switching Lemma (Lemma 14.2)
      2. 14.2 Circuits With "Counters": ACC
      3. 14.3 Lower Bounds for Monotone Circuits
        1. 14.3.1 Proving Theorem 14.7
          1. Clique indicators
          2. Approximation by clique indicators
          3. The operation f … g
          4. The operation f … g
          5. Proving Condition (b)
          6. Proof of the Sunflower Lemma (Lemma 14.10)
      4. 14.4 Circuit Complexity: The Frontier
        1. 14.4.1 Circuit lower bounds using diagonalization
        2. 14.4.2 Status of ACC versus P
        3. 14.4.3 Linear circuits with logarithmic depth
        4. 14.4.4 Branching programs
      5. 14.5 Approaches Using Communication Complexity
        1. 14.5.1 Connection to ACC0 circuits
        2. 14.5.2 Connection to linear size logarithmic depth circuits
        3. 14.5.3 Connection to branching programs
        4. 14.5.4 Karchmer-Wigderson communication games and depth lower bounds
      6. Chapter Notes and History
      7. Exercises
    4. CHAPTER 15 Proof complexity
      1. 15.1 Some Examples
      2. 15.2 Propositional Calculus and Resolution
        1. 15.2.1 Lower bounds using the bottleneck method
        2. 15.2.2 Interpolation theorems and exponential lower bounds for resolution
      3. 15.3 Other Proof Systems: A Tour D'Horizon
        1. Nullstellensatz and polynomial calculus
        2. Frege and Extended Frege
      4. 15.4 Metamathematical Musings
        1. Independence from weak theories of arithmetic
      5. Chapter Notes and History
      6. Exercises
    5. CHAPTER 16 Algebraic computation models
      1. 16.1 Algebraic Straight-Line Programs and Algebraic Circuits
        1. 16.1.1 Algebraic straight-line programs
        2. 16.1.2 Examples
        3. 16.1.3 Algebraic circuits
        4. 16.1.4 Analogs of P, NP for algebraic circuits
      2. 16.2 Algebraic Computation Trees
        1. 16.2.1 The topological method for lower bounds
      3. 16.3 The Blum-Shub-Smale Model
        1. 16.3.1 Complexity classes over the complex numbers
        2. 16.3.2 Complete problems and Hilbert's Nullstellensatz
        3. 16.3.3 Decidability Questions: Mandelbrot Set
      4. Chapter Notes and History
      5. Exercises
  13. Part THREE Advanced Topics
    1. CHAPTER 17 Complexity of counting
      1. 17.1 Examples of Counting Problems
        1. 17.1.1 Counting problems and probability estimation
        2. 17.1.2 Counting can be harder than decision
      2. 17.2 The Class #P
        1. 17.2.1 The class PP: Decision-problem analog for #P
      3. 17.3 #P Completeness
        1. 17.3.1 Permanent and Valiant's Theorem
          1. Reducing to the case of 0,1 matrices
        2. 17.3.2 Approximate solutions to #P problems
      4. 17.4 TODA.fS THEOREM: PH .o P#SAT
        1. 17.4.1 A detour: Boolean satisfiability with unique solutions
        2. 17.4.2 Properties of … and proof of Lemma 17.17 for NP, coNP
        3. 17.4.3 Proof of Lemma 17.17: General case
        4. 17.4.4 Step 2: Making the reduction deterministic
      5. 17.5 Open Problems
      6. Chapter Notes and History
      7. Exercises
    2. CHAPTER 18 Average case complexity: Levin's theory
      1. 18.1 Distributional Problems and distP
      2. 18.2 Formalization of "Real-Life Distributions"
      3. 18.3 distNP and its complete problems
        1. 18.3.1 A complete problem for distNP
        2. 18.3.2 P-samplable distributions
      4. 18.4 Philosophical and Practical Implications
      5. Chapter Notes and History
      6. Exercises
    3. CHAPTER 19 Hardness amplification and error-correcting codes
      1. 19.1 Mild to Strong Hardness: Yao's XOR Lemma
        1. 19.1.1 Proof of Yao's XOR Lemma using Impagliazzo's Hardcore Lemma
        2. 19.1.2 Proof of Impagliazzo's Lemma
      2. 19.2 Tool: Error-Correcting Codes
        1. Why half?
        2. 19.2.1 Explicit codes
        3. 19.2.2 Walsh-Hadamard code
        4. 19.2.3 Reed-Solomon code
        5. 19.2.4 Reed-Muller codes
        6. 19.2.5 Concatenated codes
      3. 19.3 Efficient Decoding
        1. 19.3.1 Decoding Reed-Solomon
        2. 19.3.2 Decoding concatenated codes
      4. 19.4 Local Decoding and Hardness Amplification
        1. 19.4.1 Local decoder for Walsh-Hadamard
        2. 19.4.2 Local decoder for Reed-Muller
        3. 19.4.3 Local decoding of concatenated codes
        4. 19.4.4 Putting it all together
      5. 19.5 List Decoding
        1. 19.5.1 List decoding the Reed-Solomon code
      6. 19.6 Local List Decoding: Getting to BPP =P
        1. 19.6.1 Local list decoding of the Walsh-Hadamard code
        2. 19.6.2 Local list decoding of the Reed-Muller code
        3. 19.6.3 Local list decoding of concatenated codes
        4. 19.6.4 Putting it all together
        5. Chapter Notes and History
        6. Exercises
    4. CHAPTER 20 Derandomization
      1. 20.1 Pseudorandom Generators and Derandomization
        1. 20.1.1 Derandomization using pseudorandom generators
        2. 20.1.2 Hardness and derandomization
      2. 20.2 Proof of Theorem 20.6: Nisan-Wigderson Construction
        1. 20.2.1 Two toy examples
          1. Extending the input by one bit using Yao’s Theorem
          2. Extending the input by two bits using the averaging principle
          3. Beyond two bits
        2. 20.2.2 The NW construction
      3. 20.3 Derandomization Under Uniform Assumptions
      4. 20.4 Derandomization Requires Circuit Lower Bounds
      5. Chapter Notes and History
      6. Exercises
    5. CHAPTER 21 Pseudorandom constructions: Expanders and extractors
      1. 21.1 Random Walks and Eigenvalues
        1. 21.1.1 Distributions as vectors and the parameter (G)
          1. Relation to eigenvalues
        2. 21.1.2 Analysis of the randomized algorithm for undirected connectivity
      2. 21.2 Expander Graphs
        1. What do we mean by a constant?
        2. 21.2.1 The algebraic definition
        3. Explicit constructions
        4. 21.2.2 Combinatorial expansion and existence of expanders
        5. 21.2.3 Algebraic expansion implies combinatorial expansion
        6. 21.2.4 Combinatorial expansion implies algebraic expansion
        7. 21.2.5 Error reduction using expanders
      3. 21.3 Explicit Construction of Expander Graphs
        1. 21.3.1 Rotation maps
        2. 21.3.2 The matrix/path product
        3. 21.3.3 The tensor product
        4. 21.3.4 The replacement product
        5. 21.3.5 The actual construction
      4. 21.4 Deterministic Logspace Algorithm for Undirected Connectivity
        1. Proof outline
        2. 21.4.1 The logspace algorithm for connectivity (proof of Theorem 21.21)
      5. 21.5 Weak Random Sources and Extractors
        1. 21.5.1 Min entropy
        2. 21.5.2 Statistical distance
        3. 21.5.3 Definition of randomness extractors
        4. 21.5.4 Existence proof for extractors
        5. 21.5.5 Extractors based on hash functions
        6. 21.5.6 Extractors based on random walks on expanders
        7. 21.5.7 Extractors from pseudorandom generators
      6. 21.6 Pseudorandom Generators for Space-Bounded Computation
      7. Chapter Notes and History
      8. Exercises
    6. CHAPTER 22 Proofs of PCP theorems and the Fourier transform technique
      1. 22.1 Constraint Satisfaction Problems with Nonbinary Alphabet
      2. 22.2 Proof of the PCP Theorem
        1. 22.2.1 Proof outline for the PCP Theorem
          1. Proving Theorem 11.5 from Lemma 22.4
        2. 22.2.2 Dinur's gap amplification: Proof of Lemma 22.5
        3. 22.2.3 Expanders, walks, and hardness of approximating INDSET
        4. 22.2.4 Dinur's gap amplification
          1. Construction of ψt
          2. The plurality assignment
          3. Analysis
        5. 22.2.5 Alphabet reduction: Proof of Lemma 22.6
          1. Concatenation test
      3. 22.3 Hardness of 2CSPW: Trade off between gap and alphabet size
        1. 22.3.1 Idea of Raz's proof: Parallel repetition
      4. 22.4 HÅSTAD’S 3-BIT PCP THEOREMAND HARDNESS OF MAX-3SAT
        1. 22.4.1 Hardness of approximating MAX-3SAT
      5. 22.5 Tool: The Fourier Transform Technique
        1. 22.5.1 Fourier transform over GF(2)n
        2. 22.5.2 The connection to PCPs: High-level view
        3. 22.5.3 Analysis of the linearity test over GF(2)
      6. 22.6 Coordinate Functions, Long Code, and its Testing
      7. 22.7 Proof of Theorem 22.16
        1. Håstad’s verifier
        2. Completeness part; easy
        3. Soundness of VH; more difficult
        4. The distribution from which π is chosen
        5. The analysis
      8. 22.8 Hardness of Approximating SET-COVER
        1. The construction
        2. The analysis
      9. 22.9 Other PCP Theorems: A Survey
        1. 22.9.1 PCP's with subconstant soundness parameter
        2. 22.9.2 Amortized query complexity
        3. 22.9.3 2-bit tests and powerful Fourier analysis
        4. 22.9.4 Unique games and threshold results
        5. 22.9.5 Connection to isoperimetry and metric space embeddings
      10. 22.A Transforming qCSP instancesinto ``nice''instances
      11. Chapter Notes and History
      12. Exercises
    7. 23 Why are circuit lower bounds so difficult?
      1. 23.1 Definition of Natural Proofs
      2. 23.2 What's So Natural About Natural Proofs?
        1. 23.2.1 Why constructiveness?
        2. 23.2.2 Why largeness?
        3. 23.2.3 Natural proofs from complexity measures
      3. 23.3 Proof of Theorem 23.1
      4. 23.4 An "Unnatural" Lower Bound
      5. 23.5 APhilosophical View
      6. Chapter Notes and History
      7. Exercises
  14. APPENDIX Mathematical background
    1. A.1 Sets, Functions, Pairs, Strings, Graphs, Logic
    2. A.2 Probability Theory
      1. Inclusion exclusion principle
      2. A.2.1 Random variables and expectations
      3. A.2.2 The averaging argument
      4. A.2.3 Conditional probability and independence
      5. A.2.4 Deviation upper bounds
      6. A.2.5 Some other inequalities
        1. Jensen’s inequality
        2. Approximating the binomial coef.cient
      7. A.2.6 Statistical distance
    3. A.3 Number Theory and Groups
      1. A.3.1 Groups
      2. A.3.2 Finite groups
      3. A.3.3 The Chinese Remainder Theorem
    4. A.4 Finite Fields
      1. A.4.1 Nonprime fields
    5. A.5 Basic Facts from Linear Algebra
      1. A.5.1 Inner product
      2. A.5.2 Dot product
      3. A.5.3 Eigenvectors and eigenvalues
      4. A.5.4 Norms
      5. A.5.5 Metric spaces
    6. A.6 Polynomials
  15. Hints for selected exercises
    1. Chapter 0
    2. Chapter 1
    3. Chapter 2
    4. Chapter 3
    5. Chapter 4
    6. Chapter 5
    7. Chapter 6
    8. Chapter 7
    9. Chapter 8
    10. Chapter 9
    11. Chapter 10
    12. Chapter 11
    13. Chapter 12
    14. Chapter 13
    15. Chapter 14
    16. Chapter 15
    17. Chapter 16
    18. Chapter 17
    19. Chapter 18
    20. Chapter 19
    21. Chapter 20
    22. Chapter 21
    23. Chapter 22
    24. Chapter 23
  16. Main theorems and definitions
  17. Bibliography
  18. Index
  19. Complexity class index