Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-042 | 27th July 1998 00:00

#### A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

TR98-042
Authors: Pavel Pudlak
Publication: 27th July 1998 17:29
Keywords:

Abstract:

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(s):

Comment #1 to TR98-042 | 27th December 1998 18:53

#### Comment Comment on: TR98-042

Comment #1
Authors: Alexander Razborov
Accepted on: 27th December 1998 18:53