Found 3 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.

Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2009.1810, author = {Bienvenu, Laurent and Downey, Rod}, title = {{Kolmogorov Complexity and Solovay Functions}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {147--158}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1810}, URN = {urn:nbn:de:0030-drops-18107}, doi = {10.4230/LIPIcs.STACS.2009.1810}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

From 28.10. to 02.11.2007, the Dagstuhl Seminar 07441 ``Algorithmic-Logical Theory of Infinite Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.1, author = {Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.}, title = {{07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--13}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7441}, editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.1}, URN = {urn:nbn:de:0030-drops-14122}, doi = {10.4230/DagSemProc.07441.1}, annote = {Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

One of the important research fields of theoretical and applied
computer science and mathematics is the study of algorithmic, logical
and model theoretic properties of structures and their
interactions. By a structure we mean typical objects that arise in
computer science and mathematics such as data structures, programs,
transition systems, graphs, large databases, XML documents, algebraic
systems including groups, integers, fields, Boolean algebras and so
on.

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Summary – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.2, author = {Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.}, title = {{07441 Summary – Algorithmic-Logical Theory of Infinite Structures}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7441}, editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.2}, URN = {urn:nbn:de:0030-drops-14111}, doi = {10.4230/DagSemProc.07441.2}, annote = {Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

From 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
This is a collection of abstracts of the presentations given during the seminar.

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.1, author = {Downey, Rod and Grohe, Martin and Woeginger, Gerhard}, title = {{05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability}}, booktitle = {Exact Algorithms and Fixed-Parameter Tractability}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5301}, editor = {Rod Downey and Martin Grohe and Gerhard Woeginger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.1}, URN = {urn:nbn:de:0030-drops-4405}, doi = {10.4230/DagSemProc.05301.1}, annote = {Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Summary of the Dagstuhl Seminar held 24. July - 29. July 2005.

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Summary – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.2, author = {Downey, Rod and Grohe, Martin and Woeginger, Gerhard}, title = {{05301 Summary – Exact Algorithms and Fixed-Parameter Tractability}}, booktitle = {Exact Algorithms and Fixed-Parameter Tractability}, pages = {1--4}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5301}, editor = {Rod Downey and Martin Grohe and Gerhard Woeginger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.2}, URN = {urn:nbn:de:0030-drops-4396}, doi = {10.4230/DagSemProc.05301.2}, annote = {Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of "low for speed" oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time f(n) with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one.

Laurent Bienvenu and Rodney Downey. On Low for Speed Oracles. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2018.15, author = {Bienvenu, Laurent and Downey, Rodney}, title = {{On Low for Speed Oracles}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.15}, URN = {urn:nbn:de:0030-drops-85226}, doi = {10.4230/LIPIcs.STACS.2018.15}, annote = {Keywords: Lowness for speed, Oracle computations, Turing degrees} }

Document

**Published in:** Dagstuhl Reports, Volume 7, Issue 2 (2017)

Computability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and its applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of mathematics and theoretical computer science. The core of this theory is the analysis of relative computability and the induced degrees of unsolvability; its applications are mainly to Kolmogorov complexity and randomness as well as mathematical logic, analysis and algebra. Current research in computability theory stresses these applications and focuses on algorithmic randomness, computable analysis, computable model theory, and reverse mathematics (proof theory). Recent advances in these research directions have revealed some deep interactions not only among these areas but also with the core parts of computability theory. The goal of this Dagstuhl Seminar is to bring together researchers from all parts of computability theory and related areas in order to discuss advances in the individual areas and the interactions among those.

Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp. Computability Theory (Dagstuhl Seminar 17081). In Dagstuhl Reports, Volume 7, Issue 2, pp. 89-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{ambosspies_et_al:DagRep.7.2.89, author = {Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen}, title = {{Computability Theory (Dagstuhl Seminar 17081)}}, pages = {89--101}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {2}, editor = {Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.2.89}, URN = {urn:nbn:de:0030-drops-73540}, doi = {10.4230/DagRep.7.2.89}, annote = {Keywords: algorithmic randomness, computability theory, computable algebra, computable analysis, generic case complexity, proof mining} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 1 (2012)

Research on the notions of information and randomness has drawn on methods and ideas from computability theory and cumputational complexity, as well as core mathematical subjects like measure theory and information theory. The Dagstuhl seminar 12021 ``Computability, Complexity and Randomness'' was aimed to meet people and ideas in these areas to share new results and discuss open problems.
This report collects the material presented during the course of the seminar.

Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo. Computability, Complexity and Randomness (Dagstuhl Seminar 12021). In Dagstuhl Reports, Volume 2, Issue 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{becher_et_al:DagRep.2.1.19, author = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, title = {{Computability, Complexity and Randomness (Dagstuhl Seminar 12021)}}, pages = {19--38}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {1}, editor = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.1.19}, URN = {urn:nbn:de:0030-drops-34555}, doi = {10.4230/DagRep.2.1.19}, annote = {Keywords: algorithmic randomness, computability theory, computationl complexity, Kolmogorov complexity, algorithmic information theory} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Rodney G. Downey, Michael R. Fellows, Rolf Niedermeier, and Peter Rossmanith. Parameterized Complexity (Dagstuhl Seminar 01311). Dagstuhl Seminar Report 316, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{downey_et_al:DagSemRep.316, author = {Downey, Rodney G. and Fellows, Michael R. and Niedermeier, Rolf and Rossmanith, Peter}, title = {{Parameterized Complexity (Dagstuhl Seminar 01311)}}, pages = {1--28}, ISSN = {1619-0203}, year = {2002}, type = {Dagstuhl Seminar Report}, number = {316}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.316}, URN = {urn:nbn:de:0030-drops-152009}, doi = {10.4230/DagSemRep.316}, }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail