General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

Probl. Peredachi Inf., 2009, Volume 45, Issue 1, Pages 51–59 (Mi ppi1259)  

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

Automata Theory

Perceptrons of large weight

V. V. Podolskii

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

Abstract: A threshold gate is a linear combination of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximum absolute value of the coefficients of a threshold gate is called its weight. A degree-$d$ perceptron is a Boolean circuit of depth 2 with a threshold gate at the top and any Boolean elements of fan-in at most $d$ at the bottom level. The weight of a perceptron is the weight of its threshold gate.
For any constant $d\ge 2$ independent of the number of input variables $n$, we construct a degree-$d$ perceptron that requires weights of at least $n^{\Omega(n^d)}$; i.e., the weight of any degree-$d$ perceptron that computes the same Boolean function must be at least $n^{\Omega(n^d)}$. This bound is tight: any degree-$d$ perceptron is equivalent to a degree-$d$ perceptron of weight $n^{O(n^d)}$. For the case of threshold gates (i.e., $d=1$), the result was proved by Håstad in [2]; we use Håstad's technique.

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

English version:
Problems of Information Transmission, 2009, 45:1, 46–53

Bibliographic databases:

UDC: 621.391.1:004.8
Received: 22.07.2008

Citation: V. V. Podolskii, “Perceptrons of large weight”, Probl. Peredachi Inf., 45:1 (2009), 51–59; Problems Inform. Transmission, 45:1 (2009), 46–53

Citation in format AMSBIB
\by V.~V.~Podolskii
\paper Perceptrons of large weight
\jour Probl. Peredachi Inf.
\yr 2009
\vol 45
\issue 1
\pages 51--59
\jour Problems Inform. Transmission
\yr 2009
\vol 45
\issue 1
\pages 46--53

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. V. V. Podolskii, A. A. Sherstov, “A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length”, Math. Notes, 87:6 (2010), 860–873  mathnet  crossref  crossref  mathscinet  isi
    2. Diakonikolas I., Servedio R.A., Tan L.-Ya., Wan A., “A Regularity Lemma, and Low-weight Approximators, for Low-degree Polynomial Threshold Functions”, 25th Annual IEEE Conference on Computational Complexity - Ccc 2010, Annual IEEE Conference on Computational Complexity, 2010, 211–222  crossref  mathscinet  isi
    3. Babai L., Hansen K.A., Podolskii V.V., Sun X., “Weights of Exact Threshold Functions”, Mathematical Foundations of Computer Science 2010, Lecture Notes in Computer Science, 6281, 2010, 66–77  crossref  mathscinet  zmath  isi
    4. Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  mathnet  crossref  mathscinet  isi  elib  elib
    5. De A., Diakonikolas I., Servedio R.A., “Deterministic Approximate Counting For Juntas of Degree-2 Polynomial Threshold Functions”, 2014 IEEE 29Th Conference on Computational Complexity (Ccc), IEEE Conference on Computational Complexity, IEEE, 2014, 229–240  crossref  mathscinet  isi
    6. Viola E., “the Communication Complexity of Addition”, Combinatorica, 35:6 (2015), 703–747  crossref  mathscinet  isi  elib
    7. Rao Ya., Zhang X., “Characterization of Linearly Separable Boolean Functions: a Graph-Theoretic Perspective”, IEEE Trans. Neural Netw. Learn. Syst., 28:7 (2017), 1542–1549  crossref  mathscinet  isi  scopus
    8. De A., Servedio R.A., “A New Central Limit Theorem and Decomposition For Gaussian Polynomials, With An Application to Deterministic Approximate Counting”, Probab. Theory Relat. Field, 171:3-4 (2018), 981–1044  crossref  mathscinet  zmath  isi  scopus
    9. Rao Yanyi, Zhang Xianda, “The Characterizations of Hyper-Star Graphs Induced By Linearly Separable Boolean Functions”, Chin. J. Electron., 27:1, 1 (2018), 19–25  crossref  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:454
    Full text:74
    First page:17

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