A nondeterministic space-time tradeoff for linear codes

DOI10.1016/j.ipl.2008.11.001zbMath1192.94126OpenAlexW2063729784MaRDI QIDQ976097

Stasys P. Jukna

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.11.001

zbMATH Keywords

computational complexitylinear codeslower boundsbranching programs

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Limitations of incremental dynamic programming ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Unnamed Item ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.

Cites Work

• Neither reading few bits twice nor reading illegally helps much
• A lower bound on branching programs reading some bits twice
• Time-space tradeoffs for branching programs
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• On lower bounds for read-\(k\)-times branching programs
• Expanders and time-restricted branching programs
• Time-space trade-off lower bounds for randomized computation of decision problems
• A note on read-$k$ times branching programs
• Branching Programs and Binary Decision Diagrams
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A nondeterministic space-time tradeoff for linear codes