{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:43Z","timestamp":1781078263969,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2009060"],"award-info":[{"award-number":["CCF-2009060"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649718","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"479-490","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Limitations of Stochastic Selection Problems with Pairwise Independent Priors"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2784-1868","authenticated-orcid":false,"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9524-4677","authenticated-orcid":false,"given":"Yusuf Hakan","family":"Kalayci","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1942-778X","authenticated-orcid":false,"given":"Neel","family":"Patel","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS). 251","author":"Abdolazimi Dorna","year":"2023","unstructured":"Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. 2023. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS). 251, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 2:1\u20132:9."},{"key":"e_1_3_2_1_2_1","volume-title":"Patras","author":"Adamczyk Marek","year":"2015","unstructured":"Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. 2015. Improved approximation algorithms for stochastic matching. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. 1\u201312."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00080"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89575"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 10th ACM Conference on Recommender Systems. Association for Computing Machinery","author":"Askalidis Georgios","unstructured":"Georgios Askalidis and Edward C. Malthouse. 2016. The Value of Online Customer Reviews. In Proceedings of the 10th ACM Conference on Recommender Systems. Association for Computing Machinery, New York, NY, USA. 155\u2013158."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.135"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399554"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283429"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Maryam Bahrani Hedyeh Beyhaghi Sahil Singla and S. Matthew Weinberg. 2022. Formal Barriers to Simple Algorithms for the Matroid Secretary Problem. In Web and Internet Economics Michal Feldman Hu Fu and Inbal Talgam-Cohen (Eds.). 280\u2013298.","DOI":"10.1007\/978-3-030-94676-0_16"},{"key":"e_1_3_2_1_13_1","volume-title":"Patras","author":"Bateni MohammadHossein","year":"2015","unstructured":"MohammadHossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, and Saeed Seddighin. 2015. Revenue maximization for selling multiple correlated items. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. 95\u2013105."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0383-4"},{"key":"e_1_3_2_1_15_1","volume-title":"Delegated Stochastic Probing. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. 185","author":"Bechtel Curtis","year":"2021","unstructured":"Curtis Bechtel and Shaddin Dughmi. 2021. Delegated Stochastic Probing. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. 185, 37:1\u201337:19."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538267"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.13"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467643"},{"key":"e_1_3_2_1_19_1","volume-title":"Prophet Inequality, and Random Bipartite Matching. In Web and Internet Economics, Michal Feldman, Hu Fu, and Inbal Talgam-Cohen (Eds.)","author":"Caragiannis Ioannis","unstructured":"Ioannis Caragiannis, Nick Gravin, Pinyan Lu, and Zihe Wang. 2022. Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching. In Web and Internet Economics, Michal Feldman, Hu Fu, and Inbal Talgam-Cohen (Eds.). Springer International Publishing, 131\u2013148."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, New York, NY, USA. 311\u2013320."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.82"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the forty-third annual ACM symposium on Theory of computing. 783\u2013792","author":"Chekuri Chandra","year":"2011","unstructured":"Chandra Chekuri, Jan Vondr\u00e1k, and Rico Zenklusen. 2011. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third annual ACM symposium on Theory of computing. 783\u2013792."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491557"},{"key":"e_1_3_2_1_25_1","volume-title":"47th International Colloquium on Automata, Languages and Programming (ICALP). 168","author":"Dughmi Shaddin","year":"2020","unstructured":"Shaddin Dughmi. 2020. The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem. In 47th International Colloquium on Automata, Languages and Programming (ICALP). 168, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 42:1\u201342:18."},{"key":"e_1_3_2_1_26_1","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS). 215","author":"Dughmi Shaddin","year":"2022","unstructured":"Shaddin Dughmi. 2022. Matroid Secretary Is Equivalent to Contention Resolution. In 13th Innovations in Theoretical Computer Science Conference (ITCS). 215, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 58:1\u201358:23."},{"key":"e_1_3_2_1_27_1","volume-title":"Yusuf Hakan Kalayci, and Neel Patel","author":"Dughmi Shaddin","year":"2023","unstructured":"Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. 2023. Limitations of Stochastic Selection Problems with Pairwise Independent Priors. arXiv preprint arXiv:2310.05240."},{"key":"e_1_3_2_1_28_1","volume-title":"50th International Colloquium on Automata, Languages and Programming (ICALP). 261","author":"Dughmi Shaddin","year":"2023","unstructured":"Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. 2023. On Sparsification of Stochastic Packing Problems. In 50th International Colloquium on Automata, Languages and Programming (ICALP). 261, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 51:1\u201351:17."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399513"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.135"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_3_2_1_34_1","volume-title":"Pairwise Independent Contention Resolution. In The 25th Conference on Integer Programming and Combinatorial Optimization (IPCO). Springer International Publishing, Cham.","author":"Gupta Anupam","year":"2024","unstructured":"Anupam Gupta, Jinqiao Hu, and Roie Levin Gregory Kehne. 2024. Pairwise Independent Contention Resolution. In The 25th Conference on Integer Programming and Combinatorial Optimization (IPCO). Springer International Publishing, Cham."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601986719"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/125\/1160620"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399452"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_22"},{"key":"e_1_3_2_1_39_1","unstructured":"Joseph Naor Aravind Srinivasan and David Wajc. 2023. Online Dependent Rounding Schemes. arxiv:2301.08680."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195409"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219205"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA).","author":"Lee Euiwoong","year":"2018","unstructured":"Euiwoong Lee and Sahil Singla. 2018. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1197169"},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC \u201990)","author":"Naor J.","unstructured":"J. Naor and M. Naor. 1990. Small-Bias Probability Spaces: Efficient Constructions and Applications. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC \u201990). New York, NY, USA. 213\u2013223."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32726-1_27"},{"key":"e_1_3_2_1_47_1","volume-title":"Matroid theory. 3","author":"Oxley James G","unstructured":"James G Oxley. 2006. Matroid theory. 3, Oxford University Press, USA."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1481722.1481728"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538295"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/lnms\/1215461961"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.110"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/110852061"},{"key":"e_1_3_2_1_53_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science, 7, 1\u20133","author":"Vadhan Salil P.","year":"2012","unstructured":"Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science, 7, 1\u20133 (2012), 1\u2013336."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":54,"alternative-id":["10.1145\/3618260.3649718","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649718","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}