{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T20:24:21Z","timestamp":1730319861377,"version":"3.28.0"},"publisher-location":"New York, NY, USA","reference-count":98,"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":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DST (DST\/SJF\/MSA-01\/2013-14)"},{"name":"Google India Pvt. Ltd."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188762","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1166-1179","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Bootstrapping variables in algebraic circuits"],"prefix":"10.1145","author":[{"given":"Manindra","family":"Agrawal","sequence":"first","affiliation":[{"name":"IIT Kanpur, India"}]},{"given":"Sumanta","family":"Ghosh","sequence":"additional","affiliation":[{"name":"IIT Kanpur, India"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[{"name":"IIT Kanpur, India"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2017990.2017994"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"volume-title":"PRIMES is in P. Annals of mathematics","year":"2004","author":"Agrawal Manindra","key":"e_1_3_2_2_4_1"},{"key":"e_1_3_2_2_5_1","unstructured":"Manindra Agrawal Chandan Saha Ramprasad Saptharishi and Nitin Saxena. 2012. Manindra Agrawal Chandan Saha Ramprasad Saptharishi and Nitin Saxena. 2012."},{"volume-title":"hitting-sets, lower bounds for depth-D occur-k formulas &","author":"Jacobian","key":"e_1_3_2_2_6_1"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488649"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_2_9_1","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Sanjeev Arora and Boaz Barak. 2009."},{"edition":"1","volume-title":"A Modern Approach","author":"Complexity Computational","key":"e_1_3_2_2_10_1"},{"key":"e_1_3_2_2_11_1","unstructured":"M. Beecken J. Mittmann and N. Saxena. 2013. M. Beecken J. Mittmann and N. Saxena. 2013."},{"volume-title":"2\u201319. (Conference version in ICALP","year":"2013","author":"Independence Algebraic","key":"e_1_3_2_2_12_1"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875589"},{"key":"e_1_3_2_2_14_1","unstructured":"Peter B\u00fcrgisser. 2013. Peter B\u00fcrgisser. 2013."},{"volume-title":"Springer Science &","author":"Vol Completeness","key":"e_1_3_2_2_15_1"},{"key":"e_1_3_2_2_16_1","unstructured":"Michael Clausen Andreas Dress Johannes Grabmeier and Marek Karpinski. 1991. Michael Clausen Andreas Dress Johannes Grabmeier and Marek Karpinski. 1991."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90157-W"},{"volume-title":"Lipton","year":"1978","author":"Demillo Richard A.","key":"e_1_3_2_2_18_1"},{"volume-title":"Lett. 7, 4","year":"1978","author":"Inform A","key":"e_1_3_2_2_19_1"},{"key":"e_1_3_2_2_20_1","unstructured":"Rodney G Downey and Michael R Fellows. 2013. Rodney G Downey and Michael R Fellows. 2013."},{"key":"e_1_3_2_2_21_1","unstructured":"Fundamentals of parameterized complexity. Vol. 4. Springer. Fundamentals of parameterized complexity. Vol. 4. Springer."},{"key":"e_1_3_2_2_22_1","unstructured":"Pranjal Dutta Nitin Saxena and Amit Sinhababu. 2017. Pranjal Dutta Nitin Saxena and Amit Sinhababu. 2017."},{"volume-title":"Rafael Mendes de Oliveira, and Amir Shpilka","year":"2014","author":"Dvir Zeev","key":"e_1_3_2_2_24_1"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897564"},{"key":"e_1_3_2_2_26_1","unstructured":"754\u2013763. 754\u2013763."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1994.11996185"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Michael A Forbes. 2015. Michael A Forbes. 2015.","DOI":"10.1002\/14651858.CD006489.pub4"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.35"},{"key":"e_1_3_2_2_30_1","unstructured":"Michael A. Forbes Sumanta Ghosh and Nitin Saxena. 2018. Michael A. Forbes Sumanta Ghosh and Nitin Saxena. 2018."},{"key":"e_1_3_2_2_31_1","unstructured":"Towards blackbox identity testing of log-variate circuits. Technical Report. https:\/\/www.cse.iitk.ac.in\/users\/nitin\/research.html. Towards blackbox identity testing of log-variate circuits. Technical Report. https:\/\/www.cse.iitk.ac.in\/users\/nitin\/research.html."},{"key":"e_1_3_2_2_32_1","unstructured":"Michael A. Forbes Ramprasad Saptharishi and Amir Shpilka. 2014. Michael A. Forbes Ramprasad Saptharishi and Amir Shpilka. 2014."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213995"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188792"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055496"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/070711761"},{"key":"e_1_3_2_2_38_1","unstructured":"Ankit Garg Leonid Gurvits Rafael Oliveira and Avi Wigderson. 2016. Ankit Garg Leonid Gurvits Rafael Oliveira and Avi Wigderson. 2016."},{"volume-title":"Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","year":"2016","author":"A","key":"e_1_3_2_2_39_1"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0103-x"},{"key":"e_1_3_2_2_41_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"55","author":"Grochow Joshua A.","year":"2016"},{"key":"e_1_3_2_2_42_1","unstructured":"Zeyu Guo Nitin Saxena and Amit Sinhababu. 2018. Zeyu Guo Nitin Saxena and Amit Sinhababu. 2018."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.10"},{"key":"e_1_3_2_2_44_1","unstructured":"Ankit Gupta Pritish Kamath Neeraj Kayal and Ramprasad Saptharishi. 2013. Ankit Gupta Pritish Kamath Neeraj Kayal and Ramprasad Saptharishi. 2013."},{"volume-title":"54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013","year":"2013","author":"Circuits Arithmetic","key":"e_1_3_2_2_45_1"},{"key":"e_1_3_2_2_46_1","unstructured":"Rohit Gurjar Arpita Korwar and Nitin Saxena. 2017. Rohit Gurjar Arpita Korwar and Nitin Saxena. 2017."},{"volume-title":"Read-Once Oblivious Arithmetic Branching Programs. Theory of Computing 13, 2","year":"2017","author":"Constant-Width Identity Testing","key":"e_1_3_2_2_47_1"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2015.323"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055440"},{"volume-title":"Vishnoi","year":"2017","author":"Gurjar Rohit","key":"e_1_3_2_2_50_1"},{"key":"e_1_3_2_2_51_1","unstructured":"Joos Heintz and Claus-Peter Schnorr. 1980. Joos Heintz and Claus-Peter Schnorr. 1980."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780595"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_2_56_1","unstructured":"Erich Kaltofen. 1989. Erich Kaltofen. 1989."},{"volume-title":"Randomness and Computation 5","year":"1989","author":"Factorization","key":"e_1_3_2_2_57_1"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"volume-title":"Tsinghua University","year":"2011","author":"Koiran Pascal","key":"e_1_3_2_2_59_1"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0269-1"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0002-8"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.25"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982479"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982480"},{"key":"e_1_3_2_2_65_1","first-page":"77","article-title":"Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees","volume":"24","author":"Lagarde Guillaume","year":"2017","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_66_1","unstructured":"Guillaume Lagarde Guillaume Malod and Sylvain Perifel. 2016. Guillaume Lagarde Guillaume Malod and Sylvain Perifel. 2016."},{"volume-title":"lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC) 23","year":"2016","author":"Noncommutative","key":"e_1_3_2_2_67_1"},{"key":"e_1_3_2_2_68_1","unstructured":"Fran\u00e7ois Le Gall. 2014. Fran\u00e7ois Le Gall. 2014."},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135627"},{"key":"e_1_3_2_2_71_1","unstructured":"Partha Mukhopadhyay. 2016. Partha Mukhopadhyay. 2016."},{"volume-title":"International Computer Science Symposium in Russia. Springer, 309\u2013323","key":"e_1_3_2_2_72_1"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/864"},{"volume-title":"Vazirani","year":"1987","author":"Mulmuley Ketan","key":"e_1_3_2_2_74_1"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_3_2_2_76_1","unstructured":"Ketan D Mulmuley. 2012. Ketan D Mulmuley. 2012."},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"e_1_3_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.15"},{"key":"e_1_3_2_2_79_1","unstructured":"Noam Nisan and Avi Wigderson. 1994. Noam Nisan and Avi Wigderson. 1994."},{"key":"e_1_3_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"volume-title":"41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016","year":"2016","author":"Pandey Anurag","key":"e_1_3_2_2_81_1"},{"key":"e_1_3_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0054-4"},{"key":"e_1_3_2_2_83_1","unstructured":"Ramprasad Saptharishi. 2016. Ramprasad Saptharishi. 2016."},{"key":"e_1_3_2_2_84_1","unstructured":"A survey of lower bounds in arithmetic circuit complexity. Technical Report. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/. A survey of lower bounds in arithmetic circuit complexity. Technical Report. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/."},{"key":"e_1_3_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"e_1_3_2_2_86_1","unstructured":"Nitin Saxena. 2009. Nitin Saxena. 2009."},{"volume-title":"Bulletin of the EATCS 99","year":"2009","author":"Polynomial Identity Testing Progress","key":"e_1_3_2_2_87_1"},{"key":"e_1_3_2_2_88_1","unstructured":"Nitin Saxena. 2013. Nitin Saxena. 2013."},{"volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 20","year":"2013","author":"Polynomial Identity Progress","key":"e_1_3_2_2_89_1"},{"key":"e_1_3_2_2_90_1","unstructured":"Nitin Saxena and C. Seshadhri. 2012. Nitin Saxena and C. Seshadhri. 2012."},{"key":"e_1_3_2_2_91_1","series-title":"SIAM J. Comput. 41, 5","volume-title":"The Field Doesn\u2019t Matter","author":"Bounded Top-Fanin Blackbox Identity","year":"2012"},{"key":"e_1_3_2_2_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_2_94_1","unstructured":"Ola Svensson and Jakub Tarnawski. 2017. Ola Svensson and Jakub Tarnawski. 2017."},{"volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 24","year":"2017","author":"General The Matching","key":"e_1_3_2_2_95_1"},{"key":"e_1_3_2_2_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_2_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/3065468"},{"key":"e_1_3_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.95"},{"key":"e_1_3_2_2_99_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T19:07:01Z","timestamp":1673464021000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":98,"alternative-id":["10.1145\/3188745.3188762","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188762","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"}}]}}