A superpolynomial lower bound for (1,+k(n))-branching programs
From MaRDI portal
Publication:3569022
DOI10.1007/3-540-60246-1_138zbMath1193.68121MaRDI QIDQ3569022
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
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, Expanders and time-restricted branching programs