4 Search Results for "Downey, Rodney"

Document
DOI: 10.4230/LIPIcs.STACS.2018.15
On Low for Speed Oracles

Authors: Laurent Bienvenu and Rodney Downey

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/DagRep.7.2.89
Computability Theory (Dagstuhl Seminar 17081)

Authors: Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/DagRep.2.1.19
Computability, Complexity and Randomness (Dagstuhl Seminar 12021)

Authors: Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/DagSemRep.316
Parameterized Complexity (Dagstuhl Seminar 01311)

Authors: Rodney G. Downey, Michael R. Fellows, Rolf Niedermeier, and Peter Rossmanith

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

Abstract
Cite as

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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.316},
  URN =		{urn:nbn:de:0030-drops-152009},
  doi =		{10.4230/DagSemRep.316},
}
  • Refine by Author
  • 3 Downey, Rodney
  • 2 Bienvenu, Laurent
  • 1 Ambos-Spies, Klaus
  • 1 Becher, Veronica
  • 1 Brattka, Vasco
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 algorithmic randomness
  • 2 computability theory
  • 1 Kolmogorov complexity
  • 1 Lowness for speed
  • 1 Oracle computations
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2002
  • 1 2012
  • 1 2017
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact