Favorite Theorems: Superlinear Bounds on Branching Programs

June Edition

Branching programs give us a nice way to model time and space bounds for Boolean functions in a simple non-uniform model. A branching program is a directed acyclic graph where every non-leaf node is labeled by a variable and has two edges labeled One and Zero. All of the leaves are labeled Accept or Reject. Given an input, one follows a path taking the One edge on a node labeled i if the ith input bit is one and the Zero edge otherwise.

The depth (length of the longest path) of the branching program represents time and log of the size represents space. Lower bounds on branching programs give us lower bounds on unrestricted computation.

In 1999, Miklós Ajtai gave the first polynomial-time computable Boolean function for which any subexponential-size deterministic branching program requires superlinear length.

A Non-Linear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai In other words there exists a specified easily computable function that cannot be solved in linear-time unless one uses nearly linear space.

Ajtai creates a function based on quadratic forms and builds on techniques used in his slightly earlier paper.

For more details I recommend the paper Time-space tradeoff lower bounds for randomized computation of decision problems by Beame, Saks, Sun and Vee which gives a nice history of the problem and the techniques to solve it and generalizes Ajtai's work to the probabilistic setting.