V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of $\Pi$-circuits”, Mat. Zametki, 9:1 (1971), 35–40; Math. Notes, 9:1 (1971), 21

Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

Matematicheskie Zametki

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Forthcoming papers
	Archive
	Impact factor
	Guidelines for authors
	License agreement
	Submit a manuscript

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

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

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

Matematicheskie Zametki, 1971, Volume 9, Issue 1, Pages 35–40 (Mi mzm9639)

This article is cited in 47 scientific papers (total in 49 papers)

Complexity of the realization of a linear function in the class of

$\Pi$ -circuits

V. M. Khrapchenko

Applied Mathematics Institute, Academy of Sciences of the USSR

Full-text PDF (665 kB) Citations (49)

Abstract: It is proved that the linear function

$g_n(x_1,\dots,x_n)=x_1+\dots+x_n\mod2$ is realized in the class of

$\Pi$ -circuits with complexity

$L_\pi(g_n)\geqslant n^2$ . Combination of this result with S. V. Yablonskii's upper bound yields

$L_\pi(g_n)\genfrac{}{}{0pt}{}{\smile}{\frown} n^2$ .

Received: 23.04.1970

English version:
Mathematical Notes, 1971, Volume 9, Issue 1, Pages 21–23
DOI: https://doi.org/10.1007/BF01405045

Bibliographic databases:

Document Type: Article

UDC: 51.01.16

Language: Russian

Citation: V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of

$\Pi$ -circuits”, Mat. Zametki, 9:1 (1971), 35–40; Math. Notes, 9:1 (1971), 21–23

Citation in format AMSBIB

\Bibitem{Khr71}

\by V.~M.~Khrapchenko

\paper Complexity of the realization of a linear function in the class of $\Pi$-circuits

\jour Mat. Zametki

\yr 1971

\vol 9

\issue 1

\pages 35--40

\mathnet{http://mi.mathnet.ru/mzm9639}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=290872}

\zmath{https://zbmath.org/?q=an:0222.94044|0206.29004}

\transl

\jour Math. Notes

\yr 1971

\vol 9

\issue 1

\pages 21--23

\crossref{https://doi.org/10.1007/BF01405045}

Linking options:

https://www.mathnet.ru/eng/mzm9639

https://www.mathnet.ru/eng/mzm/v9/i1/p35

This publication is cited in the following 49 articles:

N. P. Redkin, “O minimalnoi realizatsii operatora sovpadeniya bulevykh naborov”, Diskret. matem., 37:1 (2025), 52–75
K. L. Rychkov, “O stroenii odnogo klassa sovershennykh $\Pi$-razbienii”, Sib. elektron. matem. izv., 20:2 (2023), 1499–1518
K. L. Rychkov, “Predstavleniya normalizovannykh formul”, Diskretn. analiz i issled. oper., 29:4 (2022), 77–103
S. B. Gashkov, I. S. Sergeev, “O znachenii rabot V. M. Khrapchenko”, PDM, 2020, no. 48, 109–124
K. L. Rychkov, “O sovershennosti minimalnykh pravilnykh razbienii mnozhestva reber $n$-mernogo kuba”, Diskretn. analiz i issled. oper., 26:4 (2019), 74–107
K. L. Rychkov, “Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes”, J. Appl. Industr. Math., 12:3 (2018), 540–576
Benjamin Rossman, “The Average Sensitivity of Bounded-Depth Formulas”, comput. complex., 27:2 (2018), 209
K. L. Rychkov, “Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating”, J. Appl. Industr. Math., 9:4 (2015), 580–587
Kenya UENO, “Candidate Boolean Functions towards Super-Quadratic Formula Size”, IEICE Trans. Inf. & Syst., E98.D:3 (2015), 524
Kenya UENO, “Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory”, IIS, 21:4 (2015), 329
K. L. Rychkov, “O nizhnikh otsenkakh formulnoi slozhnosti lineinoi bulevoi funktsii”, Sib. elektron. matem. izv., 11 (2014), 165–184
Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Industr. Math., 7:4 (2013), 588–596
V. M. Khrapchenko, “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174
KENYA UENO, “BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS”, Int. J. Found. Comput. Sci., 24:08 (2013), 1339
S. V. Avgustinovich, Yu. L. Vasil'ev, K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Industr. Math., 6:4 (2012), 403–409
A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165
A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46
Kenya Ueno, Lecture Notes in Computer Science, 7434, Computing and Combinatorics, 2012, 433
Kenya Ueno, “A stronger LP bound for formula size lower bounds via clique constraints”, Theoretical Computer Science, 434 (2012), 87
Andrew M. Childs, Shelby Kimmel, Robin Kothari, Lecture Notes in Computer Science, 7501, Algorithms – ESA 2012, 2012, 337

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Statistics & downloads:
Abstract page:	422
Full-text PDF :	196
First page:	1

Registration to the website

Logotypes