{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T20:32:53Z","timestamp":1722371573981},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T00:00:00Z","timestamp":1681171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T00:00:00Z","timestamp":1681171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00453-023-01112-4","type":"journal-article","created":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T05:03:11Z","timestamp":1681189391000},"page":"2843-2884","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Faster Interior-Point Method for Sum-of-Squares Optimization"],"prefix":"10.1007","volume":"85","author":[{"given":"Shunhua","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bento","family":"Natura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,11]]},"reference":[{"key":"1112_CR1","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522\u2013539. SIAM (2021)","DOI":"10.1137\/1.9781611976465.32"},{"issue":"3","key":"1112_CR2","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1080\/10586458.2009.10129052","volume":"18","author":"B Ballinger","year":"2009","unstructured":"Ballinger, B., Blekherman, G., Cohn, H., Giansiracusa, N., Kelly, E., Sch\u00fcrmann, A.: Experimental study of energy-minimizing point configurations on spheres. Exp. Math. 18(3), 257\u2013283 (2009)","journal-title":"Exp. Math."},{"issue":"5","key":"1112_CR3","doi-asserted-by":"publisher","first-page":"1984","DOI":"10.1137\/090779024","volume":"48","author":"L Bos","year":"2010","unstructured":"Bos, L., De Marchi, S., Sommariva, A., Vianello, M.: Computing multivariate Fekete and Leja points by numerical linear algebra. SIAM J. Numer. Anal. 48(5), 1984\u20131999 (2010)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"1112_CR4","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/17M1138236","volume":"48","author":"B Barak","year":"2019","unstructured":"Barak, B., Hopkins, S.B., Kelner, J.A., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48(2), 687\u2013735 (2019)","journal-title":"SIAM J. Comput."},{"key":"1112_CR5","unstructured":"Bl\u00e4ser, M.: Fast matrix multiplication. In: Theory of Computing, pp. 1\u201360 (2013)"},{"key":"1112_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM (2012)"},{"key":"1112_CR7","doi-asserted-by":"crossref","unstructured":"Barak., B., Raghavendra., P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 472\u2013481. IEEE (2011)","DOI":"10.1109\/FOCS.2011.95"},{"key":"1112_CR8","doi-asserted-by":"crossref","unstructured":"Bachoc, C., Vallentin, F.: New upper bounds for kissing numbers from semidefinite programming. Technical report, Journal of the American Mathematical Society (2006)","DOI":"10.1090\/S0894-0347-07-00589-9"},{"key":"1112_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Lee, Y.T., Song, Z.: Solving linear programs in the current matrix multiplication time. In: Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC) (2019)","DOI":"10.1145\/3313276.3316303"},{"issue":"1\u20133","key":"1112_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci. 326(1\u20133), 57\u201367 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"1112_CR11","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1109\/TPWRS.2015.2390037","volume":"31","author":"B Ghaddar","year":"2016","unstructured":"Ghaddar, B., Marecek, J., M, M.: Optimal power flow as a polynomial optimization problem. IEEE Trans. Power Syst. 31, 539\u2013546 (2016)","journal-title":"IEEE Trans. Power Syst."},{"key":"1112_CR12","doi-asserted-by":"crossref","unstructured":"Gall, F.L., Urrutia, F.: Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In: Proceedings of the 2018 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1029\u20131046. SIAM (2018)","DOI":"10.1137\/1.9781611975031.67"},{"issue":"3","key":"1112_CR13","doi-asserted-by":"publisher","first-page":"1633","DOI":"10.1137\/15M1033198","volume":"54","author":"R He\u00df","year":"2016","unstructured":"He\u00df, R., Henrion, D., Lasserre, J.-B., Pham, T.S.: Semidefinite approximations of the polynomial abscissa. SIAM J. Control Optim. 54(3), 1633\u20131656 (2016)","journal-title":"SIAM J. Control Optim."},{"key":"1112_CR14","doi-asserted-by":"crossref","unstructured":"Huang, B., Jiang, S., Song, Z., Tao, R., Zhang, R.: Solving sdp faster: a robust ipm framework and efficient implementation (2021)","DOI":"10.1109\/FOCS54457.2022.00029"},{"key":"1112_CR15","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Kothari, P.K., Potechin, A., Raghavendra, P., Schramm, T., Steurer, D.: The power of sum-of-squares for detecting hidden structures. In: 58th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pp. 720\u2013731. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.72"},{"key":"1112_CR16","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Li, J.: Mixture models, robustness, and sum of squares proofs. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pp. 1021\u20131034. ACM (2018)","DOI":"10.1145\/3188745.3188748"},{"key":"1112_CR17","doi-asserted-by":"crossref","unstructured":"Jiang, H., Kathuria, T., Lee, Y.T., Padmanabhan, S., Song, Z.: A faster interior point method for semidefinite programming. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 910\u2013918. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00089"},{"key":"1112_CR18","doi-asserted-by":"crossref","unstructured":"Jiang, S., Man, Y., Song, Z., Yu, Z., Zhuo, D.: Fast graph neural tangent kernel via kronecker sketching (2021). arXiv preprint arXiv:2112.02446, AAAI\u201922","DOI":"10.1609\/aaai.v36i6.20662"},{"key":"1112_CR19","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"1112_CR20","volume-title":"An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge Texts in Applied Mathematics","author":"JB Lasserre","year":"2015","unstructured":"Lasserre, J.B.: An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press (2015)"},{"key":"1112_CR21","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of Squares, Moment Matrices and Optimization over Polynomials. Number 149 in The IMA Volumes in Mathematics and Its Applications Series, pp. 155\u2013270. Springer, Germany (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"1112_CR22","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"1112_CR23","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A.: Path finding methods for linear programming: solving linear programs in $${\\tilde{O}}(\\sqrt{rank})$$ iterations and faster algorithms for maximum flow. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 424\u2013433. IEEE (2014)","DOI":"10.1109\/FOCS.2014.52"},{"key":"1112_CR24","unstructured":"Lee, Y.T., Song, Z., Zhang, Q.: Solving empirical risk minimization in the current matrix multiplication time. In: Conference on Learning Theory (COLT), pp. 2140\u20132157. PMLR (2019)"},{"key":"1112_CR25","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Squared functional systems and optimization problems. In: High Performance Optimization, pp. 405\u2013440. Springer (2000)","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"1112_CR26","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms in convex programming. In: Siam Studies in Applied Mathematics (1987)"},{"key":"1112_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0129-8","volume-title":"Structured Matrices and Polynomials","author":"VY Pan","year":"2001","unstructured":"Pan, V.Y.: Structured Matrices and Polynomials. Birkh\u00e4user, Boston (2001)"},{"issue":"497","key":"1112_CR28","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1080\/01621459.2012.656035","volume":"107","author":"D Papp","year":"2012","unstructured":"Papp, D.: Optimal designs for rational function regression. J. Am. Stat. Assoc. 107(497), 400\u2013411 (2012)","journal-title":"J. Am. Stat. Assoc."},{"key":"1112_CR29","volume-title":"Sum of Squares: Theory and Applications: AMS Short Course, Sum of Squares: Theory and Applications, January 14\u201315, 2019, Baltimore, Maryland","author":"P Parrilo","year":"2020","unstructured":"Parrilo, P.: Sum of Squares: Theory and Applications: AMS Short Course, Sum of Squares: Theory and Applications, January 14\u201315, 2019, Baltimore, Maryland. American Mathematical Society, Providence (2020)"},{"issue":"7","key":"1112_CR30","first-page":"585","volume":"328","author":"M Putinar","year":"1999","unstructured":"Putinar, M., Vasilescu, F.-H.: Positive polynomials on semi-algebraic sets. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences - Series I - Mathematics 328(7), 585\u2013589 (1999)","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences - Series I - Mathematics"},{"issue":"1","key":"1112_CR31","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/17M1160124","volume":"29","author":"D Papp","year":"2019","unstructured":"Papp, D., Yildiz, S.: Sum-of-squares optimization without semidefinite programming. SIAM J. Optim. 29(1), 822\u2013851 (2019)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1112_CR32","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1109\/JSTSP.2007.910261","volume":"1","author":"T Roh","year":"2007","unstructured":"Roh, T., Dumitrescu, B., Vandenberghe, L.: Multidimensional FIR filter design via trigonometric sum-of-squares optimization. J. Sel. Top. Signal Process. 1(4), 641\u2013650 (2007)","journal-title":"J. Sel. Top. Signal Process."},{"key":"1112_CR33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718812","volume-title":"A Mathematical View of Interior-Point Methods in Convex Optimization","author":"J Renegar","year":"2001","unstructured":"Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. Society for Industrial and Applied Mathematics (2001)"},{"issue":"2","key":"1112_CR34","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF03025891","volume":"9","author":"G Strang","year":"1987","unstructured":"Strang, G.: Karmarkar\u2019s algorithm and its place in applied mathematics. Math. Intell. 9(2), 4\u201310 (1987)","journal-title":"Math. Intell."},{"issue":"8","key":"1112_CR35","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1016\/j.camwa.2008.11.011","volume":"57","author":"A Sommariva","year":"2009","unstructured":"Sommariva, A., Vianello, M.: Computing approximate Fekete points by QR factorizations of Vandermonde matrices. Comput. Math. Appl. 57(8), 1324\u20131336 (2009)","journal-title":"Comput. Math. Appl."},{"key":"1112_CR36","unstructured":"Song, Z., Yang, S., Zhang, R.: Does preprocessing help training over-parameterized neural networks? In: Advances in Neural Information Processing Systems, vol. 34 (2021)"},{"key":"1112_CR37","unstructured":"Song, Z., Zhang, L., Zhang R.: Training multi-layer over-parametrized neural network in subquadratic time (2021). arXiv preprint arXiv:2112.07628"},{"key":"1112_CR38","unstructured":"Tan, N.: On the power of Lasserre SDP hierarchy. Ph.D. thesis, EECS Department, University of California, Berkeley (2015)"},{"key":"1112_CR39","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication. In: 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 332\u2013337. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63499"},{"key":"1112_CR40","unstructured":"van\u00a0den Brand, J., Peng, B., Song, Z., Weinstein, O.: Training (overparametrized) neural networks in near-linear time. In: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), vol. 185, pp. 63:1\u201363:15 (2021)"},{"issue":"1","key":"1112_CR41","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1287\/moor.19.1.53","volume":"19","author":"Y Yinyu","year":"1994","unstructured":"Yinyu, Y., Michael\u00a0J, T., Shinji, M.: An $${O}(\\sqrt{n}{L})$$-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19(1), 53\u201367 (1994)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01112-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01112-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01112-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T12:55:31Z","timestamp":1702212931000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01112-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,11]]},"references-count":41,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1112"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01112-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,11]]},"assertion":[{"value":"27 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}