Summer School in Algorithmic Randomness
Gainesville, Florida, June 9-19, 2008.

1. Review of computational complexity concepts.
   • time complexity: DTIME[t(n)], P, E, EXP
   • space complexity: DSPACE[s(n)], PSPACE, ESPACE
   • circuit complexity: SIZE[s(n)], P/poly = PSIZE
   • randomized complexity: BPP, RP, ZPP
   • efficiently checkable proofs: NP, MA, AM
   • polynomial-time reductions and completeness
   • complexity of real-valued functions

2. Measure and dimension in complexity classes.
   • Viewing decision problems as elements of Cantor space (infinite binary sequences).
   • Viewing complexity classes as subsets of Cantor space.
   • Resource-bounded martingales: p = polynomial-time, qp = quasipolynomial-time, pspace = polynomial-space.
   • Notions of success for martingales: growth rates, strong success, weak success.
   • Resource-bounded versions of Lebesgue measure, Hausdorff dimension, packing dimension, and scaled dimension. Varying the resource bound gives measure and dimension concepts that are useful within different complexity classes.
     • p-martingales yield p-measure and p-dimension for E.
     • qp-martingales yield qp-measure and qp-dimension for EXP.
     • pspace-martingales yield pspace-measure and pspace-dimension for ESPACE.
   • Resource-bounded randomness: p-randomness, qp-randomness, pspace-randomness.

3. Introductory examples.
   • P has dimension 0 in E.
   • E has measure 1 in E.
   • P-bi-immune sets have measure 1 in E.
   • For each c ≥ 1, the circuit class SIZE[n^c] has dimension 0 in EXP.
   • SIZE[2ⁿ/n] has measure 0 in ESPACE.
   • For each 0 ≤ α ≤ 1, SIZE[α 2ⁿ/n] has dimension α in ESPACE.

4. Techniques for constructing martingales.
   • Fundamental techniques: betting and density arguments.
   • Borel-Cantelli lemma.
   • Exact computation lemma.
   • Computational learning algorithms.
   • Approximate counting.

5. Resource-bounded Kolmogorov complexity and compressibility.
   • Time-bounded complexity, space-bounded complexity, and variations due to Levin, Sipser, and Allender.
   • Equivalent definition of pspace-dimension using polynomial-space Kolmogorov complexity.
   • Open: can p-Kolmogorov complexity be used to define p-dimension?
   • Polynomial-time compressibility and p-dimension.
   • Randomness extractors and dimension 0-1 laws.

6. A sampling of applications.
   • Derandomization and natural proofs.
   • Hypotheses on NP and their consequences.
   • Kolmogorov complexity and the NP-machine hypothesis.
   • Degrees, lower spans, weakly complete sets.
   • Lower bounds for the density of hard sets.
   • ...

1. Survey Papers
   • The Quantitative Structure of Exponential Time.
     Jack Lutz, 1997.
     [ PostScript ]

   • Resource-Bounded Measure and Randomness.
     Klaus Ambos-Spies and Elvira Mayordomo, 1997.
     [ PostScript (gzipped) ]

   • Twelve Problems in Resource-Bounded Measure.
     Jack Lutz and Elvira Mayordomo, 1999.
     [ PostScript ]

     The Fractal Geometry of Complexity Classes.
     John Hitchcock, Jack Lutz, and Elvira Mayordomo, 2005.
     [ Abstract | PostScript | PDF ]

2. Bibliographies
   • Resource-Bounded Measure
   • Effective Fractal Dimension