Neither reading few bits twice nor reading illegally helps much
From MaRDI portal
Publication:1130185
DOI10.1016/S0166-218X(98)00042-0zbMath0903.68074OpenAlexW2054498950MaRDI QIDQ1130185
Stasys P. Jukna, Alexander A. 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
Related Items (13)
On multi-partition communication complexity ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Expanders and time-restricted branching programs ⋮ A lower bound on branching programs reading some bits twice ⋮ On uncertainty versus size in branching programs. ⋮ Arthur-Merlin games in Boolean decision trees ⋮ Yet harder knapsack problems ⋮ Limitations of incremental dynamic programming ⋮ Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ Linear codes are hard for oblivious read-once parity branching programs ⋮ Lower bounds for linearly transformed OBDDs and FBDDs
Cites Work
- 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\)
- A lower bound on branching programs reading some bits twice
- New lower bounds and hierarchy results for restricted branching programs
- On lower bounds for read-\(k\)-times branching programs
- A superpolynomial lower bound for (1,+k(n))-branching programs
- On the complexity of branching programs and decision trees for clique functions
- A note on read-$k$ times branching programs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Neither reading few bits twice nor reading illegally helps much
