DagSemProc.07411.4.pdf
- Filesize: 96 kB
- 1 pages
Document
Diagonal Circuit Identity Testing and Lower Bounds
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7411
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2008-01-22
Cite As Get BibTex
Nitin Saxena. Diagonal Circuit Identity Testing and Lower Bounds. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/DagSemProc.07411.4
Abstract
In this talk we give a deterministic polynomial time algorithm for testing whether a {em diagonal}
depth-$3$ circuit $C(arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is
zero.
Subject Classification
Keywords
- Arithmetic circuit
- identity testing
- depth 3
- depth 4
- determinant
- permanent
- lower bound
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads