Polynomial identity testing for depth 3 circuits
N Kayal, N Saxena - computational complexity, 2007 - Springer
N Kayal, N Saxena
computational complexity, 2007•SpringerWe study the identity testing problem for depth 3 arithmetic circuits (∑ ∏ ∑ circuit). We give
the first deterministic polynomial time identity test for ∑ ∏ ∑ circuits with bounded top fanin.
We also show that the rank of a minimal and simple ∑ ∏ ∑ circuit with bounded top fanin,
computing zero, can be unbounded. These results answer the open questions posed by
Klivans–Spielman (STOC 2001) and Dvir–Shpilka (STOC 2005).
the first deterministic polynomial time identity test for ∑ ∏ ∑ circuits with bounded top fanin.
We also show that the rank of a minimal and simple ∑ ∏ ∑ circuit with bounded top fanin,
computing zero, can be unbounded. These results answer the open questions posed by
Klivans–Spielman (STOC 2001) and Dvir–Shpilka (STOC 2005).
Abstract
We study the identity testing problem for depth 3 arithmetic circuits ( circuit). We give the first deterministic polynomial time identity test for circuits with bounded top fanin. We also show that the rank of a minimal and simple circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans–Spielman (STOC 2001) and Dvir–Shpilka (STOC 2005).
Springer
