期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-31
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper 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 top(output) gate is an addition gate with indegree 2. Such circuits naturally compute polynomials of the form G×(T1 T2), where G, T1, T2 are product of affine forms computed at the first(addition) layer in the circuit, and polynomials T1, T2 have no common factors. Rank of such a circuit is defined to be the dimension of vector space spanned by all affine factors of T1 and T2. 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 algorithms, which take as input a black-box computing polynomial f, with coefficients in a finite field F, exhibiting such a circuit. Here are the results. • [Low rank] ∶ When 5 ≤ r = rank(f) = O(log3 d), it runs in time (ndlog3 d log ∣F∣)O(1) and outputs a depth three circuit computing f (with high probability), with top addition gate having in-degree ≤ d rank(f) . • [High rank] ∶ When rank(f) = Ω(log3 d), it runs in time (nd log ∣F∣)O(1) , and with high probability outputs a depth three circuit computing f, with top addition gate having in-degree 2. Prior to our work, black-box reconstruction for this circuit class was addressed in [Shp07, KS09, Sin16b]. Reconstruction algorithm in [Shp07] runs in time quasi-polynomial in n, d, ∣F∣ and that in [KS09] is quasi-polynomial in d, ∣F∣. Algorithm in [Sin16b] works only for polynomials over characteristic zero fields. Thus ours is the first blackbox reconstruction algorithm for this class of circuits that runs in time polynomial in log ∣F∣. This problem has been mentioned as an open problem in [GKL12] (STOC 2012). In the high rank case, our algorithm runs in (nd log ∣F∣)O(1) time, thereby significantly improving the existing algorithms in [Shp07, KS09].
