A nondeterministic space-time tradeoff for linear codes

DOI10.1016/J.IPL.2008.11.001MaRDI QIDQ976097zbMATH OpenOpenAlexFDO

Authors Stasys 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 complexitylower boundslinear codesbranching programs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5899238
• Time-space tradeoffs for branching programs
• scientific article; zbMATH DE number 1746571
• A lower bound for the computational complexity of characteristic functions of BCH-codes by branching programs
• Neither reading few bits twice nor reading illegally helps much

Cites work

• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• scientific article; zbMATH DE number 4218008 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A lower bound on branching programs reading some bits twice
• A note on read-$k$ times branching programs
• Branching Programs and Binary Decision Diagrams
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Expanders and time-restricted branching programs
• Neither reading few bits twice nor reading illegally helps much
• On lower bounds for read-\(k\)-times branching programs
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs for branching programs

Cited in

(4)

• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Limitations of incremental dynamic programming
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976097)