{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:01:12Z","timestamp":1753437672529,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":76,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520025","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"389-402","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals"],"prefix":"10.1145","author":[{"given":"Robert","family":"Andrews","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}]},{"given":"Michael A.","family":"Forbes","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.21"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384245"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170709"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0097-4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.37"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365667"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90113-3"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-021-00209-y"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.29"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-002-0059-5"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294258"},{"key":"#cr-split#-e_1_3_2_1_16_1.1","unstructured":"Chi-Ning Chou Mrinal Kumar and Noam Solomon. 2019. Closure of VP under taking factors: a short and simple proof. https:\/\/doi.org\/10.48550\/arXiv.1903.02366 arXiv:1903.02366. 10.48550\/arXiv.1903.02366"},{"key":"#cr-split#-e_1_3_2_1_16_1.2","unstructured":"Chi-Ning Chou Mrinal Kumar and Noam Solomon. 2019. Closure of VP under taking factors: a short and simple proof. https:\/\/doi.org\/10.48550\/arXiv.1903.02366 arXiv:1903.02366."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a013"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"volume-title":"varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4 ed.)","author":"Cox David A.","key":"e_1_3_2_1_19_1","unstructured":"David A. Cox , John Little , and Donal O\u2019Shea . 2015. Ideals , varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4 ed.) . Springer . isbn:978-3-319-16720-6 David A. Cox, John Little, and Donal O\u2019Shea. 2015. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (4 ed.). Springer. isbn:978-3-319-16720-6"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01392548"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(78)90077-4"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1974533185"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00018"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.11"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188760"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735850"},{"key":"e_1_3_2_1_28_1","unstructured":"Michael A. Forbes. 2016. Some concrete questions on the border complexity of polynomials. Talk presented at the Workshop on Algebraic Complexity Theory (WACT) Tel Aviv  Michael A. Forbes. 2016. Some concrete questions on the border complexity of polynomials. Talk presented at the Workshop on Algebraic Complexity Theory (WACT) Tel Aviv"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188792"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.32"},{"key":"e_1_3_2_1_33_1","unstructured":"Joshua A. Grochow. 2020. Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bull. EATCS.  Joshua A. Grochow. 2020. Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs. Bull. EATCS."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230742"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.4"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a016"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a002"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0141-z"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394754"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28443"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/110824516"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2537-3"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.67"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press. isbn:9781108416849  Jan Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press. isbn:9781108416849","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00083"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.1997.005"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.19"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196836"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0130-2"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0131-1"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.8"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451013"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984450.2984455"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.50"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451010"},{"key":"e_1_3_2_1_63_1","unstructured":"Ramprasad Saptharishi. 2019. A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey  Ramprasad Saptharishi. 2019. A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3460-4"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770679"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/10848232"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528403"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316341"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.33"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_74_1","unstructured":"Finn Wiersig. 2020. Sparse Polynomials in Polynomial Ideals.  Finn Wiersig. 2020. Sparse Polynomials in Polynomial Ideals."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520025","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":76,"alternative-id":["10.1145\/3519935.3520025","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520025","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}