Geodesic
Application of separability and independence notions for proving lower bounds of circuit complexity
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 38-48

Voir la notice de l'article provenant de la source Math-Net.Ru

This note consists of two independent parts. In the first part the concept of an $(m,c)$-system for a set of linear forms is introduced, and a lower bound is obtained for the algebraic complexity of the computation of $(m,c)$-systems on algebraic circuits of a special form. In the second part, the notion of an $l$-independent set of boolean functions is introduced and a lower bound is obtained for a certain complexity measure for circuits of boolean functions computing $l$-independent sets. As a corollary it is shown that the standard algorithm for multiplying matrices or polynomials may be realized by a circuit of boolean functions in a way that is optimal with respect to a selected complexity measure. 
@article{ZNSL_1976_60_a3,
     author = {D. Yu. Grigor'ev},
     title = {Application of separability and independence notions for proving lower bounds of circuit complexity},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {38--48},
     publisher = {mathdoc},
     volume = {60},
     year = {1976},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a3/}
}
TY  - JOUR
AU  - D. Yu. Grigor'ev
TI  - Application of separability and independence notions for proving lower bounds of circuit complexity
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1976
SP  - 38
EP  - 48
VL  - 60
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a3/
LA  - ru
ID  - ZNSL_1976_60_a3
ER  - 
%0 Journal Article
%A D. Yu. Grigor'ev
%T Application of separability and independence notions for proving lower bounds of circuit complexity
%J Zapiski Nauchnykh Seminarov POMI
%D 1976
%P 38-48
%V 60
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a3/
%G ru
%F ZNSL_1976_60_a3
D. Yu. Grigor'ev. Application of separability and independence notions for proving lower bounds of circuit complexity. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 38-48. http://geodesic.mathdoc.fr/item/ZNSL_1976_60_a3/