Index
Author Index
Ajtai, M., 69
Blum, M., 31
Chaitin, G.J., 1, 29
Goldreich, O., 31
Goldwasser, S., 30, 31
H˚astad, J., 31
Impagliazzo, R., 31, 43, 44
Kolmogorov, A., 1, 29
Komlos, J., 69
Levin, L.A., 31
Luby, M., 31
Micali, S., 30, 31
Naor, J., 69
Naor, M., 69
Nisan, N., 43, 56
Reingold, O., 56
Shannon, C.E., 1
Solomonoff, R.J., 1
Szemer´edi, E., 69
Trevisan, L., 86
Wigderson, A., 43, 44
Yao, A.C., 30, 43
Zuckerman, D., 56
Archetypical case of pseudorandom
9–34
Blum-Micali Construction, 24
Boolean Circuits, 26
constant-depth, 42
Natural Proofs, 28
Chebyshev’s Inequality, 81
Complexity classes
BPL, 51, 54–57, 104
BPP, 25–27, 35–39, 51, 93–95, 104
E, 104
EXP, 104
L, 105
NL, 54, 105
NP, 43, 103, 104
P, 103
quasi-P, 42
RL, 54, 96–97, 105
RP, 104
SC, 54
Computational Indistinguishability, 6, 11,
13, 15–19, 30
multiple samples, 16–19
non-triviality, 16
The Hybrid Technique, 17–19, 24,
30, 40
vs statistical closeness, 16
Computational Learning Theory, 28
Computational problems
Primality Testing, 93–95
Testing polynomial identity, 95–96
Undirected Connectivity, 96–97
Conceptual discussion of derandomization,
43–45
Conceptual discussion of pseudorandom-
ness, 29–34
Derandomization, 25–27, 35–45
high end, 39
low end, 39
Discrepancy sets, 66
Expander Graphs, 66, 67
random walk, 67–75
Expander random walks, 66–75
Extractors, see Randomness Extractors,
see Randomness Extractors
Fourier coefficients, 63
General paradigm of pseudorandomness,
1–9, 77–78
113
generator,
Previous Page Next Page