A superpolynomial lower bound for (1,+k(n))-branching programs

DOI10.1007/3-540-60246-1_138MaRDI QIDQ3569022zbMATH OpenOpenAlexFDO

Authors Stanislav Zak

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://www.nusl.cz/ntk/nusl-33629

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A lower bound on branching programs reading some bits twice
• Stochastic Algorithms: Foundations and Applications
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 3919835
• New lower bounds and hierarchy results for restricted branching programs

Cited in

(7)

• Neither reading few bits twice nor reading illegally helps much
• Superlinear lower bounds for bounded-width branching programs
• Expanders and time-restricted branching programs
• A lower bound on branching programs reading some bits twice
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Superpolynomial lower bounds for monotone span programs
• scientific article; zbMATH DE number 1361505 (Why is no real title available?)

This page was built for publication: A superpolynomial lower bound for \((1,+k(n))\)-branching programs

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