A simple function that requires exponential size read-once branching programs
From MaRDI portal
Publication:287023
DOI10.1016/S0020-0190(97)00041-0zbMath1336.68125MaRDI QIDQ287023
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
Size of OBDD representation of 2-level redundancies functions, Almost \(k\)-wise independence and hard Boolean functions., A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs, Time-space tradeoffs for branching programs, Lower bounds for linearly transformed OBDDs and FBDDs, A very simple function that requires exponential size read-once branching programs.