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

DOI10.1007/3-540-60246-1_138zbMATH Open1193.68121OpenAlexW3140160542MaRDI QIDQ3569022FDOQ3569022

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)

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)