matrix rigidity

Volume 1, Article 8 (pages 149-176)
A Non-linear Time Lower Bound for Boolean Branching Programs
by Miklós Ajtai