Branching Programs 2/3

142 views · Published 14 March 2016 · 57:40 · Indexed 10 November 2026

Channel: Institut Henri Poincaré · 2016 · Science & Technology

Watch on YouTube

By Paul Beame (University of Washington)
Abstract: 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.

More from this channel