期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial f computed by an unknown/hidden arithmetic formula reconstructs, on the average, an equivalent or smaller formula in time polynomial in the size of its output .
Specifically, we consider arithmetic formulas wherein the underlying tree is a complete binary tree, the leaf nodes are labelled by affine forms (i.e. degree one polynomials) over the input variables and where the internal nodes consist of alternating layers of addition and multiplication gates. We call these alternating normal form (ANF) formulas. If a polynomial f can be computed by an arithmetic formula of size s, it can also be computed by an ANF formula , possibly of slightly larger size sO(1). Our algorithm gets as input blackbox access to the output polynomial f (i.e. for any point x in the domain, it can query the blackbox and obtain f(x) in one step) of a random ANF formula of size s (wherein the coefficients of the affine forms in the leaf nodes of are chosen independently and uniformly at random from a large enough subset of the underlying field). With high probability (over the choice of coefficients in the leaf nodes), the algorithm efficiently (i.e. in time sO(1)) computes an ANF formula of size s computing f. This then is the strongest model of arithmetic computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case.
关键词：arithmetic formulas, average case, reconstruction
