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

DOI10.1007/3-540-60246-1_138zbMath1193.68121OpenAlexW3140160542MaRDI QIDQ3569022

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)

Related Items (4)

Expanders and time-restricted branching programs ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ A lower bound on branching programs reading some bits twice ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

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