On the meaning of works by V. M. Khrapchenko

S. B. Gashkov ; I. S. Sergeev

Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 109-124.

Résumé

The paper surveys main works and results by Valerii Mikhailovich Khrapchenko, who stands among the pioneers of national theoretical cybernetics. Mathematical results by V. M. Khrapchenko can be related to the following five directions: 1) synthesis of parallel adders; 2) relations between the complexity and depth of Boolean formulae; 3) low bounds for complexity of Boolean formulae; 4) synthesis of formulae for symmetric Boolean functions; 5) relation between depth and delay of schemes. Method of low bounds by V. M. Khrapchenko comes into many courses of lectures and into all the main monographies on the complexity of Boolean functions. The description of parallel adder by V. M. Khrapchenko is given in many books attended to rapid arithmetics.

Détail

Keywords: depth, circuit delay, lower complexity bounds, parallel adder, symmetric functions.
Mots-clés : Khrapchenko method

Bibliographie

[1] Khrapchenko V. M., “On a method of transforming a multiserial code into a uniserial one”, Soviet Phys. Dokl., 8 (1963), 8–10

[2] Khrapchenko V. M., “On the bounding of an error in binary multiplication”, Problemy Kibernetiki, 10, ed. A. A. Lyapunov, Nauka Publ., M., 1963, 165–177 (in Russian) | MR

[3] Khrapchenko V. M., “Asymptotic estimation of addition time of a parallel adder”, Problemy Kibernetiki, 19, ed. A. A. Lyapunov, Nauka Publ., M., 1967, 107–120 (in Russian)

[4] Yablonskii S. V., Kozyrev V. P., “Mathematical problems of cybernetics”, Information materials of Scientific council of Acad. of Sci. USSR on complex problem “Kibernetika”, 19a, M., 1968, 3–15 (in Russian)

[5] Khrapchenko V. M., “On the complexity of the realization of the linear function in the class of $\Pi$-circuits”, Math. Notes Acad. of Sci. USSR, 9:1 (1971), 21–23 | MR | Zbl | Zbl

[6] Khrapchenko V. M., “A method of obtaining lower bounds for the complexity of $\Pi$-schemes”, Math. Notes Acad. of Sci. USSR, 10:1 (1971), 474–479 | MR | Zbl

[7] Khrapchenko V. M., “The complexity of the realization of symmetric functions by formulae”, Math. Notes Acad. of Sci. USSR, 11:1 (1972), 70–76 | MR | Zbl

[8] Khrapchenko V. M., “A quadratic complexity lower bound based on the continuity of the second derivative”, Problemy Kibernetiki, 26, ed. A. A. Lyapunov, Nauka Publ., M., 1973, 203–206 (in Russian) | MR

[9] Khrapchenko V. M., “On the complexity of realization of symmetric Boolean functions by formulas over finite bases”, Problemy Kibernetiki, 31, ed. S. V. Yablonskii, Nauka Publ., M., 1976, 231–234 (in Russian) | MR

[10] Khrapchenko V. M., “Some bounds for the time of multiplication”, Problemy Kibernetiki, 33, ed. S. V. Yablonskii, Nauka Publ., M., 1978, 221–227 (in Russian) | MR

[11] Khrapchenko V. M., “Depth and delay in a network”, Soviet Math. Dokl., 19 (1978), 1006–1009 | Zbl

[12] Khrapchenko V. M., “On a relation between the complexity and the depth of formulae”, Metody Diskretnogo Analiza v Sinteze Upravlyayushchikh Sistem, 32, Math. Instit. Siber. Branch Acad. Sci. USSR, Novosibirsk, 1978, 76–94 (in Russian)

[13] Khrapchenko V. M., “A difference and a similarity between depth and delay”, Problemy Kibernetiki, 35, ed. S. V. Yablonskii, Nauka Publ., M., 1979, 141–168 (in Russian) | MR

[14] Khrapchenko V. M., “On the relation between the complexity and the depth of formulae in a base containing median”, Metody Diskretnogo Analiza v Izuchenii Bulevykh Funktsii i Grafov, 37, Math. Instit. Siber. Branch Acad. Sci. USSR, Novosibirsk, 1981, 77–84 (in Russian) | MR

[15] Khrapchenko V. M., “Lower complexity bounds for the circuits of functional elements (the survey)”, Kibernetichesk. Sbornik, 21, ed. O. B. Lupanov, Mir Publ., M., 1984, 3–54 (in Russian) | MR

[16] Khrapchenko V. M., “New inequality relations between depth and delay”, Discrete Math. Appl., 5:6 (1995), 547–555 | DOI | Zbl

[17] Khrapchenko V. M., “Works by R. G. Nigmatullin on the lower complexity bounds”, Diskretn. Analiz i Issled. Oper., Ser. 1, 7:1 (2000), 18–31 (in Russian) | MR | Zbl

[18] Khrapchenko V. M., “A quadratic lower bound for the complexity of formulae over the base $\{\,\vee,\overline{\phantom a}\}$ for BCH-codes”, Matematicheskie Voprosy Kibernetiki, 16, ed. N. A. Karpova, Fizmatlit Publ., M., 2007, 239–241 (in Russian)

[19] Khrapchenko V. M., “On one of the possibilities of sharpening estimates for the delay of a parallel adder”, J. Appl. Industr. Math., 2:2 (2008), 211–214 | DOI | MR

[20] Khrapchenko V. M., “The fundamental difference between depth and delay”, Discrete Math. Appl., 18:4 (2008), 391–412 | DOI | DOI | MR | Zbl

[21] Khrapchenko V. M., “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174 | DOI | DOI | MR | Zbl

[22] Khrapchenko V. M., “Mathematician Oleg Borisovich Lupanov (1932–2006)”, Chebysh. Sbornik, 17:2 (2016), 6–20 (in Russian) | DOI | MR | Zbl

[23] Khrapchenko V. M., “Lupanov methods and their significance for the development of the circuit synthesis theory”, Chebysh. Sbornik, 17:2 (2016), 184–195 (in Russian) | DOI | MR | Zbl

[24] Andreev A. E., “On a method for obtaining more than quadratic effective lower bounds for the complexity of $\pi$-schemes”, Moscow University Math. Bulletin, 42:1 (1987), 63–66 ; 15:4 (2008), 92–93 | MR | Zbl | Zbl | MR | Zbl

[25] Gashkov S. B., Grinchuk M. I., Sergeev I. S., “Circuit design of an adder of small depth”, J. Appl. Industr. Math., 2:2 (2008), 167–178 | DOI | MR | MR | MR | Zbl | Zbl

[26] Grinchuk M. I., “Sharpening an upper bound on the adder and comparator depths”, J. Appl. Industr. Math., 3:1 (2009), 61–67 | DOI | MR | MR | Zbl

[27] Zdobnov S. V., “On the complexity of linear function in the class of $\Pi$-schemes without null chains”, Kombinatorno-Algebr. Metody i ih Primenenie, Gork. Univ. Publ., Gor'kyi, 1987, 27–34 (in Russian)

[28] Lozhkin S. A., Danilov B. R., “Network delay in a model with inputs of functional elements”, Moscow Univ. Comput. Math. and Cybern., 37:4 (2013), 180–188 | DOI | MR | Zbl

[29] Lupanov O. B., Asymptotic Estimates for the Complexity of control systems, MSU Publ., M., 1984, 138 pp. (in Russian)

[30] Nechiporuk E. I., “On a Boolean function”, Soviet Math. Dokl., 7:4 (1966), 999–1000 | MR | Zbl

[31] Nigmatullin R. G., The Complexity of Boolean Functions, Nauka Publ., M., 1991, 240 pp. (in Russian) | MR

[32] Ofman Y. P., “On the algorithmic complexity of discrete functions”, Soviet Phys. Dokl., 7 (1963), 589–591 | MR | Zbl

[33] Pulatov A. K., “A lower bound for the circuit complexity of a class of codes”, Diskretnyi Analiz, 25 (1974), 56–61 (in Russian) | Zbl

[34] Rychkov K. L., “A modification of Khrapchenko's method and its application to lower bounds for $\Pi$-schemes of code functions”, Metody Diskretnogo Analiza v Teorii Grafov i Skhem, 42, Math. Instit. Siber. Branch Acad. Sci. USSR, Novosibirsk, 1985, 91–98 (in Russian)

[35] Rychkov K. L., “Lower bounds on the complexity of parallel-sequential switching circuits that realize linear Boolean functions”, Sibirsk. Zh. Issled. Oper., 1:4 (1994), 33–52 (in Russian) | Zbl

[36] Rychkov K. L., “On the lower bounds of formula complexity of the linear Boolean function”, Sibirsk. Elektr. Matem. Izv., 11 (2014), 165–184 (in Russian) | Zbl

[37] Sergeev I. S., “Complexity and depth of formulas for symmetric Boolean functions”, Moscow University Math. Bulletin, 71:3 (2016), 127–130 | DOI | MR | Zbl

[38] Subbotovskaya B. A., “Realizations of linear functions by formulas using $\{\vee,\,\neg\}$”, Soviet Math. Dokl., 2 (1961), 110–112 | MR | Zbl

[39] Ugol'nikov A. B., “Depth and polynomial equivalence of formulas for closed classes of two-valued logic”, Math. Notes Acad. of Sci. USSR, 42:4 (1987), 832–837 | MR | Zbl

[40] Cherukhin D. Y., “Lower bounds for the formula complexity of symmetric Boolean functions”, Diskretn. Analiz i Issled. Oper., Ser. 1, 7:3 (2000), 86–98 (in Russian) | MR | Zbl

[41] Cherukhin D. Y., “To the problem of the logic representation of parity”, Neformal'naya Nauka, 2008, no. 2, 14–23 (in Russian)

[42] Yablonskii S. V., “Realisation of the linear function in the class of $\Pi$-schemes”, Dokl. Akad. Nauk USSR, 94:5 (1954), 805–806 (in Russian) | Zbl

[43] Brent R., “On the addition of binary numbers”, IEEE Trans. Comp., C-19:8 (1970), 758–759 | DOI

[44] Commentz-Walter B., “Size-depth tradeoff in monotone Boolean formulae”, Acta Inf., 12 (1979), 227–243 | DOI | MR | Zbl

[45] Commentz-Walter B., Sattler J., “Size-depth tradeoff in non-monotone Boolean formulae”, Acta Inf., 14 (1980), 257–269 | DOI | MR | Zbl

[46] Coppersmith D., Schieber B., “Lower bounds on the depth of monotone arithmetic computations”, Proc. 33rd Symp. Foundations of Computer Sci. (Pittsburgh, 1992), IEEE CS, Washington, 1992, 288–295 | DOI | Zbl

[47] Dunne P. E., The Complexity of Boolean Networks, Academic Press, San Diego, 1988, 512 pp. | MR | Zbl

[48] Gál A., Tal A., Trejo Nuñez A., “Cubic formula size lower bounds based on compositions with majority”, Electr. Colloq. Comput. Complexity, 2018, TR18-160 | MR

[49] Grove E., Proofs with Potential, Ph.D. thesis, Univ. of California, Berkeley, 1993

[50] Håstad J., “The shrinkage exponent of de Morgan formulas is 2”, SIAM J. Comput., 27:1 (1998), 48–64 | DOI | MR

[51] Held S., Spirkl S. T., “Binary adder circuits of asymptotically minimum depth, linear size, and fan-out two”, ACM Trans. Algorithms, 14:1 (2017), 4:1–4:18 | MR

[52] Hodes L., Specker E., “Length of formulas and elimination of quantifiers I”, Contributions to Mathematical Logic, North Holland, Amsterdam, 1968, 175–188 | MR

[53] Jukna S., Boolean function complexity, Springer Verlag, Berlin–Heidelberg, 2012, 618 pp. | MR | Zbl

[54] Karchmer M., Wigderson A., “Monotone circuits for connectivity require super-logarithmic depth”, SIAM J. Discrete Math., 3:2 (1990), 255–265 | DOI | MR | Zbl

[55] Kosaraju S. R., “Parallel evaluation of division-free arithmetic equations”, Proc. 18th Symp. Theory of Comput. (Berkeley, 1986), ACM, NY, 1986, 231–239

[56] Maruyama K., “On the parallel evaluation of polynomials”, IEEE Trans. Comp., C-22:1 (1973), 2–5 | DOI | MR

[57] McColl W. F., Some results on circuit depth. Theory of computation, Report No 18, Univ. of Warwick, Coventry, 1977

[58] Munro I., Paterson M., “Optimal algorithms for parallel polynomial evaluation”, J. Comp. System Sci., 7 (1973), 189–198 | DOI | MR | Zbl

[59] Paterson M. S., “An introduction to Boolean function complexity”, Astérisque, 38–39, 1976, 183–201 | MR | Zbl

[60] Paterson M. S., Pippenger N., Zwick U., “Optimal carry save networks”, Boolean function complexity, LMS Lecture Notes Series, 169, ed. M. S. Paterson, Cambridge University Press, 1992, 174–201 | MR

[61] Paterson M., Zwick U., “Shallow circuits and concise formulae for multiple addition and multiplication”, Comput. Complexity, 3 (1993), 262–291 | DOI | MR | Zbl

[62] Preparata F. P., Muller D. E., “Efficient parallel evaluation of Boolean expressions”, IEEE Trans. Comp., C-25:5 (1976), 548–549 | DOI | MR

[63] Pudlák P., “Bounds for Hodes — Specker theorem”, Logic and Machines: Decision Problems and Complexity, LNCS, 171, 1984, 421–445 | MR | Zbl

[64] Ragaz M., “Parallelizable algebras”, Arch. Math. Logic, 26 (1986/87), 77–99 | DOI | MR

[65] Savage J. E., The Complexity of Computing, Wiley, New York, 1976, 391 pp. | MR | Zbl

[66] Spira P. M., “On time-hardware complexity tradeoffs for Boolean functions”, Proc. 4th Hawaii Symp. System Sci., Western Periodical Company, N. Hollywood, 1971, 525–527

[67] Tal A., “Shrinkage of de Morgan formulae from quantum query complexity”, Electr. Colloq. on Comput. Complexity, 2014, TR14-048

[68] Wegener I., The complexity of Boolean functions, Wiley-Teubner, Stuttgart, 1987, 470 pp. | MR | Zbl