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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy MIAN:
Year:
Volume:
Issue:
Page:
Find






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


Tr. Mat. Inst. Steklova, 2011, Volume 274, Pages 252–268 (Mi tm3327)  

This article is cited in 1 scientific paper (total in 1 paper)

Degree-uniform lower bound on the weights of polynomials with given sign function

Vladimir V. Podolskii

Steklov Mathematical Institute, Russian Academy of Sciences, Moscow, Russia

Abstract: A Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is called the sign function of an integer polynomial $p$ of degree $d$ in $n$ variables if it is true that $f(x)=1$ if and only if $p(x)>0$. In this case the polynomial $p$ is called a threshold gate of degree $d$ for the function $f$. The weight of the threshold gate is the sum of the absolute values of the coefficients of $p$. For any $n$ and $d\le D\le\frac{\varepsilon n^{1/5}}{\log n}$ we construct a function $f$ such that there is a threshold gate of degree $d$ for $f$, but any threshold gate for $f$ of degree at most $D$ has weight $2^{(\delta n)^d/D^{4d}}$, where $\varepsilon>0$ and $\delta>0$ are some constants. In particular, if $D$ is constant, then any threshold gate of degree $D$ for our function has weight $2^{\Omega(n^d)}$. Previously, functions with these properties have been known only for $d=1$ (and arbitrary $D$) and for $D=d$. For constant $d$ our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was $2^{\Omega(n)}$. Our results can also be translated to the case of functions $f\colon\{-1,1\}^n\to\{-1,1\}$.

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

English version:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 231–246

Bibliographic databases:

UDC: 510.52
Received in October 2010

Citation: Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Algorithmic aspects of algebra and logic, Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday, Tr. Mat. Inst. Steklova, 274, MAIK Nauka/Interperiodica, Moscow, 2011, 252–268; Proc. Steklov Inst. Math., 274 (2011), 231–246

Citation in format AMSBIB
\Bibitem{Pod11}
\by Vladimir~V.~Podolskii
\paper Degree-uniform lower bound on the weights of polynomials with given sign function
\inbook Algorithmic aspects of algebra and logic
\bookinfo Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday
\serial Tr. Mat. Inst. Steklova
\yr 2011
\vol 274
\pages 252--268
\publ MAIK Nauka/Interperiodica
\publaddr Moscow
\mathnet{http://mi.mathnet.ru/tm3327}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2962944}
\elib{http://elibrary.ru/item.asp?id=16766486}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 231--246
\crossref{https://doi.org/10.1134/S0081543811060149}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000295983200013}
\elib{http://elibrary.ru/item.asp?id=23964433}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84879911297}


Linking options:
  • http://mi.mathnet.ru/eng/tm3327
  • http://mi.mathnet.ru/eng/tm/v274/p252

    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. Podolskii V.V., “Lower Bound on Weights of Large Degree Threshold Functions”, Log. Meth. Comput. Sci., 9:2 (2013), 13  crossref  mathscinet  zmath  isi  elib
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Number of views:
    This page:272
    Full text:29
    References:28

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