A nondeterministic space-time tradeoff for linear codes

DOI10.1016/J.IPL.2008.11.001zbMATH Open1192.94126OpenAlexW2063729784MaRDI QIDQ976097FDOQ976097

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

Recommendations

• scientific article
• 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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
• Limitations of incremental dynamic programming

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)