Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme
Organisateur(s)
Date(s)
19/05/2024
Branching Programs 2/3
De Paul Beame
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.
