◈ We establish a lower bound 5n–o(n) on the complexity of an explicit boolean n×n matrix with respect to implementation by additive circuits over GF(2). It seems that only 3n–o(n) bounds were previously known. Also we obtain complexity lower bounds 3n–o(n) for an explicit n×n circulant matrix, and for the Sierpiński matrix of the same size. Along the way, we prove lower bounds on the additive complexity of bilinear algorithms: (4–o(1))n² for multiplication of n×n matrices, 5n–o(n) for multiplication of degree n–1 polynomials, and 4n–o(n) for the cyclic convolution of order n over GF(2).

◈ We prove a lower bound 0.75(n–1)2ⁿ on the complexity of a universal fanout-2 depth-n prefix circuit on 2ⁿ inputs improving over the previous lower bound 0.5(n+1–o(1))2ⁿ due to F. Fich (1983) and getting closer to the upper bound (n–0.5)2ⁿ by P. Kogge and H. Stone (1973). We also propose a number of simple constructions and upper complexity bounds on fanout-2 prefix circuits of depth n+k, for small k's.

◈ The paper contains a few results on the additive complexity. (i) We improve the N. Pippenger's upper bound (1980) on the complexity of the class of m×n matrices with bounded by q coefficients in a linear term from A + O(m+n) to A + n, where A = min(m, n)log₂q + (1+o(1))H/log₂H, and H = mnlog₂q, and it is tight. Principally, it follows from [29]. (ii) For the sequence {2, 2², ..., 2^n–1, 2ⁿ–1}, we obtain a rather accurare complexity n + (2±o(1))n^1/2 improving the asymptotic of the `second term' in bounds by P. Downey, B. Leong, R. Sethi (1981). (iii) D. Dobkin and R. J. Lipton (1980) for an explicitly given polynomially bounded sequence of size n proved a lower bound n + n^2/3–o(1). We construct explicit sequences of size n: (a) of polynomially bounded numbers, and of complexity n + Ω(n^1–ε), for any ε>0; (b) of numbers bounded by n^{O(log n)}, and of complexity n + Ω(n).
Conference version: in Proc. DMTCS'11 (Moscow, 2023).

◈ M. M. Halldórsson, J. Radhakrishnan and K. V. Subrahmanyam (1993) proved a lower bound Ω(n log log log n) on the complexity of computation of the threshold symmetric function T_n^n-1 by monotone switching (contact) networks. We improve this bound to Ω(n log log n) by a simpler argument.

◈ For any n and k, we construct an explicit (that is, computable in polynomial time) example of a dence enough integer B_k-sequence of size n consisting of elements bounded by n^k+o(k). It seems that in the case of growing k's, such examples were missed in literature. A fragment of [42].

◈ J. Alman, Y. Guan, A. Padaki (2022) proposed a new method for constructing low-complexity coverings of Kronecker powers of matrices and improved an upper bound on the depth-2 additive complexity of the Sierpiński (disjointness) matrix stated in the book. We provide an alternative proof for the case of symmetric matrices in a stronger form. This allows to further improve the above upper bound.

◈ We show that the multiplicative (nonscalar) complexity of the class of complex degree-d polynomials of n variables is of order n^⌈d/2⌉, for constant d, improving previously known lower bounds for odd d's. More accurate estimates are provided for the class of cubic polynomials.

◈ We introduce a model of programs reflecting a conveyor way of computations and provide a few simple examples to illustrate some effects on the complexity.

◈ We adapt V. M. Khrapchenko's formula size lower bound method (1971) to k-ary unate bases U_k by introducing appropriate complexity measures on graphs. As a consequence, we obtain a new lower bound Ω(n^1.53) for the formula complexity of a linear boolean function of n variables in the basis U₃ improving the result by H. Chockler and U. Zwick (2001). Also, we obtain an accurate form n^{1+Θ(1/log k)} for the order of the formula complexity of linear functions in bases U_k as k→∞.

◈ We prove that the sorting of n elements of a linearly ordered set is possible in log₂(n!) + o(n) comparisons in the worst case, thus resolving a long-standing problem from information theory. Previously known upper bounds were of the form log₂(n!) + Θ(n), even for the average case complexity.
Conference version: in Proc. sPTK'19 (online, 2020).
⌘ D. Taranovsky on his page claims to prove the same upper bound in 2020. However, the exposition there is too vague to understand whether it hides a correct proof (just my personal impression).

◈ A preprint version of [38], includes an additional example to illustrate a simplified method of sorting.

◈ We show that additional reciprocal inputs cannot help to reduce the complexity of monotone circuits in the basis {+, ×} more than quadratically in both arithmetic and tropical settings, though it is well-known that a single division gate at the output can lead to superpolynomial savings.

◈ We propose a new exposition of a (modified) multilevel representation synthesis method invented by E. I. Nechiporik (1962) and provide an alternative proof for the asymptotic Shannon complexity of AC-circuits with free negations, and also some bounds for the bounded-depth version of the problem. A supplementary result to [30].

◈ The paper surveys main works and results by V. M. Khrapchenko (1936-2019).

◈ A survey of modern methods of multiplication of numbers and polynomials.

◈ We establish the monotone circuit complexity of the threshold-2 symmetric boolean function of n variables in an accurate form 2n + Θ(n^1/2), thus resolving an old problem by L. Adleman. Even tighter complexity result 3n + O(log n) – O(1) we obtain for the threshold-3 symmetric function improving a lower bound due to P. Dunne (1985). Basing on the method by A. C. Yao (1975) we provide accurate upper bounds of the form 2nlog₂k + o(n) on the complexity of symmetric functions with small thresholds k.
Conference version: in Proc. sDMA'13 (Moscow, 2019).

◈ For the formula depth and complexity of a function f in a binary basis, the trivial inequality D(f) ≥ log₂L(f) holds. Stronger inequalities D(f) ≥ clog₂L(f) with c > 1 were previously obtained for some bases and special function sequences, e.g. c ≥ 1.5 for the monotone arithmetic basis due to D. Coppersmith and B. Schiber (1992). We prove the first depth-complexity separation result of this sort for an arithmetic-type boolean basis, namely, with c > 1.06 for the monotone basis {∨, ∧}.

◈ We prove tight in order lower bound on the monotone circuit complexity of the boolean permutation operator (generalizing the boolean shift operator) by adaptation of an argument proposed by A. V. Chashkin (2006). It also provides an alternative proof of the known lower bound for the shift operator as well.
Comment: in the first version of the paper, I missed that the lower bound on the complexity of the shift operator was already proved by E. A. Lamagna and J. E. Savage (1974).

◈ We show that conversions between binary and Fibonacci (Zeckendorf) representations of n-bit integer numbers may be implemented by boolean circuits of complexity O(M(n)log n), where M(n) stands for the complexity of multiplication of n-bit numbers, improving over a simple complexity bound O(n²) due to C. Ahlbach, J. Usatine, C. Frougny, N. Pippenger (2013). We also obtain analogous results for generalized representations, including c^log1/2nn complexity bounds for r-Fibonacci representations.

◈ M. W. Green (1969) and D. C. van Voorhis (about 1970) proposed the best known sorting networks for 16 elements in terms of complexity (60) and depth (9), respectively. These networks have a rather intricate construction. We propose an explanation of ideas behind the structure of the networks.

◈ We obtain a number of asymptotic results concerning the complexity of the class of boolean functions of n variables with respect to implementation by various types of AC circuits and formulas of bounded depth, improving e.g. an earlier result by V. Dančík (1996). In particular, we show that the Shannon complexity of de Morgan AC-circuits is ~2^n/2+1, and it is achieved in depth 3 (this result is final). A principal ingredient of the proofs is a special covering of the boolean cube by what we call pseudospheres, that generalizes coverings by spheres.
Comment: the word “unbounded” is missed in the title of the translated paper.
Conference version: in Proc. DMTCS'10 (Moscow, 2018).

◈ E. I. Nechiporuk (1963) showed that the asymptotic linear complexity mn/log₂(mn) of the class of boolean (m, n)-matrices is achieved in depth 3 for various ratios between m and n. N. Pippenger (1979) proved that the asymptotic holds for all m, n, except of some extremely unbalanced cases. We show that in the general case, the asymptotic is achieved by depth-3 circuits, and this result is final. Also, we slightly improve Pippenger's upper bounds on the linear complexity of classes of integer (m, n)-matrices with bounded by q coefficients from A + O(n) to A + n, where A = 3mlog₃q + (1+o(1))H/log₂H, and H = mnlog₂q, assuming m ≤ n, and it is tight.

◈ Improving a long-standing result, J. van Buskirk and T. J. Lundy (2007) proved that the complex DFT of order N = 2ⁿ may be computed via ~3.777...N log₂N real arithmetic operations. We show that this upper bound may be further improved to ~3.76875N log₂N.
Conference version: in Proc. PTK'18 (Penza, 2017).
⌘ J. Alman and K. Rao (2023) established a new record bound ~3.75N log₂N by a simpler method.

◈ We obtain asymptotically tight complexity bounds for the GCD matrix (formed by numbers gcd(i, j)) when implementing by circuits in the additive basis {+}, and for the analogously defined LCM matrix with respect to computation by circuits in addition-subtraction basis {±}. For the latter result, we propose a new nontrivial factorization of the LCM matrix in which all matrices have nonnegative integer entries.
Conference version: in Proc. DMTCS'9 (Moscow, 2015).

◈ We obtain new upper bounds for the size and the depth of formulae for some MOD-functions (that is, functions counting n bits modulo m). In particular, we improve the result of A. Chin (1990) on the depth of counting modulo 3 in the standard boolean basis {∨, ∧, ¯} to 2.8 log₂n + O(1) and substantially simplify the proof.
Conference version: in Proc. yDMA'10 (Moscow, 2015).

◈ Exploiting L. G. Valiant's idea of approximate computation of threshold symmetric functions, we further improve upper bounds [21, 22] on the depth and complexity of general symmetric boolean functions, and, particularly, of counting and threshold functions. As a consequence, we obtain new record asymptotic bounds for the depth of multiplication of n-bit numbers: 4.02 log₂n in the full binary boolean basis, and 5.14 log₂n in the standard boolean basis {∨, ∧, ¯}. New bounds are nonconstructive.

◈ M. Farah-Colton and M.-T. Tsai (2015) proved that the complexity of computing the table of primes between 1 and n on a multitape Turing machine is O(n log² n /log log n). We improve this bound to O(n log n). Note that the complexity of computing the table of composite numbers below n is Θ(n log n).

◈ We provide accurate upper bounds on the boolean circuit complexity of the standard and the Karatsuba methods of integer multiplication.
Conference version: in Proc. IMT'22 (Moscow, 2014).

◈ We construct explicit boolean matrices whose OR-complexity differs significantly from the complexity of their complement matrices. An additional material for the book.
Conference version: in Proc. PTK'17 (Kazan, 2014).

◈ We prove accurate upper complexity bounds on the complexity of submatrices of the Sierpiński (disjointness) matrix improving preliminary results by the authors (including [e3]) and provide some applications.

◈ A companion paper for [21]. Contains analogous results for the depth of symmetric boolean functions, also improving upper bounds due to E. Grove (1993).
Conference version: in Proc. yDMA'9 (Moscow, 2013).
⌘ The obtained bounds were further improved in [25], but nonconstructively.

◈ M. S. Paterson, N. Pippenger and U. Zwick (1990-1993) completed the theory of optimal constructing of compressor trees from compressing units with the main application to obtaining low-depth or low-size formulae for symmetric boolean functions from carry-save adder (CSA) modules. We implant an idea of modular computation and improve upper formula size bounds for symmetric functions in general, and for important particular cases: counting and threshold functions, with a consequence to the complexity of the integer multiplication.
Conference version: in Proc. yDMA'9 (Moscow, 2013).
⌘ The obtained bounds were further improved in [25], but nonconstructively.

◈ The journal version of the book.

◈ We obtain upper bounds on the bounded-depth XOR-complexity of boolean circulant matrices. A supplementary material for the book.

◈ U. Zwick (1996) observed a simple relation between the multiplicative and the total monotone complexity of boolean functions, that is tight up to the order of magnitude. We prove a similar but asymptotically tight relation for boolean circuits over Zhegalkin basis, that is, arithmetic circuits over GF(2). It follows from an old result by E. I. Nechiporuk (1962).

◈ A full and improved version of [9]. We provide accurate complexity estimates for multiplication and inversion in some special field towers, with applications to multiplication of polynomials. Namely, we obtain new upper bounds for the complexity of FFT in tower fields, leading to the currently record complexity bounds for multiplication of polynomials (via the Schönhage-type method). Say, the complexity of multiplication of binary degree-n polynomials doesn't exceed (10+o(1))nlog₃nlog₂logn.
Conference version: in Proc. sDMA'11 (Moscow, 2012).
⌘ D. Harvey, J. van der Hoeven and G. Lecerf (2017) improved the complexity of polynomial multiplication to O(n log n α(n)), where α(n) is an extremely slowly growing function.

◈ A full version of [14]. We establish the exact complexity of the minimal width-2ⁿ depth-n general (parallel) prefix circuit improving over an earlier result by F. E. Fich (1982). It is 3.5·2ⁿ – (8.5+3.5(n mod 2))2^⌊n/2⌋ + n + 5. We also provide a number of new upper bounds on the complexity of parallel prefix circuits under various restrictions, and better (than general) upper bounds on the complexity of prefix XOR-circuits, e.g. (36/11–o(1))m for width m and minimal depth.
Conference version: in Proc. sDMA'10 (Moscow, 2010).
⌘ The case of bounded-by-2-fanout prefix circuits is examined in more detail in [43].

◈ S. B. Gashkov (1987) proposed a method for proving lower bounds on the monotone arithmetic complexity of real polynomials corresponding to the thin (i.e. rectangle-free) sets. We slightly generalize his method and e.g. for explicitly given degree-n polynomials, obtain nearly extremal bounds n^1–o(1) and n^1/2–o(1) on the overall and on the multiplicative complexity, respectively. By the way, we describe a procedure of reconstruction of multidimensional thin sets into one-dimensional equally thin sets of nearly the same density. For example, it also provides an explicit example of a circulant boolean n×n matrix of nearly quadratic OR-complexity n^2–o(1).
Conference version: in Proc. PTK'16 (Nizhny Novgorod, 2011).
⌘ S. Jukna (2017) proposed a simplified modification of our method.

◈ P. Kaski, M. Koivisto and J. H. Korhonen (2012) obtained some upper bounds on the additive complexity of submatrices of the Sierpiński (disjointness) matrix. We improve these bounds and also prove a lower counterpart.
⌘ In the joint paper [23], we obtained even better complexity upper bounds.

◈ We apply the idea by M. S. Paterson and U. Zwick (1993) of efficient generating low-depth compressor trees from compressing units with multiple-type inputs/outputs to constructing low-size formulas for symmetric boolean functions and improve the previously known complexity bounds.
⌘ The obtained complexity bounds are further improved in [21] and [25].

◈ An improvement over the complexity bounds [11] for exponential and raising to a power of complex or real power series. The former costs as much as ~23/12 same-size multiplications, and the latter as ~27/8 multiplications.

◈ A survey of some results on the complexity of implementation of arithmetic operations in finite fields by boolean circuits.

◈ We construct circuits for the truncated Fourier transform (TFT) efficient either in complexity and depth, or in complexity and memory size, with application to the polynomial multiplication: complexity bounds are essentially the same as for unrestricted TFT algorithms. The latter in-place algorithm constitutes an improvement over the result due to D. Harvey and D. S. Roche (2010).
Conference version: in Proc. yDMA'7 (Moscow, 2009), and in Proc. yDMA'8 (Moscow, 2011).
⌘ A. Arnold (2013) slightly improved the complexity of the in-place algorithm.
⌘ N. Coxon (2022) proposed yet another in-place TFT algorithm of nearly the same complexity as those mentioned above.

◈ A brief version of [18] (omitting most of proofs).

◈ M. I. Grinchuk (1988) proved the existence of circulant boolean n×n matrices of almost quadratic OR-complexity. We further tighten his result and as a consequence obtain an almost tight lower bound Ω(n²/log⁶n) for the monotone complexity of the order-n boolean convolution improving over the result by J. Weiß (1983).
⌘ In [17], we proposed a constructive example of a circulant boolean matrix of almost quadratic OR-complexity.

◈ We resolve an old problem stated by B. S. Mityagin and B. N. Sadovskii (1965) of constructing a boolean matrix without 2×2 rectangles whose linear XOR-complexity is much smaller than the matrix weight, and consider some generalizations of this problem. In fact, we constructively prove almost maximal possible separations OR(M)/XOR(M) between OR- and XOR-complexity of an n×n boolean matrix M in both rectangle-free (n^1/2–o(1)) and unrestricted settings (n^1–o(1)).
Conference version: in Proc. sDMA'10 (Moscow, 2010).
⌘ The questions of separations between linear measures of matrix complexity are thoroughly discussed in the book.

◈ We prove new upper bounds on the complexity of some elementary operations with complex or real power series. For instance, we show that inversion or square root cost as much as ~5/4 same-size multiplications improving over the results by A. Schönhage (2000) and D. J. Bernstein (2004), and exponential costs as ~13/6 multiplications improving the bound due to J. van der Hoeven (2006).
Conference version: in Proc. sDMA'9 (Moscow, 2007).
⌘ D. Harvey (2009) observed another and simpler way to prove the same complexity bound for exponential.
⌘ Complexity bounds for exponential and raising to a power were further improved in [e1].

◈ A survey of FFT algorithms in some rings with applications to polynomial multiplication. Contains a slight improvement of the bound from [9].

◈ We provide accurate complexity estimates for multiplication and inversion in some special field towers. In particular, they lead to better asymptotic upper bounds for multiplication of binary polynomials than those following from earlier works by J. von zur Gathen and J. Gerhard (1999) and D. J. Bernstein (2001).
⌘ Complexity bounds for multiplication were further improved in [10] and [19].

◈ We implement inversion in finite fields GF(pⁿ) by logarithmic depth arithmetic circuits over GF(p) and provide accurate complexity estimates.

◈ A survey of parallel circuits for operations in finite fields.

◈ W. Baur and V. Strassen (1983) proved a classical relation C(∇ f) ≤ 4C(f) between the circuit complexity of a rational function f and its gradient in the arithmetic basis { ±,×, ⁄ }. We improve it to C(∇ f) ≤ 3C(f) + n, where n is the number of variables of f.

◈ E. Kaltofen and V. Shoup (1998) for the problem of transition between the polynomial and normal representations of finite fields GF(qⁿ) proposed arithmetic circuits of subquadratic complexity O(n^1.82) over GF(q). However, their polynomial-to-normal algorithm is probabilistic. We propose a pair of deterministic and seemingly simpler algorithms of similar complexity O(n^1.81) (the exponent was slightly improved due to the progress in the rectangular matrix multiplication). Better algorithms are proposed for normal bases of the so-called low multiplication complexity. We also obtain corollaries for the problems of computing Frobenius automorphisms and checking the linear independence of a normal system.
Comment: It's my first genuinely self-written journal paper. Thus, it suffers from an insufficiently informative abstract and introduction, and a lack of notions.
Conference version: in Proc. SCCS'16 (Saint Petersburg, 2006).
⌘ C. Umans (2008) showed that the modular composition of degree-n polynomials over the fields of characteristic n^o(1) has almost linear complexity n^1+o(1). This result lowers the complexity of the algorithms for transitions in the fields of small characteristic to O(n^1.63) given the present-day (2023) bounds for the rectangular matrix multiplication.

◈ We obtain almost tight bounds for the minimal depth of a compressor tree composed of the standard (3,2)-compressors (carry-save adders) in the full binary boolean basis. It constitutes a slight but practically meaningful improvement over the bounds by M. S. Paterson, N. Pippenger and U. Zwick (1992) in this particular case. Precisely, we bound the minimal depth d(n) of a compressor tree with n inputs as log_λn – 2.7 < d(n) < log_λn – 0.8, where λ ≈ 1.205.

◈ We present and compare a few practical methods for shallow implementation of adder carry functions. Finally we construct an n-digit adder of complexity (8+o(1))n and depth log₂n + ((2+o(1))log₂n)^1/2 in the full binary boolean basis slightly improving the depth estimate for balanced adders made by V. M. Khrapchenko (1967).
⌘ M. I. Grinchuk (2008) proved a new upper bound log₂n + log₂log₂n + O(1) on the depth of an n-digit adder.
⌘ A. Hermann (2020) constructed adders of linear complexity and depth log₂n + log₂log₂n + log₂log₂log₂n + O(1).

◈ A brief version of [2] (omitting most of proofs).

◈ B. Litow and G. Davida (1988) and J. von zur Gathen (1990) constructed logarithmic depth circuits for inversion in finite fields. We propose an alternative method and provide accurate depth and complexity bounds for binary fields.
Conference version: in Proc. PTK'14 (Penza, 2005).

◈ We discuss constructions of addition chains for efficient implementation of inversion in binary finite fields. By the way, we construct addition chains computing n with asymptotically minimal length (1+o(1))log₂n and depth ⌊log₂n⌋ + 2, and note that in the general case, this depth bound cannot be improved.

Conference abbreviations:
DMTCS – “Discrete Models in the Theory of Control Systems” conference
IMT – “Information Means and Technology” conference
NTA – conference to the memory of A. A. Karatsuba on Number Theory and Applications
PTK – “Problems of Theoretical Cybernetics” conference
sPTK – online seminar of the “Problems of Theoretical Cybernetics” conference
SCCS – school-seminar “Synthesis and Complexity of Control Systems”
sDMA – seminar “Discrete Mathematics and its Applications”
yDMA – youth scientific school on Discrete Mathematics and its Applications

Report: seminar MVK - “Mathematical problems of cybernetics” (Moscow State University, 2024)

◈ An illustrated exposition of the results from [44].

Plenary talk: DMTCS'11 conference (Moscow, 2023). original slides (in Russian)

◈ A survey of known bounds on the complexity of computation of symmetric boolean functions by boolean circuits, formulae, switching circuits, including a brief exposition of some methods.

Report: seminar SCCS - “Synthesis and complexity of control systems” (Moscow State University, 2023); seminar MVK - “Mathematical problems of cybernetics” (Moscow State University, 2021).

◈ An exposition of the results from [39], with some proofs.

Plenary talk: PTK'19 conference (online, 2021). original slides (in Russian)

◈ An illustrated survey of results on the complexity of boolean linear circuits. Closely follows the contents of our book, and also includes some recent results.

Report: Research seminar on algebra (Moscow State University, 2021)

◈ A collection of examples of how the algebraic method (i.e. transition between algebraic structures) reduces the complexity of computations.

Report: seminar MVK - “Mathematical problems of cybernetics” (Moscow State University, 2021)

◈ A brief exposition of the results from [38].

Report: seminar MVK - “Mathematical problems of cybernetics” (Moscow State University, 2021)

◈ A brief exposition of the results from [31] and slightly beyond.

Report: Research seminar on number theory (Moscow State University, 2021)

◈ A survey of some results on the complexity of additive circuits over boolean, integer and real/complex domains.

Plenary talk: NTA'3 conference (Moscow, 2016)

◈ A survey of results on the complexity of some linear mappings, with respect to the implementation by boolean and arithmetic linear circuits.

Plenary talk: PTK'16 conference (Nizhny Novgorod, 2011). original slides (in Russian)

◈ A survey of some results on the complexity of arithmetic circuits for polynomials, with an emphasis on the results from [17].