A nondeterministic space-time tradeoff for linear codes
type: Item
instance of: scholarly article
title: A nondeterministic space-time tradeoff for linear codes
zbMATH Open document ID: 1192.94126
published in: Information Processing Letters
publication date: 2010-06-16T00:00:00Z
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5721988
zbMATH Keywords: computational complexity
zbMATH Keywords: branching programs
zbMATH Keywords: lower bounds
zbMATH Keywords: linear codes
author: Stasys Jukna
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.11.001
OpenAlex ID: W2063729784
cites work: Determinism versus nondeterminism for linear time RAMs with memory restrictions
cites work: Q3002761
cites work: Time-space tradeoffs for branching programs
cites work: Time-space trade-off lower bounds for randomized computation of decision problems
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: A note on read-$k$ times branching programs
cites work: Expanders and time-restricted branching programs
cites work: Neither reading few bits twice nor reading illegally helps much
cites work: Q5545524
cites work: Q3364203
cites work: A lower bound on branching programs reading some bits twice
cites work: Branching Programs and Binary Decision Diagrams
DOI: 10.1016/J.IPL.2008.11.001
description: scientific article; zbMATH DE number 5721988