Algorithmic randomness and computable model theory

The project "Algorithmic randomness and computable model theory" was supported by the Austrian Science Fund FWF under the number P23989.

Summary

The project deals with two main topics. The primary work was on the interaction of randomness and computability. With various collaborators, we solved the long open Covering Problem for Martin-Löf randomness by studying the interaction of randomness and analysis. A number of related results came out of this work as well. We also did work in linear orders, equivalence relations, and effective versions of the Axiom of Choice. In linear orders, there is an old result of Watnik and Ash for countable linear orders. With collaborators, we discovered and proved the generalization for larger linear orders. In equivalence relations, we studied hyperarithmetic isomorphism of computable structures. With collaborators, we showed that this equivalence relation is naturally \Pi^1_1-complete. This is the first natural example of a relation complete at this level. The particular version of the Axiom of Choice studied is called the Finite Intersection Principle, and involves families of intersecting sets. The principle states that such families always exist. With collaborators, we investigated the computational complexity of finding such a family. We showed that, in certain circumstances, finding such a family is exactly as hard as finding a 1-generic. Later work by others removed the qualification and generalized this to all circumstances.

The second topic was parameterized complexity theory. It offers a framework for a more fine-grained complexity analysis of computational problems. Problem instances come along with a natural number, their parameter, and computational resources used by an algorithm are measured by functions in the inputs length as well as its parameter. Parameterized time and space complexity are well established research fields. We gave a theoretical foundation for a parameterized analysis of random complexity and proves various parameterized analogues of classical results. We suggested a new way how parameterizations can be introduced to propositional proof complexity. We defined natural parameterized versions of the most important strong propositional proof systems and compared their relative strength via a newly introduced notion of simulation. We also studied the question to what extent it is possible to feasibly produce problem instances which are hard for a given algorithm or proof system. We obtained some positive and some negative results. We proved a model-theoretic preservation theorem for quantified constraint satisfaction problems on certain well-behaved infinite databases. This is vital for an algebraic approach to constraint satisfaction complexity, so successful in the unquantified setting.

List of publications supported by the project

  • S. Lempp, J. Miller, S. Ng, D. Turetsky, R. Weber. Lowness for Effective Dimension. Submitted. pdf
  • D. Diamondstone, R. Downey, N. Greenberg, D. Turetsky. The Finite Intersection Principle and Genericity. Submitted. pdf
  • L. Bienvenu, N. Greenberg, A. Kučera, A. Nies, D. Turetsky. Coherent Randomness Tests and Computing K-trivial Sets. Submitted. pdf
  • R. Downey, A. Kach, S. Lempp, A. Lewis A. Montalbán, D. Turetsky. The Complexity of Computable Categoricity. Submitted. pdf
  • N. Greenberg, A. Kach, S. Lempp, D. Turetsky. Computability and Uncountable Linear Orderings II: Degree Spectra. Submitted. pdf
  • N. Greenberg, A. Kach S. Lempp, D. Turetsky. Computability and Uncountable Linear Orderings I: Computable Categoricity . To appear in the Journal of Symbolic Logic. pdf
  • N. Greenberg, D. Turetsky. Strong Jump Traceability and Demuth Randomness. Proceedings of the London Mathematical Society, 108 (2014), 738-779. pdf
  • L. Bienvenu, N. Greenberg, A. Kučera, J. Miller, A. Nies, D. Turetsky. Joining Non-Low C.E. Sets with Diagonally Non-Computable Functions. Journal of Logic and Computation, 23 (2013), 1183-1194. pdf
  • J.-A. Montoya, M. Müller. Parameterized random complexity. Theory of Computing Systems, 2012, Theory of Computing Systems 52 (2): 221-270, 2013. pdf
  • J. Flum, M. Müller. Some definitorial suggestions for parameterized proof complexity. 7th International Symposium on Parameterized and Exact Computation (IPEC), Springer LNCS 7535, pp. 73-84, 2012. here
  • Y. Chen, J. Flum, M. Müller. Hard instances of algorithms and proof systems. 8th Computability in Europe (CiE), Springer LNCS 7318, pp. 119-129, 2012. pdf
  • H. Chen, M. Müller. An algebraic preservation theorem for Aleph0 categorical quantified constraint satisfaction. 27th ACM/IEEE Symposium Logic in Computer Science (LICS), IEEE, pp. 215-224, 2012. here