Trade-off lower bounds for stack machines

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A space bounded Stack Machine is a regular Turing Machine with a read-only input tape, several space bounded read-write work tapes, and an unbounded stack. Stack Machines with a logarithmic space bound have been connected to other classical models of computation, such as polynomial time Turing Machines (P) (Cook; 1971) and polynomial size, polylogarithmic depth, bounded fan-in circuits (NC) e.g., (Borodin et al.; 1989). In this paper, we give the first known lower bound for Stack Machines. This comes in the form of a trade-off lower bound between space and number of passes over the input tape. Specifically, we give an explicit permuted inner product function such that any Stack Machine computing this function requires either sublinear polynomial space or sublinear polynomial number of passes. In the case of logarithmic space Stack Machines, this yields an unconditional sublinear polynomial lower bound for the number of passes. To put this result in perspective, we note that Stack Machines with logarithmic space and a single pass over the input can compute Parity, Majority, as well as certain languages outside NC. The latter follows from (Allender; 1989), conditional on the widely believed complexity assumption that EXP is different from PSPACE. Our technique is a novel communication complexity reduction, thereby extending the already wide range of models of computation for which communication complexity can be used to obtain lower bounds. Informally, we show that a k-player number-in-hand communication protocol for a base function f can efficiently simulate a space- and pass-bounded Stack Machine for a related function F, which consists of several permuted instances of f, bundled together by a combining function h. Trade-off lower bounds for Stack Machines then follow from known communication complexity lower bounds. The framework for this reduction was given by (Beame and Huynh-Ngoc; 2008), who used it to obtain similar trade-off lower bounds for Turing Machines with a constant number of pass-bounded external tapes. We also prove that the latter cannot efficiently simulate Stack Machines, conditional on the complexity assumption that E is not a subset of PSPACE. It is the treatment of an unbounded stack which constitutes the main technical novelty in our communication complexity reduction.

Original languageEnglish (US)
Title of host publicationProceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Pages163-171
Number of pages9
DOIs
StatePublished - 2010
Externally publishedYes
Event25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States
Duration: Jun 9 2010Jun 11 2010

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
Country/TerritoryUnited States
CityCambridge, MA
Period6/9/106/11/10

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Keywords

  • AuxPDA
  • Communication complexity
  • Lower bound
  • Reversals
  • Space bound
  • Stack
  • Streaming

Fingerprint

Dive into the research topics of 'Trade-off lower bounds for stack machines'. Together they form a unique fingerprint.

Cite this