A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

S. B. Gashkov   ; I. S. Sergeev

Sbornik. Mathematics, Tome 203 (2012) no. 10, pp. 1411-1447

Résumé

This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis $\{x+y, \,x \cdot y\}\cup\{a \cdot x\mid a\in \mathbb R_+\}$. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree $m-1$ in each of the $n$ variables with coefficients 0 and 1 having additive monotone complexity $m^{(1-o(1))n}$ and multiplicative monotone complexity $m^{(1/2-o(1))n}$ as $m^n \to \infty$. In this form, the lower bounds derived here are sharp. Bibliography: 72 titles.

Détail

Keywords: lower bounds for complexity, arithmetic circuits, thin sets, monotone complexity
Mots-clés : permanent.

Bibliographie

[1] M. R. Garey, D. S. Johnson, Computers and intractability, Freeman, San Francisco, CA, 1979 | MR | MR | Zbl | Zbl

[2] R. G. Nigmatullin, Slozhnost bulevykh funktsii, Nauka, M., 1991 | MR | Zbl

[3] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[4] O. B. Lupanov, “O metodakh polucheniya otsenok slozhnosti i vychisleniya individualnykh funktsii”, Diskret. analiz, 25 (1974), 3–18 | MR | Zbl

[5] V. M. Khrapchenko, “Nizhnie otsenki slozhnosti skhem iz funktsionalnykh elementov (obzor)”, Kiberneticheskii sbornik. Novaya seriya, v. 21, Mir, M., 1984, 3–54 | MR | Zbl

[6] R. G. Nigmatullin, Nizhnie otsenki slozhnosti i slozhnost universalnykh skhem, Izd-vo Kazanskogo un-ta, Kazan, 1990 | MR | Zbl

[7] A. A. Razborov, “Lower bounds for the monotone complexity of some Boolean functions”, Soviet Math. Dokl., 31:2 (1985), 354–357 | MR | Zbl

[8] A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493 | DOI | MR | Zbl

[9] A. E. Andreev, “A method for obtaining efficient lower bounds for monotone complexity”, Algebra and Logic, 26:1 (1987), 1–18 | DOI | MR | Zbl

[10] N. Alon, R. B. Boppana, “The monotone circuit complexity of boolean functions”, Combinatorica, 7:1 (1987), 1–22 | DOI | MR | Zbl

[11] A. E. Andreev, Ob odnom metode polucheniya nizhnikh otsenok slozhnosti individualnykh monotonnykh funktsii, Preprint No 248 IPMekh AN SSSR i MGU, M., 1985

[12] A. E. Andreev, “On a method for obtaining lower bounds for the complexity of individual monotone functions”, Soviet Math. Dokl., 31:3 (1985), 530–534 | MR | Zbl

[13] D. Harnik, R. Raz, “Higher lower bounds on monotone size”, Proceedings of the 32 Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, 378–387 | MR

[14] D. E. Knuth, The art of computer programming, v. 2, Seminumerical algorithms, Bonn, Reading, MA, 1998 | MR | MR | Zbl | Zbl

[15] J. von zur Gathen, V. Strassen, “Some polynomials that are hard to compute”, Theoret. Comput. Sci., 11:3 (1980), 331–335 | DOI | MR | MR | Zbl | Zbl

[16] J. Heintz, M. Sieveking, “Lower bounds for polynomials with algebraic coefficients”, Theoret. Comput. Sci., 11:3 (1980), 321–330 | DOI | MR | MR | Zbl | Zbl

[17] H.-J. Stoss, “Lower bounds for the complexity of polynomials”, Theoret. Comput. Sci., 64:1 (1989), 15–23 | DOI | MR | Zbl | Zbl

[18] W. Baur, K. Halupczok, “On lower bounds for the complexity of polynomials and their multiples”, Comput. Complexity, 8:4 (1999), 309–315 | DOI | MR | Zbl

[19] M. S. Paterson, L. J. Stockmeyer, “On the number of nonscalar multiplications necessary to evaluate polynomials”, SIAM J. Comput., 2 (1973), 60–66 | DOI | MR | Zbl

[20] D. Yu. Grigorev, “Nizhnie otsenki v algebraicheskoi slozhnosti vychislenii”, Teoriya slozhnosti vychislenii. I, Zap. nauchn. sem. LOMI, 118, Izd-vo “Nauka”, Leningrad. otd., L., 1982, 25–82 | MR | Zbl

[21] P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer-Verlag, Berlin–Heidelberg, 1997 | MR | Zbl

[22] C. P. Schnorr, J. P. van de Wiele, “On the additive complexity of polynomials”, Theoret. Comput. Sci., 10:1 (1980), 1–18 | DOI | MR | MR | Zbl | Zbl

[23] J. E. Savage, “An algorithm for the computation of linear forms”, SIAM J. Comput., 3 (1974), 150–158 | DOI | MR | Zbl

[24] V. Strassen, “Berechnungen in partiellen Algebren endlichen Typs”, Computing (Arch. Elektron. Rechnen), 11:3 (1973), 181–196 | DOI | MR | Zbl

[25] S. B. Gashkov, “On the complexity of the computation of certain classes of polynomials of several variables”, Moscow Univ. Math. Bull., 43:2 (1988), 65–67 | MR | Zbl

[26] S. B. Gashkov, “On parallel evaluation of certain classes of polynomials with an increasing number of variables”, Moscow Univ. Math. Bull., 45:2 (1990), 64–67 | MR | Zbl

[27] S. B. Gashkov, “Slozhnost realizatsii bulevykh funktsii skhemami iz funktsionalnykh elementov i formulami v bazisakh, elementy kotorykh realizuyut nepreryvnye funktsii”, Problemy kibernetiki, v. 37, Nauka, M., 1980, 57–118 | MR | Zbl

[28] I. I. Zhegalkin, “Arifmetizatsiya simvolicheskoi logiki”, Matem. sb., 35:3-4 (1928), 311–377 | Zbl

[29] C. P. Schnorr, “A lower bound on the number of additions in monotone computations”, Theoret. Comput. Sci., 2:3 (1976), 305–315 | DOI | MR | MR | Zbl | Zbl

[30] R. Jerrum , M. Snir, “Some exact complexity results for straight-line computations over semirings”, J. Assoc. Comput. Mach., 29:3 (1982), 874–897 | DOI | MR | Zbl

[31] L. G. Valiant, “Negation can be exponentially powerful”, Theoret. Comput. Sci., 12:3 (1980), 303–314 | DOI | MR | Zbl

[32] L. G. Valiant, “The complexity of computing the permanent”, Theoret. Comput. Sci., 8:2 (1979), 189–201 | DOI | MR | MR | Zbl | Zbl

[33] L. G. Valiant, “Completeness classes in algebra”, Conference Record of the 11-th Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1979), ACM, New York, 1979, 249–261 | MR

[34] G. Malod, “The complexity of polynomials and their coefficient functions”, Proc. IEEE Conf. Comput. Complexity, 13 (2007), 193–204

[35] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998 | MR | Zbl

[36] R. Sengupta, H. Venkaterswaran, “A lower bound for monotone arithmetic circuits computing 0–1 permanent”, Theoret. Comput. Sci., 209:1–2 (1998), 389–398 | DOI | MR | Zbl

[37] M. Agraval, “Determinant versus permanent”, Proc. International Congress of Mathematicians, v. 3, Eur. Math. Soc., Zürich, 2006, 985–997 | MR

[38] R. Raz, “Multi-linear formulas for permanent and determinant are of super-polynomial size”, Proc. of the 36th annual ACM symposium on theory of computing (Chicago, IL, USA, 2004), ACM Press, New York, 2004, 633–641 | DOI | MR | Zbl

[39] O. M. Kasim-Zade, “Ob arifmeticheskoi slozhnosti monotonnykh mnogochlenov”, Tezisy Vsesoyuznoi konferentsii “Teoreticheskie problemy kibernetiki”, Izd-vo Saratovskogo un-ta, Saratov, 1986, 68–69

[40] O. M. Kasim-Zade, “O slozhnosti monotonnykh mnogochlenov”, Materialy Vsesoyuznogo seminara po diskretnoi matematike i ee prilozheniyam, Izd-vo MGU, M., 1986, 136–138 | MR

[41] S. E. Kuznetsov, “Monotonnye vychisleniya polinomov i skhemy bez nulevykh tsepei”, Tezisy dokladov VII Vsesoyuznoi konferentsii po problemam teoreticheskoi kibernetiki. Ch. 1, Irkutsk, 1985, 108–109

[42] S. E. Kuznetsov, “Circuits of functional elements without zero chains in the basis $\{\,v\}$”, Soviet Math. (Iz. VUZ), 25:5 (1981), 62–73 | MR | Zbl

[43] S. B. Gashkov, “The complexity of monotone computations of polynomials”, Soviet Math. (Iz. VUZ), 42:5 (1987), 1–8 | Zbl | Zbl

[44] R. Raz, A. Yehudayoff, “Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors”, J. Comput. System Sci., 77:1 (2011), 167–190 | DOI | MR | Zbl

[45] N. Nisan, A. Wigderson, “Lower bounds on arithmetic circuits via partial derivatives”, Comput. Complexity, 6:3 (1996), 217–234 | DOI | MR | Zbl

[46] S. B. Gashkov, “The complexity of the realization of Boolean functions by schemes and formulas in bases consisting of continuous functions”, Soviet Math. Dokl., 21:5 (1980), 186–190 | MR | Zbl

[47] G. Turán, F. Vatan, “On the computation of boolean functions by analog circuits of bounded fan-in”, J. Comput. System Sci., 54:1 (1997), 199–212 | DOI | MR | Zbl

[48] A. Haken, S. A. Cook, “An exponential lower bound for the size of monotone real circuits”, J. Comput. System Sci., 58:2 (1999), 326–335 | DOI | MR | Zbl

[49] P. Pudlák, “Lower bounds for resolution and cutting plane proofs and monotone computations”, J. Symbolic Logic, 62:3 (1997), 981–998 | DOI | MR | Zbl

[50] J. Kóllar, L. Rónyai, T. Szabó, “Norm-graphs and bipartite Turán numbers”, Combinatorica, 16:3 (1996), 399–406 | DOI | MR | Zbl

[51] D. J. Kleitman, “Extremal properties of collections of subsets containing no two sets and their union”, J. Combinatorial Theory Ser. A, 20:3 (1976), 390–392 | DOI | MR | Zbl

[52] K. O'Bryant, “A complete annotated bibliography of work related to Sidon sequences”, Electron. J. Combin., 11 (2004) | Zbl

[53] V. Nikiforov, “A contribution to the Zarankiewicz problem”, Linear Algebra Appl., 432:6 (2010), 1405–1411 | DOI | MR | Zbl

[54] Z. Füredi, “An upper bound on Zarankiewicz' problem”, Combin. Probab. Comput., 5:1 (1996), 29–33 | DOI | MR | Zbl

[55] M. Hall, Combinatorial theory, Blaisdell Publ., Waltham, MA–Toronto–London, 1967 | MR | MR | Zbl | Zbl

[56] V. E. Alekseev, “Dve konstruktsii raznostnykh mnozhestv”, Problemy kibernetiki, v. 38, Nauka, M., 1981, 259–262 | MR | Zbl

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

[58] W. G. Brown, “On graphs that do not contain a Thomsen graph”, Canad. Math. Bull., 9 (1966), 281–285 | DOI | MR | MR | Zbl | Zbl

[59] A. I. Borevich, I. R. Shafarevich, Number theory, Academic Press, New York–London, 1966 | MR | MR | Zbl | Zbl

[60] S. B. Gashkov, I. S. Sergeev, “An application of the method of additive chains to inversion in finite fields”, Discrete Math. Appl., 16:6 (2006), 601–618 | DOI | MR | Zbl

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

[62] P. Erdős, J. Spencer, Probabilistic methods in combinatorics, Wiley-Intersci. Ser. Discrete Math. Optim., Academic Press, New York–London, 1974 | MR | MR | Zbl

[63] A. E. Andreev, “On a family of Boolean matrices”, Moscow Univ. Math. Bull., 41:2 (1986), 79–82 | MR | Zbl | Zbl

[64] S. B. Gashkov, I. S. Sergeev, “On the complexity of linear Boolean operators with thin matrices”, J. Appl. Ind. Math., 5:2 (2011), 202–211 | DOI | MR | Zbl

[65] M. I. Grinchuk, “Complexity of implementing cyclic Boolean matrices by means of gate circuits”, Soviet Math. (Iz. VUZ), 32:7 (1988), 65–72 | MR | Zbl | Zbl

[66] M. I. Grinchuk, I. S. Sergeev, “Redkie tsirkulyantnye matritsy i nizhnie otsenki slozhnosti nekotorykh bulevykh operatorov”, Diskretn. analiz i issled. oper., 18:5 (2011), 38–53 | MR | Zbl

[67] K. Mehlhorn, “Some remarks on Boolean sums”, Acta Inf., 12:4 (1979), 371–375 | DOI | MR | MR | Zbl | Zbl

[68] S. B. Gashkov, I. B. Gashkov, “On the complexity of calculation of differentials and gradients”, Discrete Math. Appl., 15:4 (2005), 327–350 | DOI | MR | Zbl

[69] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974 | MR | MR | Zbl | Zbl

[70] A. Shpilka, A. Yehudayoff, “Arithmetic circuits: a survey of recent results and open questions”, Found. Trends Theor. Comput. Sci., 5:3–4 (2010), 207–388 | DOI | MR | Zbl

[71] I. Wegener, The complexity of Boolean functions, Wiley-Teubner Ser. Comput. Sci., Wiley, Stuttgart, 1987 | MR | Zbl

[72] N. Blum, “On negations in Boolean networks”, Efficient algorithms, Lecture Notes in Comput. Sci., 5760, Springer-Verlag, Berlin–Heidelberg, 2009, 18–29 | Zbl