Computability and Complexity Symposium 2017

Bibliography

The following are readings, suggested by some of the speakers.

Computability of Julia sets:

• Braverman and Yampolsky, Computability of Julia sets, to appear in Moscow Math. Journal.

Survey papers on algortihmic randomness:

• Downey, Five lectures on algorithmic randomness, published in "Computational Prospects of Infinity", Lecture Notes Series of the Institute for Mathematical Sciences, NUS, vol. 14, World Scientific (2008).
• Downey, Algorithmic randomness and computability, proceedings of the International Congress of Mathematicians, Beijing, 2008.
• Downey, Algorithmic randomness and computability, slides from a talk at the ICM, Beijing, 2006.

Probabilistic computation:

• Chapers 7, 8, 19, 20 and 21 of Arora and Barak, Complexity Theory: A Modern Approach, to be published by Cambridge University Press, 2009.

Descriptive set theory and its interaction with analysis and dynamical systems:

The audience is encouraged to familiarise themselves with basic notions of descriptive set theory, such as Borel and analytic sets; and with the basics of model theory, in particular with Fraisse limits. Among the possible sources are

• Kechris, Classical Descriptive Set Theory (Springer, 1995)
• Hodges, Model Theory (Cambridge UP, 1993)

For further reading, look at:

• Kechris, Set theory and uniqueness for trigonometric series, preprint, 1997.
• Hjorth and Kechris, New dichotomies for Borel equivalence relations, Bull. Symb. Logic 3(3) (1997), 329-346.
• Hjorth and Kechris, Rigidity theorems for actions of product groups and countable Borel equivalence relations, Memoirs of the Amer. Math. Soc., 177, No. 833, 2005.
• Kechris, Set theory and dynamical systems, to appear in the Proceedings of the 13th International Congress of Logic, Methodology and Philosophy of Science, Beijing 2007.
• Kechris, Pestov and Todorcevic, Fraïssé limits, Ramsey theory and topological dynamics of automorphism groups, Geometric and Functional Analysis 15 (1) (2005), 106-189.