Geodesic
On the Additive Complexity
Matematičeskie zametki, Tome 115 (2024) no. 3, pp. 408-421 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper presents several results concerning the complexity of calculations in the model of vector additive chains. A refinement of N. Pippenger's upper bound is obtained for the complexity of the class of integer $m \times n$ matrices with the constraint $q$ on the size of the coefficients as $H=mn\log_2 q \to \infty$ up to $\min\{m,n\}\log_2 q+(1+o(1))H/\log_2 H+n$. The established complexity of calculating the number $2^n-1$ in the basis of powers of two is asymptotically sharp: it is equal to $(2+o(1))\sqrt n$. Based on generalized Sidon sequences, constructive examples of numerical sets of cardinality $n$ are constructed: sets, with polynomial size of elements, having the complexity $n+\Omega(n^{1-\varepsilon})$ for any $\varepsilon>0$ and sets, with the size $n^{O(\log n)}$ of the elements, having the complexity $n+\Omega(n)$.
Keywords: additive chains, ${\mathcal B}_k$-sets, sums of sets, sum-free sets, cycles in graphs, lower bounds for complexity.
Mots-clés : gate circuits, Sidon sets 
@article{MZM_2024_115_3_a7,
     author = {I. S. Sergeev},
     title = {On the {Additive} {Complexity}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {408--421},
     year = {2024},
     volume = {115},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2024_115_3_a7/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On the Additive Complexity
JO  - Matematičeskie zametki
PY  - 2024
SP  - 408
EP  - 421
VL  - 115
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MZM_2024_115_3_a7/
LA  - ru
ID  - MZM_2024_115_3_a7
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On the Additive Complexity
%J Matematičeskie zametki
%D 2024
%P 408-421
%V 115
%N 3
%U http://geodesic.mathdoc.fr/item/MZM_2024_115_3_a7/
%G ru
%F MZM_2024_115_3_a7
I. S. Sergeev. On the Additive Complexity. Matematičeskie zametki, Tome 115 (2024) no. 3, pp. 408-421. http://geodesic.mathdoc.fr/item/MZM_2024_115_3_a7/

[1] D. E. Knut, Iskusstvo programmirovaniya, v. 2, Poluchislennye algoritmy, Vilyams, M., 2004 | MR

[2] V. V. Kochergin, “Zadachi Bellmana, Knuta, Lupanova, Pippendzhera i ikh variatsii kak obobscheniya zadachi ob additivnykh tsepochkakh”, Matematicheskie voprosy kibernetiki. Vyp. 20, Fizmatlit, M., 2022, 119–256

[3] A. Brauer, “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR

[4] P. Erdös, “Remarks on number theory. III. On addition chains”, Acta Arithm., 6 (1960), 77–81 | DOI | MR

[5] N. Pippenger, “On the evaluation of powers and monomials”, SIAM J. Comput., 9:2 (1980), 230–250 | DOI | MR

[6] I. S. Sergeev, “Ventilnye skhemy ogranichennoi glubiny”, Diskretn. analiz i issled. oper., 25:1 (2018), 120–141 | DOI | MR

[7] P. Downey, B. Leong, R. Sethi, “Computing sequences with addition chains”, SIAM J. Comput., 10:3 (1981), 638–646 | DOI | MR

[8] D. Dobkin, R. J. Lipton, “Addition chain methods for the evaluation of specific polynomials”, SIAM J. Comput., 9:1 (1980), 121–125 | DOI | MR

[9] T. Lam, J. Verstraëte, “A note on graphs without short even cycles”, Electron. J. Combin., 12:5 (2005), 1–6 | MR

[10] R. C. Bose, S. Chowla, “Theorems in the additive theory of numbers”, Comment. Math. Helv., 37 (1962), 141–147 | DOI | MR

[11] B. S. Mityagin, B. N. Sadovskii, “O lineinykh bulevskikh operatorakh”, Dokl. AN SSSR, 165:4 (1965), 773–776 | MR | Zbl

[12] A. Schönhage, “A lower bound for the length of addition chains”, Theoret. Comput. Sci., 1:1 (1975), 1–12 | DOI | MR

[13] J. A. Bondy, M. Simonovits, “Cycles of even length in graphs”, J. Combinatorial Theory Ser. B, 16 (1974), 97–105 | DOI | MR

[14] I. M. Vinogradov, Osnovy teorii chisel, Gostekhizdat, M.–L., 1952 | MR

[15] J. B. Rosser, L. Schoenfeld, “Approximate formulas for some functions of prime numbers”, Illinois J. Math., 6 (1962), 64–94 | DOI | MR