{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:14Z","timestamp":1781078414992,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Villum Foundation","award":["13163"],"award-info":[{"award-number":["13163"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188830","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1297-1306","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Tight cell probe bounds for succinct Boolean matrix-vector multiplication"],"prefix":"10.1145","author":[{"given":"Diptarka","family":"Chakraborty","sequence":"first","affiliation":[{"name":"Charles University in Prague, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lior","family":"Kamma","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"50","article-title":"Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search","volume":"24","author":"Boninger Joe","year":"2017","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488707"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a019"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.71"},{"key":"e_1_3_2_2_5_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006"},{"key":"e_1_3_2_2_6_1","volume-title":"ed.)","author":"Elements"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_12_1","unstructured":"Guy Joseph Jacobson. 1988.  Guy Joseph Jacobson. 1988."},{"key":"e_1_3_2_2_13_1","volume-title":"Carnegie Mellon University","author":"Data Structures Succinct Static"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213987"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Kasper Green Larsen. 2012.  Kasper Green Larsen. 2012.","DOI":"10.3726\/85613_43"},{"key":"e_1_3_2_2_16_1","volume-title":"Cell Probe Lower Bounds for Evaluating Polynomials. In 53rd Annual IEEE Symposium on Foundations of Computer Science. 293\u2013301","author":"Higher"},{"key":"e_1_3_2_2_17_1","unstructured":"Kasper Green Larsen Omri Weinstein and Huacheng Yu. 2017.  Kasper Green Larsen Omri Weinstein and Huacheng Yu. 2017."},{"key":"e_1_3_2_2_18_1","volume-title":"CoRR abs\/1703.03575","author":"Logarithmic Crossing","year":"2017"},{"key":"e_1_3_2_2_19_1","volume-title":"Faster Online Matrix-Vector Multiplication. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Larsen Kasper Green","year":"2017"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/09075336X"},{"key":"e_1_3_2_2_21_1","volume-title":"Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 305\u2013313","author":"\u015fcu Mihai P","year":"2008"},{"key":"e_1_3_2_2_22_1","volume-title":"Proc. 21st ACM\/SIAM Symposium on Discrete Algorithms (SODA). 117\u2013122","author":"\u015fcu Mihai P","year":"2010"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_2_2_24_1","unstructured":"Mihai P \u02c7 atra\u015fcu and Mikkel Thorup. 2011.  Mihai P \u02c7 atra\u015fcu and Mikkel Thorup. 2011."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993711"},{"key":"e_1_3_2_2_26_1","first-page":"40","article-title":"Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers","volume":"24","author":"Ramamoorthy Sivaramakrishnan Natarajan","year":"2017","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_27_1","unstructured":"C. E. Shannon. 1948.  C. E. Shannon. 1948."},{"key":"e_1_3_2_2_28_1","volume-title":"Bell system technical journal 27","author":"A","year":"1948"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.41"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_3_2_2_31_1","unstructured":"Andrew Chi-Chih Yao. 1981.  Andrew Chi-Chih Yao. 1981."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188830","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":31,"alternative-id":["10.1145\/3188745.3188830","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188830","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}