{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:24Z","timestamp":1781028264063,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":36,"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"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-2232692"],"award-info":[{"award-number":["CNS-2232692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-2247484"],"award-info":[{"award-number":["CNS-2247484"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","award":["CRC-2020-00004"],"award-info":[{"award-number":["CRC-2020-00004"]}],"id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2021-03206"],"award-info":[{"award-number":["RGPIN-2021-03206"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800931","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2302-2313","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3435-7502","authenticated-orcid":false,"given":"Aleksandar","family":"Nikolov","sequence":"first","affiliation":[{"name":"University of Toronto, Department of Computer Science, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3454-3631","authenticated-orcid":false,"given":"Haohua","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Toronto, Department of Computer Science, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0323-5564","authenticated-orcid":false,"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[{"name":"Northeastern University, Khoury College of Computer Sciences, Boston, 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.1145\/3406325.3450994"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Wojciech Banaszczyk. 1998. Balancing vectors and Gaussian measures of-dimensional convex bodies. Random Structures and Algorithms 12 4 ( 1998 ) 351-360.","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc"},{"key":"e_1_3_2_1_4_1","unstructured":"Nikhil Bansal and Haotian Jiang. 2025. Decoupling via Afine SpectralIndependence: Beck-Fiala and Koml\u00f3s Bounds Beyond Banaszczyk. arXiv: 2508.03961 [math.CO] https:\/\/arxiv.org\/abs\/2508.03961"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20955"},{"key":"e_1_3_2_1_6_1","first-page":"115","volume-title":"Ser. A 26, 2 ( 1979 )","author":"B\u00e1r\u00e1ny Imre","unstructured":"Imre B\u00e1r\u00e1ny. 1979. On a Class of Balancing Games. J. Comb. Theory, Ser. A 26, 2 ( 1979 ), 115-126."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.85"},{"key":"e_1_3_2_1_12_1","first-page":"1","volume-title":"Fingerprinting Codes and the Price of Approximate Diferential Privacy. In 46th Annual ACM Symposium on the Theory of Computing (STOC '14)","author":"Bun Mark","year":"2014","unstructured":"Mark Bun, Jonathan Ullman, and Salil Vadhan. 2014. Fingerprinting Codes and the Price of Approximate Diferential Privacy. In 46th Annual ACM Symposium on the Theory of Computing (STOC '14). New York, NY, USA, 1-10."},{"key":"e_1_3_2_1_13_1","article-title":"Private and continual release of statistics","volume":"14","author":"Hubert Chan T-H","year":"2011","unstructured":"T-H Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC) 14, 3 ( 2011 ), 26.","journal-title":"ACM Transactions on Information and System Security (TISSEC)"},{"key":"e_1_3_2_1_14_1","volume-title":"Tight Hardness Results for Minimizing Discrepancy. In ACM-SIAM Symposium on Discrete Algorithms, SODA. 1607-1614","author":"Charikar Moses","year":"2011","unstructured":"Moses Charikar, Alantha Newman, and Aleksandar Nikolov. 2011. Tight Hardness Results for Minimizing Discrepancy. In ACM-SIAM Symposium on Discrete Algorithms, SODA. 1607-1614."},{"key":"e_1_3_2_1_15_1","volume-title":"September 2017 meeting of the Census Scientific Advisory Committee.","author":"Dajani Aref N.","unstructured":"Aref N. Dajani, Amy D. Lauger, Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin Machanavajjhala, Simson L. Garfinkel, Scot A. Dahl, Matthew Graham, Vishesh Karwa, Hang Kim, Philip Lelerc, Ian M. Schmutte, William N. Sexton, Lars Vilhuber, and John M. Abowd. 2017. The Modernization of Statistical Disclosure Limitation at the U.S. Census Bureau. Presented at the September 2017 meeting of the Census Scientific Advisory Committee."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_17_1","first-page":"715","volume-title":"Diferential Privacy Under Continual Observation. In Symposium on Theory of Computing (STOC)","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Diferential Privacy Under Continual Observation. In Symposium on Theory of Computing (STOC) (Cambridge, Massachusetts, USA). ACM, 715-724."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384297"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Reza Eghbali James Saunderson and Maryam Fazel. 2018. Competitive online algorithms for resource allocation over the positive semidefinite cone. Math. Program. 170 1 ( 2018 ) 267-292. doi: 10.1007\/s10107-018-1305-1 10.1007\/s10107-018-1305-1","DOI":"10.1007\/s10107-018-1305-1"},{"key":"e_1_3_2_1_20_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming. LIPIcs. Leibniz Int. Proc. Inform.","volume":"55","author":"Elad Noa","year":"2016","unstructured":"Noa Elad, Satyen Kale, and Joseph Naor. 2016. Online semidefinite programming. In 43rd International Colloquium on Automata, Languages, and Programming. LIPIcs. Leibniz Int. Proc. Inform., Vol. 55. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 40, 13."},{"key":"e_1_3_2_1_21_1","first-page":"339","volume-title":"Iterative Constructions and Private Data Release. In 9th IACR Theory of Cryptography Conference (TCC '12)","author":"Gupta Anupam","year":"2012","unstructured":"Anupam Gupta, Aaron Roth, and Jonathan Ullman. 2012. Iterative Constructions and Private Data Release. In 9th IACR Theory of Cryptography Conference (TCC '12). Springer, Taormina, Italy, 339-356."},{"key":"e_1_3_2_1_22_1","volume-title":"Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt, Katrina Ligett, and Frank McSherry. 2012. A Simple and Practical Algorithm for Diferentially Private Data Release. 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. 2348-2356."},{"key":"e_1_3_2_1_23_1","first-page":"61","article-title":"A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis","author":"Hardt Moritz","year":"2014","unstructured":"Moritz Hardt and Guy Rothblum. 2014. A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. In FOCS. 61-70.","journal-title":"FOCS."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649720"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.9"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Christian Janos Lebeda and Jakub Tetek. 2024. Better Diferentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch. SIGMOD Rec. 53 1 ( 2024 ) 7-14. doi: 10.1145\/3665252.3665255 10.1145\/3665252.3665255","DOI":"10.1145\/3665252.3665255"},{"key":"e_1_3_2_1_27_1","first-page":"123","volume-title":"Proceedings of the 29th ACM Symposium on Principles of Database Systems (PODS'10)","author":"Li Chao","year":"2010","unstructured":"Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. 2010. Optimizing linear counting queries under diferential privacy. In Proceedings of the 29th ACM Symposium on Principles of Database Systems (PODS'10). ACM, 123-134."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Nati Linial Shahar Mendelson Gideon Schechtman and Adi Shraibman. 2007. Complexity measures of sign matrices. Combinatorica 27 4 ( 2007 ) 439-463.","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rny033"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.791"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214090"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938943"},{"key":"e_1_3_2_1_33_1","first-page":"1","article-title":"General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. In ITCS (LIPIcs, Vol. 287 )","volume":"85","author":"Nikolov Aleksandar","year":"2024","unstructured":"Aleksandar Nikolov and Haohua Tang. 2024. General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. In ITCS (LIPIcs, Vol. 287 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 85 : 1-85 : 23.","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_34_1","first-page":"765","article-title":"Interactive privacy via the median mechanism","author":"Roth Aaron","year":"2010","unstructured":"Aaron Roth and Tim Roughgarden. 2010. Interactive privacy via the median mechanism. In STOC. ACM, 765-774.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90057-0"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE"}],"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.3800931","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:56Z","timestamp":1781027756000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":36,"alternative-id":["10.1145\/3798129.3800931","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800931","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"}}]}}