Lower bounds for the circuit size of partially homogeneous polynomials
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F17%3A00476933" target="_blank" >RIV/67985840:_____/17:00476933 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s10958-017-3483-4" target="_blank" >http://dx.doi.org/10.1007/s10958-017-3483-4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10958-017-3483-4" target="_blank" >10.1007/s10958-017-3483-4</a>
Alternative languages
Result language
angličtina
Original language name
Lower bounds for the circuit size of partially homogeneous polynomials
Original language description
In this paper, we associate to each multivariate polynomial f that is homogeneous relative to a subset of its variables a series of polynomial families Plambda(f) of m-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in Plambda(f) is bounded from above by the circuit size of f. This provides a method for obtaining lower bounds for the circuit size of f by proving (s, r)-(weak) elusiveness of the polynomial mapping associated with Plambda(f). We discuss some algebraic methods for proving the (s, r)-(weak) elusiveness. We also improve estimates for the normal-homogeneous form of an arithmetic circuit obtained by Raz, which results in better lower bounds for circuit size. Our methods yield nontrivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Mathematical Sciences
ISSN
1072-3374
e-ISSN
—
Volume of the periodical
225
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
19
Pages from-to
639-657
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-85026896582