A simple function that requires exponential size read-once branching programs

DOI10.1016/S0020-0190(97)00041-0zbMath1336.68125MaRDI QIDQ287023

Anna Gál

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityprojective planesread-once branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Size of OBDD representation of 2-level redundancies functions ⋮ The simplified weighted sum function and its average sensitivity ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ A very simple function that requires exponential size read-once branching programs. ⋮ Time-space tradeoffs for branching programs ⋮ Lower bounds for linearly transformed OBDDs and FBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• 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
• Parity, circuits, and the polynomial-time hierarchy
• On the complexity of branching programs and decision trees for clique functions
• A note on read-$k$ times branching programs