ECCC-Report TR98-042https://eccc.weizmann.ac.il/report/1998/042Comments and Revisions published for TR98-042en-usSun, 27 Dec 1998 18:53:00 +0200
Comment 1
| Comment Comment on: TR98-042 |
Alexander Razborov
https://eccc.weizmann.ac.il/report/1998/042#comment1we show how to prove Theorem 1 on the base of previously known
results somewhat cited in TR98-042
Sun, 27 Dec 1998 18:53:00 +0200https://eccc.weizmann.ac.il/report/1998/042#comment1
Paper TR98-042
| A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits |
Pavel Pudlak
https://eccc.weizmann.ac.il/report/1998/042
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.
Mon, 27 Jul 1998 17:29:34 +0300https://eccc.weizmann.ac.il/report/1998/042