Abstract:
In 1977 Valiant proposed a graph theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to to proving lower bounds on the rigidity of a matrix, a concept that he introduced in that paper. In 1990 J. Friedman proved a lower bound on the rigidity of the generator matrices of error correcting codes over finite fields. He showed that the proof can be interpreted as a bound on a certain parameter defined for all linear spaces of finite dimension. In this note we define another parameter which can be used to prove lower bounds on circuits with linear gates. Our parameter may be larger than Friedman's and it seems incomparable with the rigidity, hence it may be easier to prove a lower bound using this concept.