Meanders and their applications in lower bounds arguments

DOI10.1016/0022-0000(88)90002-5zbMath0664.68045OpenAlexW2069516228MaRDI QIDQ1115606

Wolfgang Maass, Noga Alon

Publication date: 1988

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(88)90002-5

zbMATH Keywords

computational complexitylower boundsbranching programsmeandersweak superconcentrators

Mathematics Subject Classification ID

Related Items (16)

On relations between counting communication complexity classes ⋮ On lower bounds for read-\(k\)-times branching programs ⋮ On multi-partition communication complexity ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Efficient oblivious branching programs for threshold and mod functions ⋮ Separating complexity classes related to bounded alternating ?-branching programs ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ On the complexity of planar Boolean circuits ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs ⋮ Time-space tradeoffs for branching programs ⋮ Superconcentrators of depths 2 and 3; odd levels help (rarely) ⋮ Two tapes versus one for off-line Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds to the complexity of symmetric Boolean functions
• Superconcentrators of depth 2
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines

This page was built for publication: Meanders and their applications in lower bounds arguments