A note on the use of determinant for proving lower bounds on the size of linear circuits
We consider computations of linear forms over R by circuits with linear gates where the absolute value coefficients are bounded by a constant. Also we consider a related concept of restricted rigidity of a matrix. We prove some lower bounds on the size of such circuits and the restricted rigidity of matrices in terms of the absolute value of the determinant of the matrix. (C) 2000 Elsevier Science B.V. All rights reserved.
determinant matrix computational complexity