Neither reading few bits twice nor reading illegally helps much

DOI10.1016/S0166-218X(98)00042-0zbMATH Open0903.68074OpenAlexW2054498950MaRDI QIDQ1130185FDOQ1130185

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

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

zbMATH Keywords

branching programssemantic branching programs

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower bound for read-once-only branching programs
• Entropy of contact circuits and lower bounds on their complexity
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• On lower bounds for read-\(k\)-times branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of branching programs and decision trees for clique functions
• Title not available (Why is that?)
• A note on read-$k$ times branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower bound on branching programs reading some bits twice
• New lower bounds and hierarchy results for restricted branching programs
• A superpolynomial lower bound for \((1,+k(n))\)-branching programs

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)