book Lectures

There are no user-defined tags in this book. You can tag content in a chapter by typing #tag_name (e.g. #important) anywhere in your personal notes.
1  Course Overview, and How to TCS
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
2  Basic Asymptotics
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
3  Factorials and Binomial Coefficients
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
4  Central Limit Theorem
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
5  Chernoff Bounds
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
6  Computational Models
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
7  Fast Multiplication with the DFT
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
8  Analysis of Boolean Functions
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
9  Quantum Computation
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
10  Fields and Polynomials
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
11  Error-Correcting Codes
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
12  Derandomization
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
13  Spectral Graph Theory I
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
14  Spectral Graph Theory II
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
15  Spectral Graph Theory III
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
15.1  Cheeger's Inequality (Spectral Graph Theory bonus)
» Preamble
» Page 1
» Page 2
» Page 3
16  Expander Graphs
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
17  Linear Programming I
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
18  Linear Programming II
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
19  The Ellipsoid Algorithm
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
20  CSPs and Approximation
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
21  LP Hierarchies and Proof Systems
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
22  Treewidth
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
» Page 84
» Page 85
» Page 86
» Page 87
» Page 88
» Page 89
» Page 90
» Page 91
» Page 92
» Page 93
» Page 94
» Page 95
» Page 96
23  Communication Complexity
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
» Page 84
» Page 85
» Page 86
» Page 87
» Page 88
» Page 89
» Page 90
» Page 91
» Page 92
» Page 93
» Page 94
» Page 95
» Page 96
» Page 97
» Page 98
» Page 99
» Page 100
» Page 101
» Page 102
» Page 103
» Page 104
» Page 105
» Page 106
» Page 107
» Page 108
» Page 109
» Page 110
» Page 111
» Page 112
» Page 113
» Page 114
» Page 115
» Page 116
» Page 117
» Page 118
» Page 119
» Page 120
» Page 121
» Page 122
» Page 123
» Page 124
» Page 125
» Page 126
» Page 127
» Page 128
» Page 129
» Page 130
» Page 131
» Page 132
» Page 133
24  Information Theory
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
» Page 84
» Page 85
» Page 86
» Page 87
» Page 88
» Page 89
» Page 90
» Page 91
» Page 92
» Page 93
» Page 94
» Page 95
» Page 96
» Page 97
» Page 98
» Page 99
» Page 100
» Page 101
» Page 102
» Page 103
25  Cryptography
» Preamble
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
» Page 84
» Page 85
» Page 86
» Page 87
» Page 88
» Page 89
» Page 90
» Page 91
» Page 92
» Page 93
» Page 94
26  Hardness Assumptions
» Page 1
» Page 2
» Page 3
» Page 4
» Page 5
» Page 6
» Page 7
» Page 8
» Page 9
» Page 10
» Page 11
» Page 12
» Page 13
» Page 14
» Page 15
» Page 16
» Page 17
» Page 18
» Page 19
» Page 20
» Page 21
» Page 22
» Page 23
» Page 24
» Page 25
» Page 26
» Page 27
» Page 28
» Page 29
» Page 30
» Page 31
» Page 32
» Page 33
» Page 34
» Page 35
» Page 36
» Page 37
» Page 38
» Page 39
» Page 40
» Page 41
» Page 42
» Page 43
» Page 44
» Page 45
» Page 46
» Page 47
» Page 48
» Page 49
» Page 50
» Page 51
» Page 52
» Page 53
» Page 54
» Page 55
» Page 56
» Page 57
» Page 58
» Page 59
» Page 60
» Page 61
» Page 62
» Page 63
» Page 64
» Page 65
» Page 66
» Page 67
» Page 68
» Page 69
» Page 70
» Page 71
» Page 72
» Page 73
» Page 74
» Page 75
» Page 76
» Page 77
» Page 78
» Page 79
» Page 80
» Page 81
» Page 82
» Page 83
» Page 84