Random arithmetic formulas can be reconstructed efficiently

Gupta, A; Kayal, N; Qiao, Y

Random arithmetic formulas can be reconstructed efficiently

Gupta, A Kayal, N Qiao, Y

Permalink

Publication Type:: Journal Article
Citation:: Computational Complexity, 2014, 23 (2), pp. 207 - 303
Issue Date:: 2014-01-01

Closed Access

	Filename	Description	Size
	10.1007%2Fs00037-014-0085-0.pdf	Published Version	806.31 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Gupta, A	en_US
dc.contributor.author	Kayal, N	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Computational Complexity, 2014, 23 (2), pp. 207 - 303	en_US
dc.identifier.issn	1016-3328	en_US
dc.identifier.uri	http://hdl.handle.net/10453/119936
dc.description.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 φ̌ 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 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 φ̌ 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. © 2014 Springer Basel.	en_US
dc.relation.ispartof	Computational Complexity	en_US
dc.relation.isbasedon	10.1007/s00037-014-0085-0	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Random arithmetic formulas can be reconstructed efficiently	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	23	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	1702 Cognitive Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	23	en_US

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 φ̌ 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 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 φ̌ 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. © 2014 Springer Basel.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/119936