A lower bound for read-once-only branching programs

DOI10.1016/0022-0000(87)90010-9zbMATH Open0652.68062OpenAlexW2048768180MaRDI QIDQ1107323FDOQ1107323

Authors: Péter Hajnal, Gy. Turán, László Babai, Endre Szemerédi 

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

Recommendations

• scientific article; zbMATH DE number 549860
• The optimal read-once branching program complexity for the direct storage access function
• A very simple function that requires exponential size read-once branching programs.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 3890736

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The monotone circuit complexity of Boolean functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A time-space tradeoff for sorting on non-oblivious machines
• Title not available (Why is that?)

Cited In (19)

• Neither reading few bits twice nor reading illegally helps much
• Paradigms for Unconditional Pseudorandom Generators
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• Title not available (Why is that?)
• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor
• On the size of binary decision diagrams representing Boolean functions
• Title not available (Why is that?)
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• On lower bounds for read-\(k\)-times branching programs
• Time-space tradeoffs for branching programs
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• Title not available (Why is that?)
• Read-Once Branching Programs for Tree Evaluation Problems
• Title not available (Why is that?)
• On the hierarchy of nondeterministic branching k-programs
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs

This page was built for publication: A lower bound for read-once-only branching programs

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