Meanders and their applications in lower bounds arguments (Q1115606)

Meanders are sequences of integers drawn from [n] that wander back and forth between disjoint subsets of [n] a lot. Considering various levels of wandering the authors obtain sharp lower bounds on the minimum length of meanders by means of Ramsey theoretic proof techniques. Due to these bounds the authors achieve lower bounds on the size of weak superconcentrators of depth 2, and the length of constant width branching programs as well as optimal time-space trade-offs for certain input oblivious branching programs. The ideas developed by the authors have inspired a lot of further investigations and results in proving lower bounds on the computational complexity of explicitly given functions.