A lower bound for read-once-only branching programs

DOI10.1016/0022-0000(87)90010-9zbMath0652.68062OpenAlexW2048768180MaRDI QIDQ1107323

György Turán, Péter Hajnal, Endre Szemerédi, László Babai

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90010-9

zbMATH Keywords

complexitylower boundsbranching programseraser RAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On lower bounds for read-\(k\)-times branching programs, A simple function that requires exponential size read-once branching programs, On the hierarchy of nondeterministic branching k-programs, Neither reading few bits twice nor reading illegally helps much, Paradigms for Unconditional Pseudorandom Generators, On the size of binary decision diagrams representing Boolean functions, Unnamed Item, A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs, Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs., Time-space tradeoffs for branching programs

Cites Work

• The monotone circuit complexity of Boolean functions
• A time-space tradeoff for sorting on non-oblivious machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item