Efficient reconstruction of depth three circuits with top fan-in two
We develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials over finite fields, computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that output gate is an addition gate with in-degree two. These circuits compute polynomials of form GĂ(T_1 + T_2), where G,T_1,T_2 are product of affine forms, and polynomials T_1,T_2 have no common factors. Rank of such a circuit is defined as dimension of vector space spanned by all affine factors of T_1 and T_2. For any polynomial f computable by such a circuit, rank(f) is defined to be the minimum rank of any such circuit computing it. Our work develops randomized reconstruction algorithms which take as input black-box access to a polynomial f (over finite field đ˝), computable by such a circuit. Here are the results. 1 [Low rank]: When 5⤠rank(f) = O(log^3 d), it runs in time (nd^log^3dlog |đ˝|)^O(1), and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree ⤠d^rank(f). 2 [High rank]: When rank(f) = Ί(log^3 d), it runs in time (ndlog |đ˝|)^O(1), and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree two. Ours is the first blackbox reconstruction algorithm for this circuit class, that runs in time polynomial in log |đ˝|. This problem has been mentioned as an open problem in [GKL12] (STOC 2012)
READ FULL TEXT