{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T18:16:57Z","timestamp":1781288217654,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"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":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374479","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"711-720","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Elusive functions and lower bounds for arithmetic circuits"],"prefix":"10.1145","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Weizmann Institute, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389944"},{"key":"e_1_3_2_1_3_1","first-page":"18","volume":"242","author":"Alekhnovich M.","year":"2003","unstructured":"M. Alekhnovich , A. Razborov. Lower Bounds for the Polynomial Calculus: Non--Binomial Case. Proceedings of the Steklov Institute of Mathematics. 242 : 18 -- 35 ( 2003 ) (preliminary version in FOCS 2001) M. Alekhnovich, A. Razborov. Lower Bounds for the Polynomial Calculus: Non--Binomial Case. Proceedings of the Steklov Institute of Mathematics. 242: 18--35 (2003) (preliminary version in FOCS 2001)","journal-title":"Mathematics."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1965416"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808731"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(87)80063-9"},{"key":"e_1_3_2_1_10_1","first-page":"317","volume":"3","author":"J.","year":"1988","unstructured":"J. von zur Gathen. Algebraic Complexity Theory. Ann. Rev. Computer Science 3 : 317 -- 347 ( 1988 ) J. von zur Gathen. Algebraic Complexity Theory. Ann. Rev. Computer Science 3: 317--347 (1988)","journal-title":"Gathen. Algebraic Complexity Theory. Ann. Rev. Computer Science"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"issue":"6","key":"e_1_3_2_1_12_1","first-page":"465","volume":"10","author":"Grigoriev D.","year":"2000","unstructured":"D. Grigoriev , A. A. Razborov. Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions o ver Finite Fields . Applicable Algebra in Engineering , Communication and Computing 10 ( 6 ): 465 -- 487 ( 2000 ) (preliminary version in FOCS 1998) D. Grigoriev, A. A. Razborov. Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Applicable Algebra in Engineering, Communication and Computing 10(6): 465--487 (2000) (preliminary version in FOCS 1998)","journal-title":"Computing"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"S.V. Lokam. Spectral Methods for Matrix Rigidity with Applicationsto Size--Depth Tradeoffs and Communication Complexity. Journal of Computer and System Sciences (2001) (preliminary version in FOCS 1995)   S.V. Lokam. Spectral Methods for Matrix Rigidity with Applicationsto Size--Depth Tradeoffs and Communication Complexity. Journal of Computer and System Sciences (2001) (preliminary version in FOCS 1995)","DOI":"10.1006\/jcss.2001.1786"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225290"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215351"},{"key":"e_1_3_2_1_20_1","volume-title":"A Note on Using the Detrminant for Proving Lower Boundson the Size of Linear Circuits. Electronic Colloquium on Computational Complexity (ECCC),Report No. 42","author":"Pudlak P.","year":"1998","unstructured":"P. Pudlak . A Note on Using the Detrminant for Proving Lower Boundson the Size of Linear Circuits. Electronic Colloquium on Computational Complexity (ECCC),Report No. 42 , 1998 . P. Pudlak. A Note on Using the Detrminant for Proving Lower Boundson the Size of Linear Circuits. Electronic Colloquium on Computational Complexity (ECCC),Report No. 42, 1998."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402147"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007353"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.42"},{"issue":"4","key":"e_1_3_2_1_24_1","first-page":"598","volume":"41","author":"Razborov. Lower A. A.","year":"1987","unstructured":"A. A. Razborov. Lower Bounds on the Size of Bounded-- Depth Networks over a Complete Basis with Logical Addition (in Russian). Matematicheskie Zametki , 41 ( 4 ): 598 -- 607 ( 1987 ). English translation in Mathematical Notes of the Academy of Sci. of the USSR 41(4): 333--338, 1987 A. A. Razborov. Lower Bounds on the Size of Bounded--Depth Networks over a Complete Basis with Logical Addition (in Russian). Matematicheskie Zametki, 41(4): 598--607 (1987). English translation in Mathematical Notes of the Academy of Sci. of the USSR 41(4): 333--338, 1987","journal-title":"Matematicheskie Zametki"},{"key":"e_1_3_2_1_25_1","first-page":"344","volume":"13","author":"Razborov. Bounded Arithmetic A. A.","year":"1995","unstructured":"A. A. Razborov. Bounded Arithmetic and Lower Bounds in Boolean Complexity . Feasible Mathematics II. Progress in Computer Science and Applied Logic , 13 : 344 -- 386 ( 1995 ) A. A. Razborov. Bounded Arithmetic and Lower Bounds in Boolean Complexity. Feasible Mathematics II. Progress in Computer Science and Applied Logic, 13: 344--386 (1995)","journal-title":"Applied Logic"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138462X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"R. Raz A. Yehudayoff. Multilinear Formulas Maximal--Partition Discrepancy and Mixed--Sources Extractors. Manuscript 2007.  R. Raz A. Yehudayoff. Multilinear Formulas Maximal--Partition Discrepancy and Mixed--Sources Extractors. Manuscript 2007.","DOI":"10.1109\/FOCS.2008.22"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203010"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90010-9"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185394"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_3_2_1_35_1","first-page":"1","volume":"1985","author":"Yao A. C. C.","unstructured":"A. C. C. Yao . Separating the Polynomial-- Time Hierarchy by Oracles FOCS 1985 : 1 -- 10 A. C. C. Yao. Separating the Polynomial--Time Hierarchy by Oracles FOCS 1985: 1--10","journal-title":"Oracles FOCS"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","location":"Victoria British Columbia Canada","acronym":"STOC '08","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374479","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:50Z","timestamp":1750255070000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":35,"alternative-id":["10.1145\/1374376.1374479","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374479","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}