The Library
Tree evaluation is in space
Tools
Cook, James and Mertz, Ian (2024) Tree evaluation is in space. In: STOC ’24 : 56th ACM Symposium on Theory of Computing, Vancouver, BC, Canada, 24–28 Jun 2024. Published in: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24) ISBN 9798400703836. doi:https://doi.org/10.1145/3618260.3649664 (In Press)
PDF
WRAP-Tree-evaluation-is-in-Space- - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (732Kb) |
Official URL: https://doi.org/https://doi.org/10.1145/3618260.36...
Abstract
The Tree Evaluation Problem (TreeEval) (Cook et al. 2009) is a central candidate for separating polynomial time (P) from logarithmic
space (L) via composition. While space lower bounds of Ω(log2
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Alternative Title: | |||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24) | ||||||
Publisher: | ACM | ||||||
ISBN: | 9798400703836 | ||||||
Official Date: | 2024 | ||||||
Dates: |
|
||||||
DOI: | https://doi.org/10.1145/3618260.3649664 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | In Press | ||||||
Re-use Statement: | © ACM, 2024. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145//3618260.3649664 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Copyright Holders: | © 2024 Copyright held by the owner/author(s) | ||||||
Date of first compliant deposit: | 29 April 2024 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | STOC ’24 : 56th ACM Symposium on Theory of Computing | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Vancouver, BC, Canada | ||||||
Date(s) of Event: | 24–28 Jun 2024 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |