RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

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

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 Håstad in [2]; we use Hå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

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
\Bibitem{Pod09} \by V.~V.~Podolskii \paper Perceptrons of large weight \jour Probl. Peredachi Inf. \yr 2009 \vol 45 \issue 1 \pages 51--59 \mathnet{http://mi.mathnet.ru/ppi1259} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2513163} \zmath{https://zbmath.org/?q=an:1171.68585} \transl \jour Problems Inform. Transmission \yr 2009 \vol 45 \issue 1 \pages 46--53 \crossref{https://doi.org/10.1134/S0032946009010062} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000265776300006} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-65549151265} 

• http://mi.mathnet.ru/eng/ppi1259
• http://mi.mathnet.ru/eng/ppi/v45/i1/p51

 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. 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
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
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
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
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
6. Viola E., “the Communication Complexity of Addition”, Combinatorica, 35:6 (2015), 703–747
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
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
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
•  Number of views: This page: 454 Full text: 74 References: 45 First page: 17