{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:33Z","timestamp":1781028273292,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800904","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1995-2006","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Combinatorial Optimization using Comparison Oracles"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, New-York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8285-8868","authenticated-orcid":false,"given":"Tommaso","family":"d'Orsi","sequence":"additional","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5579-3405","authenticated-orcid":false,"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"New York University, New-York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0963-3843","authenticated-orcid":false,"given":"Guru","family":"Guruganesh","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1454-7587","authenticated-orcid":false,"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9799-5766","authenticated-orcid":false,"given":"Renato Paes","family":"Leme","sequence":"additional","affiliation":[{"name":"Google Research, New-York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2667-9176","authenticated-orcid":false,"given":"Madhusudhan Reddy","family":"Pittu","sequence":"additional","affiliation":[{"name":"New York University, New-York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5392-3560","authenticated-orcid":false,"given":"Jon","family":"Schneider","sequence":"additional","affiliation":[{"name":"Google Research, New-York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00055"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.19"},{"key":"e_1_3_2_1_3_1","unstructured":"Arinta Auza and Troy Lee. 2021. On the query complexity of connectivity with global queries. arXiv preprint arXiv:2109.02115."},{"key":"e_1_3_2_1_4_1","volume-title":"Conference on Learning Theory. 310\u2013335","author":"Balcan Maria-Florina","year":"2016","unstructured":"Maria-Florina Balcan, Ellen Vitercik, and Colin White. 2016. Learning combinatorial functions from pairwise comparisons. In Conference on Learning Theory. 310\u2013335."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12113-003-1012-4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/2334029"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. 1383\u20131394","author":"Bshouty Nader H","year":"2011","unstructured":"Nader H Bshouty and Hanna Mazzawi. 2011. On Parity Check (0, 1)-Matrix over Z_p. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. 1383\u20131394."},{"key":"e_1_3_2_1_8_1","unstructured":"Peter Chen Xi Chen Wotao Yin and Tianyi Lin. 2025. ComPO: Preference Alignment via Comparison Oracles. arxiv:2505.05465. arxiv:2505.05465"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433420"},{"key":"e_1_3_2_1_10_1","volume-title":"Sign-OPT: A Query-Efficient Hard-label Adversarial Attack. In 8th International Conference on Learning Representations, ICLR 2020","author":"Cheng Minhao","year":"2020","unstructured":"Minhao Cheng, Simranjit Singh, Patrick H. Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. 2020. Sign-OPT: A Query-Efficient Hard-label Adversarial Attack. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. https:\/\/openreview.net\/forum?id=SklTQCNtvS"},{"key":"e_1_3_2_1_11_1","volume-title":"Conference on Learning Theory. 797\u2013818","author":"Choi Sung-Soon","year":"2013","unstructured":"Sung-Soon Choi. 2013. Polynomial time optimal query algorithms for finding graphs with arbitrary real weights. In Conference on Learning Theory. 797\u2013818."},{"key":"e_1_3_2_1_12_1","volume-title":"Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, and David P. Woodruff.","author":"Cohen-Addad Vincent","year":"2025","unstructured":"Vincent Cohen-Addad, Tommaso d\u00d3rsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, and David P. Woodruff. 2025. Combinatorial Optimization using Comparison Oracles. arXiv:2511.15142."},{"key":"e_1_3_2_1_13_1","volume-title":"Woodruff","author":"Esfandiari Hossein","year":"2015","unstructured":"Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. 2015. Applications of Uniform Sampling: Densest Subgraph and Beyond. arxiv:1506.04505. arxiv:1506.04505"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2020.64"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/S004530010033"},{"key":"e_1_3_2_1_16_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u2019asz, and Alexander Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization. Springer, 2nd ed.","edition":"2"},{"key":"e_1_3_2_1_17_1","volume-title":"International Conference on Machine Learning. 1871\u20131880","author":"Haghiri Siavash","year":"2018","unstructured":"Siavash Haghiri, Damien Garreau, and Ulrike Luxburg. 2018. Comparison-based random forests. In International Conference on Machine Learning. 1871\u20131880."},{"key":"e_1_3_2_1_18_1","unstructured":"Siavash Haghiri Debarghya Ghoshdastidar and Ulrike von Luxburg. 2017. Comparison-based nearest neighbor search. In Artificial Intelligence and Statistics. 851\u2013859."},{"key":"e_1_3_2_1_19_1","unstructured":"Nicholas James Alexander Harvey. 2008. Matchings matroids and submodular functions. Ph.D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03216919"},{"key":"e_1_3_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems","author":"Jamieson Kevin G.","year":"2012","unstructured":"Kevin G. Jamieson, Robert D. Nowak, and Benjamin Recht. 2012. Query Complexity of Derivative-Free Optimization. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, L\u00e9on Bottou, and Kilian Q. Weinberger (Eds.). 2681\u20132689. https:\/\/proceedings.neurips.cc\/paper\/2012\/hash\/e6d8545daa42d5ced125a4bf747b3688-Abstract.html"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3285953"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.40"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2021.15"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of The 35th International Conference on Algorithmic Learning Theory, Claire Vernade and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research","volume":"807","author":"Liao Hang","year":"2024","unstructured":"Hang Liao and Deeparnab Chakrabarty. 2024. Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries. In Proceedings of The 35th International Conference on Algorithmic Learning Theory, Claire Vernade and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 237). PMLR, 785\u2013807. https:\/\/proceedings.mlr.press\/v237\/liao24b.html"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_27_1","unstructured":"Vilfredo Pareto. 1919. Manuale di economia politica con una introduzione alla scienza sociale. 13 Societ\u00e0 editrice libraria."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192528"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.39"},{"key":"e_1_3_2_1_30_1","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","year":"1908","unstructured":"Alexander Schrijver. 1986. Theory of linear and integer programming. John Wiley & Sons, Inc., USA. isbn:0471908541"},{"key":"e_1_3_2_1_31_1","unstructured":"Zhiwei Tang Dmitry Rybin and Tsung-Hui Chang. 2024. Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles. arxiv:2303.03751. arxiv:2303.03751"},{"key":"e_1_3_2_1_32_1","volume-title":"Noise-tolerant interactive learning using pairwise comparisons. Advances in neural information processing systems, 30","author":"Xu Yichong","year":"2017","unstructured":"Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, and Artur Dubrawski. 2017. Noise-tolerant interactive learning using pairwise comparisons. Advances in neural information processing systems, 30 (2017)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2011.12.028"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2405.11454"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:54:51Z","timestamp":1781027691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":34,"alternative-id":["10.1145\/3798129.3800904","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800904","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}