A nondeterministic space-time tradeoff for linear codes
From MaRDI portal
Publication:976097
DOI10.1016/j.ipl.2008.11.001zbMath1192.94126OpenAlexW2063729784MaRDI QIDQ976097
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
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