Matematicheskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Sb., 2012, Volume 203, Number 10, Pages 33–70 (Mi msb7904)  

This article is cited in 6 scientific papers (total in 6 papers)

A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

S. B. Gashkov*, I. S. Sergeev

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis $\{x+y,  x \cdot y\}\cup\{a \cdot x\mid a\in \mathbb R_+\}$. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree $m-1$ in each of the $n$ variables with coefficients 0 and 1 having additive monotone complexity $m^{(1-o(1))n}$ and multiplicative monotone complexity $m^{(1/2-o(1))n}$ as $m^n \to \infty$. In this form, the lower bounds derived here are sharp.
Bibliography: 72 titles.

Keywords: lower bounds for complexity, arithmetic circuits, thin sets, monotone complexity, permanent.
* Author to whom correspondence should be addressed

DOI: https://doi.org/10.4213/sm7904

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

English version:
Sbornik: Mathematics, 2012, 203:10, 1411–1447

Bibliographic databases:

UDC: 519.61+519.71
MSC: Primary 03D15; Secondary 68Q15, 68Q17
Received: 29.06.2011 and 11.04.2012

Citation: S. B. Gashkov, I. S. Sergeev, “A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials”, Mat. Sb., 203:10 (2012), 33–70; Sb. Math., 203:10 (2012), 1411–1447

Citation in format AMSBIB
\Bibitem{GasSer12}
\by S.~B.~Gashkov, I.~S.~Sergeev
\paper A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
\jour Mat. Sb.
\yr 2012
\vol 203
\issue 10
\pages 33--70
\mathnet{http://mi.mathnet.ru/msb7904}
\crossref{https://doi.org/10.4213/sm7904}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3027137}
\zmath{https://zbmath.org/?q=an:06134393}
\elib{https://elibrary.ru/item.asp?id=19066328}
\transl
\jour Sb. Math.
\yr 2012
\vol 203
\issue 10
\pages 1411--1447
\crossref{https://doi.org/10.1070/SM2012v203n10ABEH004270}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000312249700002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84872310866}


Linking options:
  • http://mi.mathnet.ru/eng/msb7904
  • https://doi.org/10.4213/sm7904
  • http://mi.mathnet.ru/eng/msb/v203/i10/p33

    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

    This publication is cited in the following articles:
    1. S. Jukna, “Lower bounds for tropical circuits and dynamic programs”, Theory Comput. Syst., 57:1 (2015), 160–194  crossref  mathscinet  zmath  isi  elib  scopus
    2. S. Jukna, “Tropical complexity, Sidon sets, and dynamic programming”, SIAM J. Discrete Math., 30:4 (2016), 2064–2085  crossref  mathscinet  zmath  isi  scopus
    3. S. Jukna, “Lower bounds for monotone counting circuits”, Discrete Appl. Math., 213 (2016), 139–152  crossref  mathscinet  zmath  isi  scopus
    4. S. Jukna, “Minkowski complexity of sets: an easy lower bound”, Am. Math. Mon., 124:8 (2017), 749–753  crossref  mathscinet  zmath  isi  scopus
    5. Jukna S., Seiwert H., “Approximation Limitations of Pure Dynamic Programming”, SIAM J. Comput., 49:1 (2020), 170–205  crossref  mathscinet  zmath  isi
    6. Srinivasan S., “Strongly Exponential Separation Between Monotone Vp and Monotone Vnp”, ACM Trans. Comput. Theory, 12:4 (2020), 23  crossref  mathscinet  isi
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:488
    Full text:150
    References:41
    First page:16

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021