Neither reading few bits twice nor reading illegally helps much

DOI10.1016/S0166-218X(98)00042-0MaRDI QIDQ1130185zbMATH OpenOpenAlexFDO

Authors Stasys Jukna, Alexander Razborov

Publication date 20 August 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

branching programssemantic branching programs

Mathematics Subject Classification ID

Recommendations

• Lower bounds for restricted read-once parity branching programs
• Linear codes are hard for oblivious read-once parity branching programs
• Lower bounds for nondeterministic semantic read-once branching programs
• A lower bound on branching programs reading some bits twice

Cites work

• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4218008 (Why is no real title available?)
• scientific article; zbMATH DE number 3919835 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4094813 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A lower bound for read-once-only branching programs
• A lower bound on branching programs reading some bits twice
• A note on read-$k$ times branching programs
• A superpolynomial lower bound for \((1,+k(n))\)-branching programs
• Entropy of contact circuits and lower bounds on their complexity
• New lower bounds and hierarchy results for restricted branching programs
• On lower bounds for read-\(k\)-times branching programs
• On the complexity of branching programs and decision trees for clique functions
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)

Cited in

(13)

• A nondeterministic space-time tradeoff for linear codes
• Linear codes are hard for oblivious read-once parity branching programs
• Lower bounds for linearly transformed OBDDs and FBDDs
• On uncertainty versus size in branching programs.
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
• Expanders and time-restricted branching programs
• Arthur-Merlin games in Boolean decision trees
• A lower bound on branching programs reading some bits twice
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Yet harder knapsack problems
• Limitations of incremental dynamic programming
• On multi-partition communication complexity

This page was built for publication: Neither reading few bits twice nor reading illegally helps much

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