See also John Hitchcock's bibliographies of effective fractal dimension and resource-bounded measure.

Eric Allender maintains a page of just his publications that are related to Kolmogorov complexity.

George Barmpalias' publication page.

Steve Simpson's publication page (papers from 2000 on).

G. Barmpalias, Computably enumerable sets in the Solovay and the Strong Weak Truth Table Degrees, LNCS Volume 3526, proceedings of the CiE conference 2005 conference in Amsterdam (2005) 8-17.

G. Barmpalias, Random Non-Cupping Revisited, Journal of Complexity 22 (2006) 850-857.

George Barmpalias, Paul Brodhead, Douglas Cenzer, Seyyed Dashti and Rebecca Weber, Algorithmic Randomness of Closed Sets, to appear in Journal of Logic and Computation.

G. Barmpalias, D. Cenzer, J. Remmel and R. Weber, K-trivial closed sets and continuous functions, CIE 2007, Computation and Logic in the Real World, Third Conference on Computability in Europe, Siena, Italy, June 2007, S.B. Cooper, B. Loewe and A. Sorbi (Eds.), Springer Lecture Notes in Computer Science 4497 (2007), 135-145.

George Barmpalias and Andy Lewis, Randomness and the Linear degrees of computability, Annals of Pure and Applied Logic Volume 145, Issue 3, (2007), pages 252-257.

George Barmpalias and Andy Lewis, A c.e. real that cannot be sw-computed by any omega number, Notre Dame Journal of Formal Logic Volume 47 Issue 2 (2006).

George Barmpalias and Andy Lewis, Random Reals and Lipschitz Continuity, Mathematical Structures in Computer Science Volume 16, issue 5 (2006).

George Barmpalias and Andy Lewis, The ibT Degrees of C.E. Sets are Not Dense, Annals of Pure and Applied Logic Volume 141, Issues 1-2, 2006.

George Barmpalias, Andy Lewis, and Mariya Soskova, Working with the LR Degrees, Theory and Applications of Models of Computation: 4th International Conference TAMC 2007, Shanghai, China, May 2007, Proceedings (J.-Y. Cai, S.B. Cooper, H. Zhu, eds.), Springer Lecture Notes in Computer Science, LNCS 4484, 2007.

George Barmpalias, Andy Lewis, and Mariya Soskova, Randomness, Lowness and Degrees, to appear in Journal of Symbolic Logic.

George Barmpalias and Antonio Montalban, A cappable almost everywhere dominating computably enumerable degree, Electronic Notes in Theoretical Computer Science Volume 167 (2007).

Bienvenu, Laurent, David Doty, and Frank Stephan, Constructive dimension and weak truth-table degrees. Accepted to Computation and Logic in the Real World, Proceedings of the 3rd Conference on Computability in Europe (CiE), 2007. preprint pdf, arXiv pdf.

Binns, Stephen, Π⁰₁ classes with complex elements. dvi, pdf.

Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson, Vitali's theorem and WWKL, Archive for Mathematical Logic, 41, 2002, pp. 191-206.

J. Chisholm, J. Chubb, V. S. Harizanov, D. R. Hirschfeldt, C. G. Jockusch, Jr., T. McNicholl, and S. Pingrey, Pi⁰₁ classes and strong degree spectra of relations, Journal of Symbolic Logic 72 (2007) 1003 - 1018.

Natasha L. Dobrinen and Stephen G. Simpson, Almost everywhere domination, Journal of Symbolic Logic, 69, 2004, pp. 914-922.

R. G. Downey, D. R. Hirschfeldt, and G. LaForte, Randomness and reducibility, Journal of Computer and System Sciences 68 (2004), 96 - 114 (extended abstract in J. Sgall, A. Pultr, and P. Kolman (eds.), Mathematical Foundations of Computer Science 2001, Lecture Notes in Computer Science 2136 (Springer, 2001), 316 - 327).

R. Downey, D. R. Hirschfeldt, and G. LaForte, Undecidability of the structure of the Solovay degrees of c.e. reals, Journal of Computer and System Sciences 73 (2007) 769 - 787.

R. Downey, D. R. Hirschfeldt, J. S. Miller, and A. Nies, Relativizing Chaitin's halting probability, Journal of Mathematical Logic 5 (2005) 167 - 192.

R. G. Downey, D. R. Hirschfeldt, and A. Nies, Randomness, computability, and density, SIAM Journal on Computing 31 (2002) 1169 - 1183 (extended abstract in A. Ferreira and H. Reichel (eds.), STACS 2001 Proceedings, Lecture Notes in Computer Science 2010 (Springer, 2001)).

R. G. Downey, D. R. Hirschfeldt, A. Nies, and F. Stephan, Trivial reals, in R. Downey, D. Decheng, T. S. Ping, Q. Y. Hui, and M. Yasugi (eds.), Proceedings of the 7th and 8th Asian Logic Conferences (Singapore University Press and World Scientific, 2003) 103 - 131 (extended abstract in Electronic Notes in Theoretical Computer Science 66).

Downey, Rod, Andre Nies, Rebecca Weber, and Liang Yu, Lowness and Π⁰₂ nullsets. Journal of Symbolic Logic, 71(3):1044-1052, 2006. pdf.

R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn, Calibrating randomness, Bulletin of Symbolic Logic 12 (2006) 411 - 491.

D. R. Hirschfeldt, A. Nies, and F. Stephan, Using random sets as oracles, Journal of the London Mathematical Society 75 (2007) 610 - 622.

D. R. Hirschfeldt and S. A. Terwijn, Limit computability and constructive measure, to appear in the proceedings of the Program on Computational Prospects of Infinity, Singapore 2005.

Kastermans, Bart, and Steffen Lempp, Comparing notions of randomness. pdf.

Mayordomo, Elvira, Pushdown compression and dimension. pdf.

Stephen G. Simpson, Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, 1999, XIV + 445 pages.

Stephen G. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic, 11, 2005, pp. 1-27.

Stephen G. Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society, 75, 2007, pp. 287-297.

Stephen G. Simpson, Almost everywhere domination and superhighness, Mathematical Logic Quarterly, 53, 2007, pp. 462-482.

Stephen G. Simpson, Mass problems and almost everywhere domination, Mathematical Logic Quarterly, 53, 2007, pp. 483-492.

Xiaokang Yu and Stephen G. Simpson, Measure theory and weak Koenig's lemma, Archive for Mathematical Logic, 30, 1990, pp. 171-180.

Back to main FRG webpage

Last modified September 28, 2007