NDLI: Random arithmetic formulas can be reconstructed efficiently

Please wait, while we are loading the content...

Random arithmetic formulas can be reconstructed efficiently

Content Provider	Springer Nature Link
Author	Gupta, Ankit Qiao, Youming Kayal, Neeraj
Copyright Year	2014
Abstract	Informally stated, we present here a randomized algorithm that given black-box access to the polynomial f computed by an unknown/hidden arithmetic formula ϕ reconstructs, on the average, an equivalent or smaller formula $${\hat{\phi}}$$ in time polynomial in the size of its output $${\hat{\phi}}$$ .Specifically, we consider arithmetic formulas wherein the underlying tree is a complete binary tree, the leaf nodes are labeled 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 s O(1). Our algorithm gets as input black-box access to the output polynomial f (i.e., for any point x in the domain, it can query the black box 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 s O(1)) computes an ANF formula $${\hat{\phi}}$$ 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.
Ending Page	303
Page Count	97
Starting Page	207
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	2
Volume Number	23
Language	English
Publisher	Springer Basel
Publisher Date	2014-05-24
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Complexity classes (hierarchies, relations among complexity classes, etc.) Computational Mathematics and Numerical Analysis average case reconstruction Algorithm Analysis and Problem Complexity Arithmetic formulas Symbolic computation and algebraic computation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Random Arithmetic Formulas Can Be Reconstructed Efficiently

Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas

Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits

Factors of low individual degree polynomials

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

On the power of algebraic branching programs of width two

Fourier Concentration from Shrinkage

The Diophantine problem for systems of algebraic equations with exponents

Towards an algebraic natural proofs barrier via polynomial identity testing

Random arithmetic formulas can be reconstructed efficiently

Similar Documents

Random Arithmetic Formulas Can Be Reconstructed Efficiently

Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas

Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits

Factors of low individual degree polynomials

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

On the power of algebraic branching programs of width two

Fourier Concentration from Shrinkage

The Diophantine problem for systems of algebraic equations with exponents

Towards an algebraic natural proofs barrier via polynomial identity testing

Random arithmetic formulas can be reconstructed efficiently