Apparaît dans la collection : 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Branching programs are clean and simple non-uniform models of computation that capture both time and space simultaneously. We present the best methods known for obtaining lower bounds on the size of (length-restricted) branching programs and the applications of these methods to derive general time-space tradeoff lower bounds for specific natural problems.