Lower bounds to the complexity of symmetric Boolean functions
From MaRDI portal
Publication:914382
DOI10.1016/0304-3975(90)90080-2zbMath0701.68044OpenAlexW2038529163MaRDI QIDQ914382
Pavel Pudlák, Vojtěch Rödl, László Babai
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(90)90080-2
Related Items (8)
On lower bounds for read-\(k\)-times branching programs ⋮ On the Complexity of the Hidden Weighted Bit Function for Various BDD Models ⋮ Meanders and their applications in lower bounds arguments ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Unexpected upper bounds on the complexity of some communication games ⋮ Functions that have read-once branching programs of quadratic size are not necessarily testable ⋮ On the complexity of planar Boolean circuits ⋮ Two tapes versus one for off-line Turing machines
Cites Work
This page was built for publication: Lower bounds to the complexity of symmetric Boolean functions
