×

Computational barriers to estimation from low-degree polynomials. (English) Zbl 07547952

Summary: One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-degree polynomials as a restricted model of computation for such problems: it has been demonstrated in various settings that low-degree polynomials of the data can match the statistical performance of the best known polynomial-time algorithms. Prior work has studied the power of low-degree polynomials for the task of detecting the presence of hidden structures. In this work, we extend these methods to address problems of estimation and recovery (instead of detection). For a large class of “signal plus noise” problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree-\(D\) polynomial. To our knowledge, these are the first results to establish low-degree hardness of recovery problems for which the associated detection problem is easy. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems, resolving (in the low-degree framework) open problems about the computational complexity of recovery in both cases.

MSC:

62F15 Bayesian inference
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Software:

LAS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] ACHLIOPTAS, D. and COJA-OGHLAN, A. (2008). Algorithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science 793-802. IEEE, New York.
[2] AKAVIA, A., GOLDREICH, O., GOLDWASSER, S. and MOSHKOVITZ, D. (2006). On basing one-way functions on NP-hardness. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 701-710. ACM, New York. · Zbl 1302.68132 · doi:10.1145/1132516.1132614
[3] AMES, B. P. (2013). Robust convex relaxation for the planted clique and densest k-subgraph problems. ArXiv preprint. Available at arXiv:1305.4891.
[4] AMINI, A. A. and WAINWRIGHT, M. J. (2008). High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE International Symposium on Information Theory 2454-2458. IEEE.
[5] Arias-Castro, E., Candès, E. J. and Durand, A. (2011). Detection of an anomalous cluster in a network. Ann. Statist. 39 278-304. · Zbl 1209.62097 · doi:10.1214/10-AOS839
[6] ARIAS-CASTRO, E. and VERZELEN, N. (2014). Community detection in dense random networks. Ann. Statist. 42 940-969. · Zbl 1305.62035 · doi:10.1214/14-AOS1208
[7] Baik, J., Ben Arous, G. and Péché, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 33 1643-1697. · Zbl 1086.15022 · doi:10.1214/009117905000000233
[8] Baik, J. and Silverstein, J. W. (2006). Eigenvalues of large sample covariance matrices of spiked population models. J. Multivariate Anal. 97 1382-1408. · Zbl 1220.15011 · doi:10.1016/j.jmva.2005.08.003
[9] BALAKRISHNAN, S., KOLAR, M., RINALDO, A., SINGH, A. and WASSERMAN, L. (2011). Statistical and computational tradeoffs in biclustering. In NeurIPS 2011 Workshop on Computational Trade-Offs in Statistical Learning 4.
[10] BANDEIRA, A. S., BANKS, J., KUNISKY, D., MOORE, C. and WEIN, A. (2021). Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Conference on Learning Theory 410-473. PMLR.
[11] BANDEIRA, A. S., KUNISKY, D. and WEIN, A. S. (2020). Computational hardness of certifying bounds on constrained PCA problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) Schloss Dagstuhl-Leibniz-Zentrum für Informatik. · Zbl 07650426
[12] BANKS, J., KLEINBERG, R. and MOORE, C. (2019). The Lovász theta function for random regular graphs and community detection in the hard regime. SIAM J. Comput. 48 1098-1119. · Zbl 1420.05160 · doi:10.1137/18M1180396
[13] BANKS, J., MOHANTY, S. and RAGHAVENDRA, P. (2019). Local statistics, semidefinite programming, and community detection. ArXiv preprint. Available at arXiv:1911.01960.
[14] BARAK, B., CHOU, C.-N., LEI, Z., SCHRAMM, T. and SHENG, Y. (2019). (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. In Advances in Neural Information Processing Systems 9190-9198.
[15] BARAK, B., HOPKINS, S., KELNER, J., KOTHARI, P. K., MOITRA, A. and POTECHIN, A. (2019). A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48 687-735. · Zbl 1421.68056 · doi:10.1137/17M1138236
[16] BARBIER, J., MACRIS, N. and RUSH, C. (2020). All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation. ArXiv preprint. Available at arXiv:2006.07971.
[17] Bayati, M. and Montanari, A. (2011). The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inf. Theory 57 764-785. · Zbl 1366.94079 · doi:10.1109/TIT.2010.2094817
[18] Ben Arous, G., Gheissari, R. and Jagannath, A. (2020). Algorithmic thresholds for tensor PCA. Ann. Probab. 48 2052-2087. · Zbl 1444.62080 · doi:10.1214/19-AOP1415
[19] BEN AROUS, G., WEIN, A. S. and ZADIK, I. (2020). Free energy wells and overlap gap property in sparse PCA. ArXiv preprint. Available at arXiv:2006.10689.
[20] Benaych-Georges, F. and Nadakuditi, R. R. (2011). The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Adv. Math. 227 494-521. · Zbl 1226.15023 · doi:10.1016/j.aim.2011.02.007
[21] BERTHET, Q. and RIGOLLET, P. (2013). Complexity theoretic lower bounds for sparse principal component detection. In Conference on Learning Theory 1046-1066.
[22] BHASKARA, A., CHARIKAR, M., CHLAMTAC, E., FEIGE, U. and VIJAYARAGHAVAN, A. (2010). Detecting high log-densities—An \[O({n^{1/4}})\] approximation for densest \(k\)-subgraph. In STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing 201-210. ACM, New York. · Zbl 1293.05200
[23] BIROLI, G., CAMMAROTA, C. and RICCI-TERSENGHI, F. (2020). How to iron out rough landscapes and get optimal performances: Averaged gradient descent and its application to tensor PCA. J. Phys. A 53 174003. · Zbl 1514.90249 · doi:10.1088/1751-8121/ab7b1f
[24] BOGDANOV, A. and TREVISAN, L. (2006). On worst-case to average-case reductions for NP problems. SIAM J. Comput. 36 1119-1159. · Zbl 1118.68072 · doi:10.1137/S0097539705446974
[25] Bolthausen, E. (2014). An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model. Comm. Math. Phys. 325 333-366. · Zbl 1288.82038 · doi:10.1007/s00220-013-1862-3
[26] BRENNAN, M. and BRESLER, G. (2019). Optimal average-case reductions to sparse PCA: From weak assumptions to strong hardness. In Conference on Learning Theory 469-470.
[27] BRENNAN, M. and BRESLER, G. (2020). Reducibility and statistical-computational gaps from secret leakage. ArXiv preprint. Available at arXiv:2005.08099.
[28] BRENNAN, M., BRESLER, G., HOPKINS, S. B., LI, J. and SCHRAMM, T. (2021). Statistical query algorithms and low-degree tests are almost equivalent. In Conference on Learning Theory.
[29] BRENNAN, M., BRESLER, G. and HULEIHEL, W. (2018). Reducibility and computational lower bounds for problems with planted sparse structure. In Conference on Learning Theory 48-166.
[30] BRESLER, G. and HUANG, B. (2021). The algorithmic phase transition of random \(k\)-SAT for low degree polynomials. ArXiv preprint. Available at arXiv:2106.02129.
[31] BUTUCEA, C. and INGSTER, Y. I. (2013). Detection of a sparse submatrix of a high-dimensional noisy matrix. Bernoulli 19 2652-2688. · Zbl 1457.62072 · doi:10.3150/12-BEJ470
[32] BUTUCEA, C., INGSTER, Y. I. and SUSLINA, I. A. (2015). Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix. ESAIM Probab. Stat. 19 115-134. · Zbl 1330.62169 · doi:10.1051/ps/2014017
[33] CAI, T. T., LIANG, T. and RAKHLIN, A. (2017). Computational and statistical boundaries for submatrix localization in a large noisy matrix. Ann. Statist. 45 1403-1430. · Zbl 1392.62017 · doi:10.1214/16-AOS1488
[34] CAI, T. T. and WU, Y. (2020). Statistical and computational limits for sparse matrix detection. Ann. Statist. 48 1593-1614. · Zbl 1453.62285 · doi:10.1214/19-AOS1860
[35] Capitaine, M., Donati-Martin, C. and Féral, D. (2009). The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations. Ann. Probab. 37 1-47. · Zbl 1163.15026 · doi:10.1214/08-AOP394
[36] Chen, W.-K., Gamarnik, D., Panchenko, D. and Rahman, M. (2019). Suboptimality of local algorithms for a class of max-cut problems. Ann. Probab. 47 1587-1618. · Zbl 1466.60200 · doi:10.1214/18-AOP1291
[37] Chen, Y. (2015). Incoherence-optimal matrix completion. IEEE Trans. Inf. Theory 61 2909-2923. · Zbl 1359.15022 · doi:10.1109/TIT.2015.2415195
[38] CHEN, Y. and XU, J. (2016). Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. J. Mach. Learn. Res. 17 Paper No. 27. · Zbl 1360.62320
[39] CHLAMTÁČ, E. and MANURANGSI, P. (2018). Sherali-adams integrality gaps matching the log-density threshold. ArXiv preprint. Available at arXiv:1804.07842. · Zbl 1521.68253
[40] COJA-OGHLAN, A., HAQSHENAS, A. and HETTERICH, S. (2017). Walksat stalls well below satisfiability. SIAM J. Discrete Math. 31 1160-1173. · Zbl 1371.68109 · doi:10.1137/16M1084158
[41] Deshpande, Y., Abbe, E. and Montanari, A. (2017). Asymptotic mutual information for the balanced binary stochastic block model. Inf. Inference 6 125-170. · Zbl 1383.62021 · doi:10.1093/imaiai/iaw017
[42] DESHPANDE, Y. and MONTANARI, A. (2014). Information-theoretically optimal sparse PCA. In 2014 IEEE International Symposium on Information Theory 2197-2201. IEEE, New York.
[43] DESHPANDE, Y. and MONTANARI, A. (2015). Finding hidden cliques of size \[\sqrt{N/e}\] in nearly linear time. Found. Comput. Math. 15 1069-1128. · Zbl 1347.05227 · doi:10.1007/s10208-014-9215-y
[44] DING, Y., KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2019). Subexponential-time algorithms for sparse PCA. ArXiv preprint. Available at arXiv:1907.11635.
[45] Donoho, D. and Jin, J. (2004). Higher criticism for detecting sparse heterogeneous mixtures. Ann. Statist. 32 962-994. · Zbl 1092.62051 · doi:10.1214/009053604000000265
[46] Donoho, D. L., Maleki, A. and Montanari, A. (2009). Message-passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. USA 106 18914-18919.
[47] DUDEJA, R. and HSU, D. (2021). Statistical query lower bounds for tensor PCA. J. Mach. Learn. Res. 22 Paper No. 83. · Zbl 07370600
[48] FEIGENBAUM, J. and FORTNOW, L. (1993). Random-self-reducibility of complete sets. SIAM J. Comput. 22 994-1005. · Zbl 0789.68057 · doi:10.1137/0222061
[49] FELDMAN, V., GRIGORESCU, E., REYZIN, L., VEMPALA, S. S. and XIAO, Y. (2017). Statistical algorithms and a lower bound for detecting planted cliques. J. ACM 64 Art. 8. · Zbl 1397.68085 · doi:10.1145/3046674
[50] Féral, D. and Péché, S. (2007). The largest eigenvalue of rank one deformation of large Wigner matrices. Comm. Math. Phys. 272 185-228. · Zbl 1136.82016 · doi:10.1007/s00220-007-0209-3
[51] Gamarnik, D. and Jagannath, A. (2021). The overlap gap property and approximate message passing algorithms for \(p\)-spin models. Ann. Probab. 49 180-205. · Zbl 1470.60277 · doi:10.1214/20-AOP1448
[52] GAMARNIK, D., JAGANNATH, A. and SEN, S. (2021). The overlap gap property in principal submatrix recovery. Probab. Theory Related Fields 181 757-814. · Zbl 1518.68299 · doi:10.1007/s00440-021-01089-7
[53] GAMARNIK, D., JAGANNATH, A. and WEIN, A. S. (2020). Low-degree hardness of random optimization problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science 131-140. IEEE Computer Soc., Los Alamitos, CA. · doi:10.1109/FOCS46700.2020.00021
[54] Gamarnik, D. and Sudan, M. (2014). Limits of local algorithms over sparse random graphs [extended abstract]. In ITCS’14—Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science 369-375. ACM, New York. · Zbl 1365.05277
[55] GAMARNIK, D. and ZADIK, I. (2017). High dimensional regression with binary coefficients. Estimating squared error and a phase transtition. In Conference on Learning Theory 948-953.
[56] GAMARNIK, D. and ZADIK, I. (2019). The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. ArXiv preprint. Available at arXiv:1904.07174.
[57] GAO, C., MA, Z. and ZHOU, H. H. (2017). Sparse CCA: Adaptive estimation and computational barriers. Ann. Statist. 45 2074-2101. · Zbl 1421.62073 · doi:10.1214/16-AOS1519
[58] GHOSH, M., JERONIMO, F. G., JONES, C., POTECHIN, A. and RAJENDRAN, G. (2020). Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science 954-965. IEEE Computer Soc., Los Alamitos, CA.
[59] HAJEK, B., WU, Y. and XU, J. (2015). Computational lower bounds for community detection on random graphs. In Conference on Learning Theory 899-928.
[60] HAJEK, B., WU, Y. and XU, J. (2017). Submatrix localization via message passing. J. Mach. Learn. Res. 18 Paper No. 186. · Zbl 1468.68155
[61] HOLMGREN, J. and WEIN, A. S. (2021). Counterexamples to the low-degree conjecture. In 12th Innovations in Theoretical Computer Science Conference. LIPIcs. Leibniz Int. Proc. Inform. 185 Art. No. 75. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern.
[62] HOLTZMAN, G., SOFFER, A. and VILENCHIK, D. (2020). A greedy anytime algorithm for sparse PCA. In Conference on Learning Theory 1939-1956.
[63] HOPKINS, S. (2018). Statistical inference and the sum of squares method. Ph.D. thesis, Cornell University.
[64] HOPKINS, S. B., KOTHARI, P. K., POTECHIN, A., RAGHAVENDRA, P., SCHRAMM, T. and STEURER, D. (2017). The power of sum-of-squares for detecting hidden structures. In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017 720-731. IEEE Computer Soc., Los Alamitos, CA. · doi:10.1109/FOCS.2017.72
[65] HOPKINS, S. B., SCHRAMM, T. and SHI, J. (2019). A robust spectral algorithm for overcomplete tensor decomposition. In Conference on Learning Theory 1683-1722.
[66] Hopkins, S. B., Shi, J., Schramm, T. and Steurer, D. (2016). Fast spectral algorithms from sum-of-squares proofs: Tensor decomposition and planted sparse vectors. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing 178-191. ACM, New York. · Zbl 1377.68199 · doi:10.1145/2897518.2897529
[67] HOPKINS, S. B., SHI, J. and STEURER, D. (2015). Tensor principal component analysis via sum-of-squares proofs. In Conference on Learning Theory 956-1006.
[68] HOPKINS, S. B. and STEURER, D. (2017). Efficient Bayesian estimation from few samples: Community detection and related problems. In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017 379-390. IEEE Computer Soc., Los Alamitos, CA. · doi:10.1109/FOCS.2017.42
[69] Javanmard, A. and Montanari, A. (2013). State evolution for general approximate message passing algorithms, with applications to spatial coupling. Inf. Inference 2 115-144. · Zbl 1335.94015 · doi:10.1093/imaiai/iat004
[70] Johnstone, I. M. and Lu, A. Y. (2009). On consistency and sparsity for principal components analysis in high dimensions. J. Amer. Statist. Assoc. 104 682-693. · Zbl 1388.62174 · doi:10.1198/jasa.2009.0121
[71] KEARNS, M. (1998). Efficient noise-tolerant learning from statistical queries. J. ACM 45 983-1006. · Zbl 1065.68605 · doi:10.1145/293347.293351
[72] KOLAR, M., BALAKRISHNAN, S., RINALDO, A. and SINGH, A. (2011). Minimax localization of structural information in large noisy matrices. In Advances in Neural Information Processing Systems 909-917.
[73] KOTHARI, P. K., MORI, R., O’DONNELL, R. and WITMER, D. (2017). Sum of squares lower bounds for refuting any CSP. In STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 132-145. ACM, New York. · Zbl 1370.68134 · doi:10.1145/3055399.3055485
[74] KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2019). Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint. Available at arXiv:1907.11636.
[75] LESIEUR, T., KRZAKALA, F. and ZDEBOROVÁ, L. (2015). Phase transitions in sparse PCA. In 2015 IEEE International Symposium on Information Theory (ISIT) 1635-1639. IEEE.
[76] LESIEUR, T., KRZAKALA, F. and ZDEBOROVÁ, L. (2015). MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) 680-687. IEEE.
[77] LÖFFLER, M., WEIN, A. S. and BANDEIRA, A. S. (2020). Computationally efficient sparse clustering. ArXiv preprint. Available at arXiv:2005.10817.
[78] Ma, Z. and Wu, Y. (2015). Computational barriers in minimax submatrix detection. Ann. Statist. 43 1089-1116. · Zbl 1328.62354 · doi:10.1214/14-AOS1300
[79] MAGNUS, W., OBERHETTINGER, F. and SONI, R. P. (2013). Formulas and Theorems for the Special Functions of Mathematical Physics, Vol. 52. Springer Science & Business Media.
[80] MASSOULIÉ, L., STEPHAN, L. and TOWSLEY, D. (2019). Planting trees in graphs, and finding them back. In Conference on Learning Theory 2341-2371. PMLR.
[81] MOHANTY, S., RAGHAVENDRA, P. and XU, J. (2020). Lifting sum-of-squares lower bounds: Degree-2 to degree-4. In STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing 840-853. ACM, New York. · Zbl 07298292 · doi:10.1145/3357713.3384319
[82] MONTANARI, A. (2019). Optimization of the Sherrington-Kirkpatrick Hamiltonian. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science 1417-1433. IEEE Comput. Soc. Press, Los Alamitos, CA. · doi:10.1109/FOCS.2019.00087
[83] MONTANARI, A. and VENKATARAMANAN, R. (2021). Estimation of low-rank matrices via approximate message passing. Ann. Statist. 49 321-345. · Zbl 1461.62070 · doi:10.1214/20-AOS1958
[84] NISAN, N. and SZEGEDY, M. (1994). On the degree of Boolean functions as real polynomials. Comput. Complexity 4 301-313. · Zbl 0829.68047
[85] NOVAK, J. (2014). Three lectures on free probability. Random matrix theory, interacting particle systems, and integrable systems 65 13. · Zbl 1318.81009
[86] PATURI, R. (1992). On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing 468-474.
[87] Perry, A., Wein, A. S., Bandeira, A. S. and Moitra, A. (2018). Optimality and sub-optimality of PCA I: Spiked random matrix models. Ann. Statist. 46 2416-2451. · Zbl 1404.62065 · doi:10.1214/17-AOS1625
[88] RAGHAVENDRA, P., SCHRAMM, T. and STEURER, D. (2018). High-dimensional estimation via sum-of-squares proofs. ArXiv preprint. Available at arXiv:1807.11419. · Zbl 1451.90113
[89] RAHMAN, M. and VIRÁG, B. (2017). Local algorithms for independent sets are half-optimal. Ann. Probab. 45 1543-1577. · Zbl 1377.60049 · doi:10.1214/16-AOP1094
[90] RANGAN, S. and FLETCHER, A. K. (2012). Iterative estimation of constrained rank-one matrices in noise. In 2012 IEEE International Symposium on Information Theory Proceedings 1246-1250. IEEE.
[91] Richard, E. and Montanari, A. (2014). A statistical model for tensor PCA. In Advances in Neural Information Processing Systems 2897-2905.
[92] SCHRAMM, T. and WEIN, A. S (2022). Supplement to “Computational barriers to estimation from low-degree polynomials.” https://doi.org/10.1214/22-AOS2179SUPP
[93] Shabalin, A. A., Weigman, V. J., Perou, C. M. and Nobel, A. B. (2009). Finding large average submatrices in high dimensional data. Ann. Appl. Stat. 3 985-1012. · Zbl 1196.62087 · doi:10.1214/09-AOAS239
[94] SZEGÖ, G. (1939). Orthogonal Polynomials. American Mathematical Society Colloquium Publications, Vol. 23. Amer. Math. Soc., New York. · JFM 65.0278.03
[95] VERZELEN, N. and ARIAS-CASTRO, E. (2015). Community detection in sparse random networks. Ann. Appl. Probab. 25 3465-3510. · Zbl 1326.05145 · doi:10.1214/14-AAP1080
[96] WANG, T., BERTHET, Q. and PLAN, Y. (2016). Average-case hardness of RIP certification. In Advances in Neural Information Processing Systems 3819-3827.
[97] WANG, T., BERTHET, Q. and SAMWORTH, R. J. (2016). Statistical and computational trade-offs in estimation of sparse principal components. Ann. Statist. 44 1896-1930. · Zbl 1349.62254 · doi:10.1214/15-AOS1369
[98] WEIN, A. S. (2021). Optimal low-degree hardness of maximum independent set. Math. Stat. Learn. 4 221-251. · Zbl 07488304
[99] WEIN, A. S., EL ALAOUI, A. and MOORE, C. (2019). The Kikuchi hierarchy and tensor PCA. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science 1446-1468. IEEE Comput. Soc. Press, Los Alamitos, CA.
[100] Zhang, A. and Xia, D. (2018). Tensor SVD: Statistical and computational limits. IEEE Trans. Inf. Theory 64 7311-7338 · Zbl 1432.62176 · doi:10.1109/TIT.2018.2841377
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.