RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Journal history

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Fundam. Prikl. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Fundam. Prikl. Mat., 2015, Volume 20, Issue 3, Pages 153–179 (Mi fpm1657)  

Lower bounds for the circuit size of partially homogeneous polynomials

Hông Vân Lê

Mathematical Institute, Academy of Sciences of the Czech Republic, Czech Republic

Abstract: 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 $P_\lambda(f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda(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 $P_\lambda(f)$. We discuss some algebraic methods for proving the $(s,r)$-(weak) elusiveness. We also improve estimates in 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.

Funding Agency Grant Number
Корпоративное агентство Нидерландов RVO:67985840


Full text: PDF file (296 kB)
References: PDF file   HTML file

English version:
Journal of Mathematical Sciences (New York), 2017, 225:4, 639–657

Bibliographic databases:

UDC: 510.57+510.53

Citation: Hông Vân Lê, “Lower bounds for the circuit size of partially homogeneous polynomials”, Fundam. Prikl. Mat., 20:3 (2015), 153–179; J. Math. Sci., 225:4 (2017), 639–657

Citation in format AMSBIB
\Bibitem{Le15}
\by H{\^o}ng~V{\^a}n~L\^e
\paper Lower bounds for the circuit size of partially homogeneous polynomials
\jour Fundam. Prikl. Mat.
\yr 2015
\vol 20
\issue 3
\pages 153--179
\mathnet{http://mi.mathnet.ru/fpm1657}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3519752}
\elib{http://elibrary.ru/item.asp?id=31961529}
\transl
\jour J. Math. Sci.
\yr 2017
\vol 225
\issue 4
\pages 639--657
\crossref{https://doi.org/10.1007/s10958-017-3483-4}


Linking options:
  • http://mi.mathnet.ru/eng/fpm1657
  • http://mi.mathnet.ru/eng/fpm/v20/i3/p153

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Фундаментальная и прикладная математика
    Number of views:
    This page:84
    Full text:34
    References:13

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020