Tradeoff lower lounds for stack machines

DOI10.1007/s00037-012-0057-1zbMath1366.68055OpenAlexW2146634436MaRDI QIDQ744614

Periklis A. Papakonstantinou, Matei David

Publication date: 25 September 2014

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0057-1

zbMATH Keywords

lower boundTuring machinecommunication complexityreversalsstackstreamingAuxPDAspace bound

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Reversal complexity revisited
• Tree-size bounded alternation
• On uniform circuit complexity
• Properties that characterize LOGCFL
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The space complexity of approximating the frequency moments
• P-uniform circuit complexity
• Lower bounds for randomized read/write stream algorithms
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Two Applications of Inductive Counting for Complementation Problems
• Reversal Complexity
• Tally languages and complexity classes
• Communication Complexity
• Computational Complexity
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers