Lower bounds for the circuit size of partially homogeneous polynomials

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Lower bounds for the circuit size of partially homogeneous polynomials

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Lower bounds for the circuit size of partially homogeneous polynomials

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Mathematical Sciences

ISSN

1072-3374

e-ISSN

—

Svazek periodika

225

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

639-657

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85026896582