We consider computations of linear forms over {\bf R} by

circuits with linear gates where the absolute values

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.

Comment #1 Authors: Alexander Razborov

Accepted on: 27th December 1998 18:53

Downloads: 1065

Keywords:

we show how to prove Theorem 1 on the base of previously known

results somewhat cited in TR98-042