{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T06:07:49Z","timestamp":1783490869906,"version":"3.55.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T00:00:00Z","timestamp":1716768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T00:00:00Z","timestamp":1716768000000},"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":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10107-024-02099-8","type":"journal-article","created":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T14:04:26Z","timestamp":1716818666000},"page":"3-45","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Information complexity of mixed-integer convex optimization"],"prefix":"10.1007","volume":"210","author":[{"given":"Amitabh","family":"Basu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongyi","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phillip","family":"Kerger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,5,27]]},"reference":[{"key":"2099_CR1","unstructured":"Balcan, M.-F., Long, P.: Active and passive learning of linear separators under log-concave distributions. In: Shalev-Shwartz, S., Steinwart, I. (eds.) Proceedings of the 26th Annual Conference on Learning Theory, Volume 30 of Proceedings of Machine Learning Research, pp. 288\u2013316, Princeton, NJ, USA, 12\u201314. PMLR (2013)"},{"key":"2099_CR2","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s10107-022-01862-z","volume":"200","author":"A Basu","year":"2023","unstructured":"Basu, A.: Complexity of optimizing over the integers. Math. Program. Ser. B 200, 739\u2013780 (2023)","journal-title":"Math. Program. Ser. B"},{"issue":"2","key":"2099_CR3","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/16M1092908","volume":"27","author":"A Basu","year":"2017","unstructured":"Basu, A., Oertel, T.: Centerpoints: a link between optimization and convex geometry. SIAM J. Optim. 27(2), 866\u2013889 (2017)","journal-title":"SIAM J. Optim."},{"key":"2099_CR4","unstructured":"Blanchard, M., Zhang, J., Jaillet, P.: Quadratic memory is necessary for optimal query complexity in convex optimization: Center-of-mass is pareto-optimal. In: Gergely, N., Lorenzo, R. (eds.) Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 4696\u20134736. PMLR, 12\u201315 Jul (2023)"},{"key":"2099_CR5","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1007\/s10898-018-0729-8","volume":"73","author":"AY Chirkov","year":"2019","unstructured":"Chirkov, A.Y., Gribanov, D.V., Malyshev, D.S., Pardalos, P.M., Veselov, S.I., Zolotykh, N.Y.: On the complexity of quasiconvex integer minimization problem. J. Glob. Optim. 73, 761\u2013788 (2019)","journal-title":"J. Glob. Optim."},{"key":"2099_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718768","volume-title":"Introduction to Derivative-free Optimization","author":"AR Conn","year":"2009","unstructured":"Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-free Optimization. SIAM (2009)"},{"key":"2099_CR7","doi-asserted-by":"crossref","unstructured":"Gribanov, D.V., Malyshev, D.S.: Integer conic function minimization based on the comparison oracle. In: International Conference on Mathematical Optimization Theory and Operations Research, pp. 218\u2013231. Springer (2019)","DOI":"10.1007\/978-3-030-22629-9_16"},{"key":"2099_CR8","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1134\/S199047892001007X","volume":"14","author":"DV Gribanov","year":"2020","unstructured":"Gribanov, D.V., Malyshev, D.S.: Minimization of even conic functions on the two-dimensional integral lattice. J. App. Ind. Math. 14, 56\u201372 (2020)","journal-title":"J. App. Ind. Math."},{"key":"2099_CR9","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics: Study and Research Texts. Springer-Verlag, Berlin (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"2099_CR10","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.2140\/pjm.1960.10.1257","volume":"10","author":"B Gr\u00fcnbaum","year":"1960","unstructured":"Gr\u00fcnbaum, B.: Partitions of mass-distributions and of convex bodies by hyperplanes. Pac. J. Math. 10, 1257\u20131261 (1960)","journal-title":"Pac. J. Math."},{"key":"2099_CR11","unstructured":"Jamieson, K.G., Nowak, R.D., Recht, B.: Query complexity of derivative-free optimization. In: Proceedings of the 25th International Conference on Neural Information Processing Systems\u2014Vol. 2, NIPS\u201912, pp. 2672\u20132680, Red Hook, NY, USA, Curran Associates Inc. (2012)"},{"key":"2099_CR12","doi-asserted-by":"crossref","unstructured":"Marsden, A., Sharan, V., Sidford, A., Valiant, G.: Efficient Convex Optimization Requires Superlinear Memory. arXiv preprint:https:\/\/arxiv.org\/pdf\/2203.15260 (2022)","DOI":"10.24963\/ijcai.2023\/722"},{"key":"2099_CR13","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley (1983)"},{"key":"2099_CR14","unstructured":"Oertel, T.: Integer Convex Minimization in Low Dimensions. PhD thesis, Diss., Eidgen\u00f6ssische Technische Hochschule ETH Z\u00fcrich, Nr. 22288 (2014)"},{"issue":"1","key":"2099_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF02312467","volume":"59","author":"VY Protasov","year":"1996","unstructured":"Protasov, V.Y.: Algorithms for approximate calculation of the minimum of a convex function from its values. Math. Notes 59(1), 69\u201374 (1996)","journal-title":"Math. Notes"},{"key":"2099_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.dam.2019.10.006","volume":"283","author":"SI Veselov","year":"2020","unstructured":"Veselov, S.I., Gribanov, D.V., Zolotykh, N.Y., Chirkov, A.Y.: A polynomial algorithm for minimizing discrete convic functions in fixed dimension. Discrete Appl. Math. 283, 11\u201319 (2020)","journal-title":"Discrete Appl. Math."},{"key":"2099_CR17","unstructured":"Woodworth, B., Srebro, N.: Open problem: the oracle complexity of convex optimization with limited memory. In: Conference on Learning Theory, pp. 3202\u20133210. PMLR (2019)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02099-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02099-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02099-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T15:53:27Z","timestamp":1740758007000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02099-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,27]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2099"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02099-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,27]]},"assertion":[{"value":"17 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There are no financial or non-financial interests that are directly or indirectly related to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}