scientific article; zbMATH DE number 2086405

MaRDI QIDQ4736860zbMATH OpenFDO

Authors Philipp Woelfel

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2285/22850431.htm

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• New lower bounds and hierarchy results for restricted branching programs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Lower bounds for restricted read-once parity branching programs
• scientific article; zbMATH DE number 1361505
• scientific article; zbMATH DE number 1759451

Cited in

(9)

• Almost \(k\)-wise independence and hard Boolean functions.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Lower tolerance-based branch and bound algorithms for the ATSP
• New lower bounds and hierarchy results for restricted branching programs
• Superlinear lower bounds for bounded-width branching programs
• Lower bounds for restricted read-once parity branching programs
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• scientific article; zbMATH DE number 1512688 (Why is no real title available?)
• New lower bounds and hierarchy results for restricted branching programs

This page was built for publication:

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