{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:43Z","timestamp":1781077783614,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":27,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188962","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"990-1002","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Extractor-based time-space lower bounds for learning"],"prefix":"10.1145","author":[{"given":"Sumegha","family":"Garg","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Tools from higher algebra. Handbook of combinatorics 2","author":"Alon Noga","year":"1995"},{"key":"e_1_3_2_2_2_1","volume-title":"Shayan Oveis Gharan, and Xin Yang","author":"Beame Paul","year":"2017"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_28"},{"key":"e_1_3_2_2_4_1","unstructured":"Yonatan Bilu and Nathan Linial. 2006.  Yonatan Bilu and Nathan Linial. 2006."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"e_1_3_2_2_6_1","unstructured":"Avrim Blum Merrick Furst Jeffrey Jackson Michael Kearns Yishay Mansour and Steven Rudich. 1994.  Avrim Blum Merrick Furst Jeffrey Jackson Michael Kearns Yishay Mansour and Steven Rudich. 1994."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_2_8_1","unstructured":"Benny Chor and Oded Goldreich. 1988.  Benny Chor and Oded Goldreich. 1988."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_3_2_2_10_1","unstructured":"Sumegha Garg Ran Raz and Avishay Tal. 2017.  Sumegha Garg Ran Raz and Avishay Tal. 2017."},{"key":"e_1_3_2_2_11_1","volume-title":"arXiv preprint arXiv:1708.02639","author":"Time-Space Lower Extractor-Based","year":"2017"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1971-007-1"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488699"},{"key":"e_1_3_2_2_15_1","unstructured":"Gillat Kol Ran Raz and Avishay Tal. 2017.  Gillat Kol Ran Raz and Avishay Tal. 2017."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055430"},{"key":"e_1_3_2_2_17_1","volume-title":"Conference on Learning Theory. 1516\u20131566","author":"Moshkovitz Dana","year":"2017"},{"key":"e_1_3_2_2_18_1","volume-title":"Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018","author":"Moshkovitz Dana","year":"2018"},{"key":"e_1_3_2_2_19_1","volume-title":"Mixing Complexity and its Applications to Neural Networks. arXiv preprint arXiv:1703.00729","author":"Moshkovitz Michal","year":"2017"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060593"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.36"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.73"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715945"},{"key":"e_1_3_2_2_24_1","unstructured":"Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems. 163\u2013171.   Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems. 163\u2013171."},{"key":"e_1_3_2_2_25_1","volume-title":"Conference on Learning Theory. 1490\u20131516","author":"Steinhardt Jacob","year":"2016"},{"key":"e_1_3_2_2_26_1","unstructured":"Gregory Valiant and Paul Valiant. 2016.  Gregory Valiant and Paul Valiant. 2016."},{"key":"e_1_3_2_2_27_1","volume-title":"arXiv preprint arXiv:1605.02646","author":"Information","year":"2016"}],"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.3188962","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:07Z","timestamp":1750208887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":27,"alternative-id":["10.1145\/3188745.3188962","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188962","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"}}]}}