Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




TR98-042
Authors: Pavel Pudlak
Publication: 27th July 1998 17:29
Downloads: 2101
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
Downloads: 2137
Keywords: 


Abstract:

we show how to prove Theorem 1 on the base of previously known
results somewhat cited in TR98-042




ISSN 1433-8092 | Imprint