On the Validity of the Direct Sum Conjecture
The direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of com...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | article |
| منشور في: |
2016
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/3520 http://dx.doi.org/10.1137/0215071 http://epubs.siam.org/doi/abs/10.1137/0215071 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513461366554624 |
|---|---|
| author | Takche, Jean |
| author2 | Ja'ja', Joseph |
| author2_role | author |
| author_facet | Takche, Jean Ja'ja', Joseph |
| author_role | author |
| dc.creator.none.fl_str_mv | Takche, Jean Ja'ja', Joseph |
| dc.date.none.fl_str_mv | 2016-04-08T11:10:38Z 2016-04-08T11:10:38Z 2016-04-08 |
| dc.identifier.none.fl_str_mv | 0097-5397 http://hdl.handle.net/10725/3520 http://dx.doi.org/10.1137/0215071 Ja'Ja', J., & Takche, J. (1986). On the validity of the direct sum conjecture. SIAM Journal on Computing, 15(4), 1004-1020. http://epubs.siam.org/doi/abs/10.1137/0215071 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | SIAM Journal on Computing |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the Validity of the Direct Sum Conjecture |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | The direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of computations. One such class can be defined as follows. Let $S_1 $ be a set of r$m \times n$ bilinear forms, and let $S_2 $ be a different set of s$p \times q$ bilinear forms. Then, if $2 \in \{ r,m,n,s,p,q\} $, we show that the direct sum conjecture holds over any field. The proof involves some nontrivial facts from linear algebra and relies on the theory of invariant polynomials. This result also settles the multiplicative complexity of pairs of bilinear forms over any field with large enough cardinality. It is also shown that the direct sum conjecture is true for the case when $r = mn - 2$. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_a35e960470a885dbe905aa4adb720eb7 |
| identifier_str_mv | 0097-5397 Ja'Ja', J., & Takche, J. (1986). On the validity of the direct sum conjecture. SIAM Journal on Computing, 15(4), 1004-1020. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/3520 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the Validity of the Direct Sum ConjectureTakche, JeanJa'ja', JosephThe direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of computations. One such class can be defined as follows. Let $S_1 $ be a set of r$m \times n$ bilinear forms, and let $S_2 $ be a different set of s$p \times q$ bilinear forms. Then, if $2 \in \{ r,m,n,s,p,q\} $, we show that the direct sum conjecture holds over any field. The proof involves some nontrivial facts from linear algebra and relies on the theory of invariant polynomials. This result also settles the multiplicative complexity of pairs of bilinear forms over any field with large enough cardinality. It is also shown that the direct sum conjecture is true for the case when $r = mn - 2$.PublishedN/A2016-04-08T11:10:38Z2016-04-08T11:10:38Z2016-04-08Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0097-5397http://hdl.handle.net/10725/3520http://dx.doi.org/10.1137/0215071Ja'Ja', J., & Takche, J. (1986). On the validity of the direct sum conjecture. SIAM Journal on Computing, 15(4), 1004-1020.http://epubs.siam.org/doi/abs/10.1137/0215071enSIAM Journal on Computinginfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/35202020-03-12T07:46:26Z |
| spellingShingle | On the Validity of the Direct Sum Conjecture Takche, Jean |
| status_str | publishedVersion |
| title | On the Validity of the Direct Sum Conjecture |
| title_full | On the Validity of the Direct Sum Conjecture |
| title_fullStr | On the Validity of the Direct Sum Conjecture |
| title_full_unstemmed | On the Validity of the Direct Sum Conjecture |
| title_short | On the Validity of the Direct Sum Conjecture |
| title_sort | On the Validity of the Direct Sum Conjecture |
| url | http://hdl.handle.net/10725/3520 http://dx.doi.org/10.1137/0215071 http://epubs.siam.org/doi/abs/10.1137/0215071 |