Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem improves the known deterministic d kO(k)-time black-box identity test over rationals (Kayal & Saraf, FOCS 2009) to one that takes dO(k2)-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir & Shpilka (STOC 2005). We devise a powerful algebraic framework and develop tools to study depth-3 identities. We use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the "complexity" of the main identity. The special properties of this nucleus allow us to get almost optimal rank bounds for depth-3 identities. © 2010 IEEE.
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Pradip Bose
VTS 1998
Raymond Wu, Jie Lu
ITA Conference 2007
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum