Search Results

Documents authored by Kinne, Jeff


Document
Space Hierarchy Results for Randomized Models

Authors: Jeff Kinne and Dieter van Melkebeek

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following. Let $s(n)$ be any space-constructible function that is $Omega(log n)$ and such that $s(a n) = O(s(n))$ for all constants $a$, and let $s'(n)$ be any function that is $omega(s(n))$. - There exists a language computable by two-sided error randomized machines using $s'(n)$ space and one bit of advice that is not computable by two-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. - There exists a language computable by zero-sided error randomized machines in space $s'(n)$ with one bit of advice that is not computable by one-sided error randomized machines using $s(n)$ space and $min(s(n),n)$ bits of advice. The condition that $s(a n)=O(s(n))$ is a technical condition satisfied by typical space bounds that are at most linear. We also obtain weaker results that apply to generic semantic models of computation.

Cite as

Jeff Kinne and Dieter van Melkebeek. Space Hierarchy Results for Randomized Models. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 433-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kinne_et_al:LIPIcs.STACS.2008.1363,
  author =	{Kinne, Jeff and van Melkebeek, Dieter},
  title =	{{Space Hierarchy Results for Randomized Models}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1363},
  URN =		{urn:nbn:de:0030-drops-13636},
  doi =		{10.4230/LIPIcs.STACS.2008.1363},
  annote =	{Keywords: Computations with Advice, Space Hierarchy, Randomized Machine, Promise Classes, Semantic Models}
}
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