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

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

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} 

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

 SHARE:

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
2. S. Jukna, “Tropical complexity, Sidon sets, and dynamic programming”, SIAM J. Discrete Math., 30:4 (2016), 2064–2085
3. S. Jukna, “Lower bounds for monotone counting circuits”, Discrete Appl. Math., 213 (2016), 139–152
4. S. Jukna, “Minkowski complexity of sets: an easy lower bound”, Am. Math. Mon., 124:8 (2017), 749–753
5. Jukna S., Seiwert H., “Approximation Limitations of Pure Dynamic Programming”, SIAM J. Comput., 49:1 (2020), 170–205
6. Srinivasan S., “Strongly Exponential Separation Between Monotone Vp and Monotone Vnp”, ACM Trans. Comput. Theory, 12:4 (2020), 23
•  Number of views: This page: 488 Full text: 150 References: 41 First page: 16

 Contact us: math-net2021_12 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2021