Saxena, Nitin (2008) Diagonal Circuit Identity Testing and Lower Bounds In: Automata, Languages and Programming. Part of the Lecture Notes in Computer Science book series (LNCS, volume 5125), 5125 . Springer Nature Switzerland AG, Springer, Berlin, Heidelberg, pp. 60-71.
Full text not available from this repository.
Official URL: http://doi.org/10.1007/978-3-540-70575-8_6
Related URL: http://dx.doi.org/10.1007/978-3-540-70575-8_6
Abstract
In this paper we give the first deterministic polynomial time algorithm for testing whether a diagonal depth-3 circuit C(x 1,...,x n ) (i.e. C is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only if there are exponentially many linear functions.
| Item Type: | Book Section |
|---|---|
| Source: | Copyright of this article belongs to Springer Nature Switzerland AG. |
| ID Code: | 122778 |
| Deposited On: | 16 Aug 2021 07:57 |
| Last Modified: | 16 Aug 2021 07:57 |
Repository Staff Only: item control page
