Boolean circuits, tensor ranks and communication complexity.
We investigate two methods for proving lower bounds on the size of small-depth circuits, namely the approaches based on multiparty communication games and algebraic characterizations extending the concepts of the tensor rank and rigidity of matrices. Our methods are combinatorial, but we think that...
| 出版年: | SIAM journal on computing. 26, 3 (1997). |
|---|---|
| 第一著者: | |
| フォーマット: | 論文 |
| 言語: | English |
| 主題: |