{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:47Z","timestamp":1775282327713,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>The class FORMULA[s]\u2218G consists of Boolean functions computable by size-<jats:italic>s<\/jats:italic>De Morgan formulas whose leaves are any Boolean functions from a class G. We give<jats:italic>lower bounds<\/jats:italic>and (SAT, Learning, and<jats:bold>pseudorandom generators<\/jats:bold>(<jats:bold>PRG<\/jats:bold><jats:bold>s<\/jats:bold>))<jats:italic>algorithms<\/jats:italic>for FORMULA[n<jats:sup>1.99<\/jats:sup>]\u2218G, for classes G of functions with<jats:italic>low communication complexity<\/jats:italic>. Let R<jats:sup>(k)<\/jats:sup>G be the maximum<jats:italic>k<\/jats:italic>-party number-on-forehead randomized communication complexity of a function in G. Among other results, we show the following:<jats:list><jats:list-item><jats:label>\u2022<\/jats:label><jats:p>The Generalized Inner Product function GIP<jats:sup>k<\/jats:sup><jats:sub>n<\/jats:sub>cannot be computed in FORMULA[s]\u00b0 G on more than 1\/2+\u03b5 fraction of inputs for<\/jats:p><jats:p>s=o(n<jats:sup>2<\/jats:sup>\/k\u22c54<jats:sup>k<\/jats:sup>\u22c5R<jats:sup>(k)<\/jats:sup>(G)\u22c5log\u2061(n\/\u03b5)\u22c5log\u2061(1\/\u03b5))<jats:sup>2<\/jats:sup>).<\/jats:p><jats:p>This significantly extends the lower bounds against bipartite formulas obtained by\u00a0[62]. As a corollary, we get an average-case lower bound for GIP<jats:sup>k<\/jats:sup><jats:sub>n<\/jats:sub>against FORMULA[n<jats:sup>1.99<\/jats:sup>]\u2218PTF<jats:sup><jats:italic>k<\/jats:italic>\u22121<\/jats:sup>, i.e., sub-quadratic-size De Morgan formulas with degree-k-1)<jats:bold>PTF<\/jats:bold>(<jats:bold>polynomial threshold function<\/jats:bold>) gates at the bottom. Previously, it was open whether a super-linear lower bound holds for AND of PTFs.<\/jats:p><\/jats:list-item><jats:list-item><jats:label>\u2022<\/jats:label><jats:p>There is a PRG of seed length n\/2+O(s\u22c5R<jats:sup>(2)<\/jats:sup>(G)\u22c5log\u2061(s\/\u03b5)\u22c5log\u2061(1\/\u03b5)) that \u03b5-fools FORMULA[s]\u2218G. For the special case of FORMULA[s]\u2218LTF, i.e., size-<jats:italic>s<\/jats:italic>formulas with<jats:bold>LTF<\/jats:bold>(<jats:bold>linear threshold function<\/jats:bold>) gates at the bottom, we get the better seed length O(n<jats:sup>1\/2<\/jats:sup>\u22c5s<jats:sup>1\/4<\/jats:sup>\u22c5log\u2061(n)\u22c5log\u2061(n\/\u03b5)). In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of<jats:italic>n<\/jats:italic>halfspaces in the regime where \u03b5\u22641\/n, complementing a recent result of\u00a0[45].<\/jats:p><\/jats:list-item><jats:list-item><jats:label>\u2022<\/jats:label><jats:p>There exists a randomized 2<jats:sup>n-t<\/jats:sup>#SAT algorithm for FORMULA[s]\u2218G, where<\/jats:p><jats:p>t=\u03a9(n\\\u221as\u22c5log<jats:sup>2<\/jats:sup>\u2061(s)\u22c5R<jats:sup>(2)<\/jats:sup>(G))\/1\/2.<\/jats:p><jats:p>In particular, this implies a nontrivial #SAT algorithm for FORMULA[n<jats:sup>1.99<\/jats:sup>]\u2218LTF.<\/jats:p><\/jats:list-item><jats:list-item><jats:label>\u2022<\/jats:label><jats:p>The Minimum Circuit Size Problem is not in FORMULA[n<jats:sup>1.99<\/jats:sup>]\u2218XOR; thereby making progress on hardness magnification, in connection with results from\u00a0[14, 46]. On the algorithmic side, we show that the concept class FORMULA[n<jats:sup>1.99<\/jats:sup>]\u2218XOR can be PAC-learned in time 2<jats:sup><jats:italic>O(n\/log n)<\/jats:italic><\/jats:sup>.<\/jats:p><\/jats:list-item><\/jats:list><\/jats:p>","DOI":"10.1145\/3470861","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates"],"prefix":"10.1145","volume":"13","author":[{"given":"Valentine","family":"Kabanets","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, BC, Canada"}]},{"given":"Sajin","family":"Koroth","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, BC, Canada"}]},{"given":"Zhenjian","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}]},{"given":"Dimitrios","family":"Myrisiotis","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}]},{"given":"Igor C.","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Tighter connections between formula-SAT and shaving logs","volume":"8","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Karl Bringmann . 2018 . Tighter connections between formula-SAT and shaving logs . In ICALP. 8 : 1 \u2013 8 :18. Amir Abboud and Karl Bringmann. 2018. Tighter connections between formula-SAT and shaving logs. In ICALP. 8:1\u20138:18.","journal-title":"ICALP."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud Aviad Rubinstein and R. Ryan Williams. 2017. Distributed PCP theorems for hardness of approximation in P. In FOCS. 25\u201336. Amir Abboud Aviad Rubinstein and R. Ryan Williams. 2017. Distributed PCP theorems for hardness of approximation in P. In FOCS. 25\u201336.","DOI":"10.1109\/FOCS.2017.12"},{"key":"e_1_2_1_3_1","volume-title":"Richard Ryan Williams, and Huacheng Yu","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud , Richard Ryan Williams, and Huacheng Yu . 2015 . More applications of the polynomial method to algorithm design. In SODA. 218\u2013230. Amir Abboud, Richard Ryan Williams, and Huacheng Yu. 2015. More applications of the polynomial method to algorithm design. In SODA. 218\u2013230."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Josh Alman Timothy M. Chan and R. Ryan Williams. 2016. Polynomial representations of threshold functions and algorithmic applications. In FOCS. 467\u2013476. Josh Alman Timothy M. Chan and R. Ryan Williams. 2016. Polynomial representations of threshold functions and algorithmic applications. In FOCS. 467\u2013476.","DOI":"10.1109\/FOCS.2016.57"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958051"},{"key":"e_1_2_1_7_1","first-page":"63","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of -schemes","volume":"42","author":"Andreev Alexander E.","year":"1987","unstructured":"Alexander E. Andreev . 1987 . On a method for obtaining more than quadratic effective lower bounds for the complexity of -schemes . Moscow Univeristy Mathematics Bulletin 42 , 1 (1987), 63 \u2013 66 . Alexander E. Andreev. 1987. On a method for obtaining more than quadratic effective lower bounds for the complexity of -schemes. Moscow Univeristy Mathematics Bulletin 42, 1 (1987), 63\u201366.","journal-title":"Moscow Univeristy Mathematics Bulletin"},{"key":"e_1_2_1_8_1","unstructured":"Roy Armoni Michael E. Saks Avi Wigderson and Shiyu Zhou. 1996. Discrepancy Sets and Pseudorandom generators for combinatorial rectangles. In FOCS. 412\u2013421. Roy Armoni Michael E. Saks Avi Wigderson and Shiyu Zhou. 1996. Discrepancy Sets and Pseudorandom generators for combinatorial rectangles. In FOCS. 412\u2013421."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_2_1_11_1","volume-title":"Wu","author":"Boneh Dan","year":"2018","unstructured":"Dan Boneh , Yuval Ishai , Alain Passel\u00e8gue , Amit Sahai , and David J . Wu . 2018 . Exploring crypto dark matter: New simple PRF candidates and their applications. In TCC. 699\u2013729. Dan Boneh, Yuval Ishai, Alain Passel\u00e8gue, Amit Sahai, and David J. Wu. 2018. Exploring crypto dark matter: New simple PRF candidates and their applications. In TCC. 699\u2013729."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1313-z"},{"key":"e_1_2_1_13_1","first-page":"1","article-title":"On the hardness of approximate and exact (Bichromatic) maximum inner product","volume":"14","author":"Chen Lijie","year":"2018","unstructured":"Lijie Chen . 2018 . On the hardness of approximate and exact (Bichromatic) maximum inner product . In CCC. 14 : 1 \u2013 14 :45. Lijie Chen. 2018. On the hardness of approximate and exact (Bichromatic) maximum inner product. In CCC. 14:1\u201314:45.","journal-title":"CCC."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Lijie Chen Ce Jin and Ryan Williams. 2019. Hardness magnification for all sparse NP languages. In FOCS. 1240\u20131255. Lijie Chen Ce Jin and Ryan Williams. 2019. Hardness magnification for all sparse NP languages. In FOCS. 1240\u20131255.","DOI":"10.1109\/FOCS.2019.00077"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Classical algorithms from quantum and Arthur-Merlin communication protocols","volume":"23","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen and Ruosong Wang . 2019 . Classical algorithms from quantum and Arthur-Merlin communication protocols . In ITCS. 23 : 1 \u2013 23 :20. Lijie Chen and Ruosong Wang. 2019. Classical algorithms from quantum and Arthur-Merlin communication protocols. In ITCS. 23:1\u201323:20.","journal-title":"ITCS."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0100-0"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Circuit lower bounds for MCSP from local pseudorandom generators","volume":"39","author":"Cheraghchi Mahdi","year":"2019","unstructured":"Mahdi Cheraghchi , Valentine Kabanets , Zhenjian Lu , and Dimitrios Myrisiotis . 2019 . Circuit lower bounds for MCSP from local pseudorandom generators . In ICALP. 39 : 1 \u2013 39 :14. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. 2019. Circuit lower bounds for MCSP from local pseudorandom generators. In ICALP. 39:1\u201339:14.","journal-title":"ICALP."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211037"},{"key":"e_1_2_1_19_1","volume-title":"Hirsch","author":"Dantsin Evgeny","year":"2009","unstructured":"Evgeny Dantsin and Edward A . Hirsch . 2009 . Worst-case upper bounds.Handbook of Satisfiability , Vol. 185 (2009), 403\u2013424. Evgeny Dantsin and Edward A. Hirsch. 2009. Worst-case upper bounds.Handbook of Satisfiability, Vol. 185 (2009), 403\u2013424."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-017-0159-x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a008"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Yoav Freund. 1990. Boosting a weak learning algorithm by majority. In COLT. 202\u2013216. Yoav Freund. 1990. Boosting a weak learning algorithm by majority. In COLT. 202\u2013216.","DOI":"10.1016\/B978-1-55860-146-8.50019-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0166-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Parikshit Gopalan Ryan O'Donnell Yi Wu and David Zuckerman. 2010. Fooling functions of halfspaces under product distributions. In CCC. 223\u2013234. Parikshit Gopalan Ryan O'Donnell Yi Wu and David Zuckerman. 2010. Fooling functions of halfspaces under product distributions. In CCC. 223\u2013234.","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In STOC. 212\u2013219. Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In STOC. 212\u2013219.","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20786"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Peter H\u00f8yer Troy Lee and Robert Spalek. 2007. Negative weights make adversaries stronger. In STOC. 526\u2013535. Peter H\u00f8yer Troy Lee and Robert Spalek. 2007. Negative weights make adversaries stronger. In STOC. 526\u2013535.","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo Raghu Meka and David Zuckerman. 2012. Pseudorandomness from Shrinkage. In FOCS. 111\u2013119. Russell Impagliazzo Raghu Meka and David Zuckerman. 2012. Pseudorandomness from Shrinkage. In FOCS. 111\u2013119.","DOI":"10.1109\/FOCS.2012.78"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040202"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo Noam Nisan and Avi Wigderson. 1994. Pseudorandomness for network algorithms. In STOC. 356\u2013364. Russell Impagliazzo Noam Nisan and Avi Wigderson. 1994. Pseudorandomness for network algorithms. In STOC. 356\u2013364.","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_33_1","volume-title":"Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics","author":"Jukna Stasys","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics , Vol. 27 . Springer . Stasys Jukna. 2012. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, Vol. 27. Springer."},{"key":"e_1_2_1_34_1","first-page":"165","article-title":"Derandomization: A brief overview","volume":"1","author":"Kabanets Valentine","year":"2002","unstructured":"Valentine Kabanets . 2002 . Derandomization: A brief overview . Current Trends in Theoretical Computer Science 1 (2002), 165 \u2013 188 . Valentine Kabanets. 2002. Derandomization: A brief overview. Current Trends in Theoretical Computer Science 1 (2002), 165\u2013188.","journal-title":"Current Trends in Theoretical Computer Science"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"Satisfiability and derandomization for small polynomial threshold circuits","volume":"46","author":"Kabanets Valentine","year":"2018","unstructured":"Valentine Kabanets and Zhenjian Lu . 2018 . Satisfiability and derandomization for small polynomial threshold circuits . In APPROX\/RANDOM. 46 : 1 \u2013 46 :19. Valentine Kabanets and Zhenjian Lu. 2018. Satisfiability and derandomization for small polynomial threshold circuits. In APPROX\/RANDOM. 46:1\u201346:19.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_2_1_37_1","unstructured":"Adam Tauman Kalai Yishay Mansour and Elad Verbin. 2008. On agnostic boosting and parity learning. In STOC. 629\u2013638. Adam Tauman Kalai Yishay Mansour and Elad Verbin. 2008. On agnostic boosting and parity learning. In STOC. 629\u2013638."},{"key":"e_1_2_1_38_1","volume-title":"Vazirani","author":"Kearns Michael J.","year":"1994","unstructured":"Michael J. Kearns and Umesh V . Vazirani . 1994 . An Introduction to Computational Learning Theory. MIT Press . Michael J. Kearns and Umesh V. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01747074"},{"key":"e_1_2_1_40_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0212-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(61)90702-5"},{"key":"e_1_2_1_43_1","first-page":"765","article-title":"On a Boolean function","volume":"169","author":"Nechiporuk E. I.","year":"1966","unstructured":"E. I. Nechiporuk . 1966 . On a Boolean function . Doklady Akademii Nauk SSSR 169 , 4 (1966), 765 \u2013 766 . English translation in Soviet Mathematics Doklady. E. I. Nechiporuk. 1966. On a Boolean function. Doklady Akademii Nauk SSSR 169, 4 (1966), 765\u2013766. English translation in Soviet Mathematics Doklady.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of \u201cCombinatorics, Paul Erdos is Eighty\u201d. 301\u2013315","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan . 1994 . The communication complexity of threshold gates . In Proceedings of \u201cCombinatorics, Paul Erdos is Eighty\u201d. 301\u2013315 . Noam Nisan. 1994. The communication complexity of threshold gates. In Proceedings of \u201cCombinatorics, Paul Erdos is Eighty\u201d. 301\u2013315."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell Rocco A. Servedio and Li-Yang Tan. 2019. Fooling polytopes. In STOC. 614\u2013625. Ryan O'Donnell Rocco A. Servedio and Li-Yang Tan. 2019. Fooling polytopes. In STOC. 614\u2013625.","DOI":"10.1145\/3313276.3316321"},{"key":"e_1_2_1_46_1","first-page":"1","article-title":"Hardness magnification near state-of-the-art lower bounds","volume":"27","author":"Oliveira Igor Carboni","year":"2019","unstructured":"Igor Carboni Oliveira , J\u00e1n Pich , and Rahul Santhanam . 2019 . Hardness magnification near state-of-the-art lower bounds . In CCC. 27 : 1 \u2013 27 :29. Igor Carboni Oliveira, J\u00e1n Pich, and Rahul Santhanam. 2019. Hardness magnification near state-of-the-art lower bounds. In CCC. 27:1\u201327:29.","journal-title":"CCC."},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness","volume":"18","author":"Oliveira Igor Carboni","year":"2017","unstructured":"Igor Carboni Oliveira and Rahul Santhanam . 2017 . Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness . In CCC. 18 : 1 \u2013 18 :49. Igor Carboni Oliveira and Rahul Santhanam. 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In CCC. 18:1\u201318:49.","journal-title":"CCC."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Mihai Patrascu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In SODA. 1065\u20131075. Mihai Patrascu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In SODA. 1065\u20131075.","DOI":"10.1137\/1.9781611973075.86"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/47979.47982"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Ben Reichardt. 2009. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In FOCS. 544\u2013551. Ben Reichardt. 2009. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In FOCS. 544\u2013551.","DOI":"10.1109\/FOCS.2009.55"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Ben Reichardt. 2011. Faster quantum algorithm for evaluating game trees. In SODA. 546\u2013559. Ben Reichardt. 2011. Faster quantum algorithm for evaluating game trees. In SODA. 546\u2013559.","DOI":"10.1137\/1.9781611973082.43"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Ben Reichardt. 2011. Reflections for quantum query algorithms. In SODA. 560\u2013569. Ben Reichardt. 2011. Reflections for quantum query algorithms. In SODA. 560\u2013569.","DOI":"10.1137\/1.9781611973082.44"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a013"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1515\/dma-2017-0003"},{"key":"e_1_2_1_56_1","first-page":"1","article-title":"What circuit classes can be learned with non-trivial savings?","volume":"30","author":"Servedio Rocco A.","year":"2017","unstructured":"Rocco A. Servedio and Li-Yang Tan . 2017 . What circuit classes can be learned with non-trivial savings? . In ITCS. 30 : 1 \u2013 30 :21. Rocco A. Servedio and Li-Yang Tan. 2017. What circuit classes can be learned with non-trivial savings?. In ITCS. 30:1\u201330:21.","journal-title":"ITCS."},{"key":"e_1_2_1_57_1","first-page":"1","article-title":"Improved pseudorandom generators from pseudorandom multi-switching lemmas","volume":"45","author":"Servedio Rocco A.","year":"2019","unstructured":"Rocco A. Servedio and Li-Yang Tan . 2019 . Improved pseudorandom generators from pseudorandom multi-switching lemmas . In APPROX\/RANDOM. 45 : 1 \u2013 45 :23. Rocco A. Servedio and Li-Yang Tan. 2019. Improved pseudorandom generators from pseudorandom multi-switching lemmas. In APPROX\/RANDOM. 45:1\u201345:23.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_58_1","volume-title":"Doklady Akademii Nauk","volume":"136","author":"Subbotovskaya Bella Abramovna","year":"1961","unstructured":"Bella Abramovna Subbotovskaya . 1961 . Realization of linear functions by formulas using , &, \u2013 . In Doklady Akademii Nauk , Vol. 136 . Russian Academy of Sciences, 553\u2013555. Bella Abramovna Subbotovskaya. 1961. Realization of linear functions by formulas using , &, \u2013. In Doklady Akademii Nauk, Vol. 136. Russian Academy of Sciences, 553\u2013555."},{"key":"e_1_2_1_59_1","unstructured":"Avishay Tal. 2014. Shrinkage of De Morgan formulae by spectral techniques. In FOCS. 551\u2013560. Avishay Tal. 2014. Shrinkage of De Morgan formulae by spectral techniques. In FOCS. 551\u2013560."},{"key":"e_1_2_1_60_1","first-page":"114","article-title":"#SAT algorithms from shrinkage","volume":"22","author":"Tal Avishay","year":"2015","unstructured":"Avishay Tal . 2015 . #SAT algorithms from shrinkage . Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 114 . Avishay Tal. 2015. #SAT algorithms from shrinkage. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 114.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_61_1","first-page":"181","article-title":"The bipartite formula complexity of inner-product is quadratic","volume":"23","author":"Tal Avishay","year":"2016","unstructured":"Avishay Tal . 2016 . The bipartite formula complexity of inner-product is quadratic . Electronic Colloquium on Computational Complexity (ECCC) 23 (2016), 181 . Avishay Tal. 2016. The bipartite formula complexity of inner-product is quadratic. Electronic Colloquium on Computational Complexity (ECCC) 23 (2016), 181.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Avishay Tal. 2017. Formula lower bounds via the quantum method. In STOC. 1256\u20131268. Avishay Tal. 2017. Formula lower bounds via the quantum method. In STOC. 1256\u20131268.","DOI":"10.1145\/3055399.3055472"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant. 1984. A theory of the learnable. In STOC. 436\u2013445. Leslie G. Valiant. 1984. A theory of the learnable. In STOC. 436\u2013445.","DOI":"10.1145\/800057.808710"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3078-3"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_2_1_67_1","first-page":"1","article-title":"Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation","volume":"2","author":"Williams Ryan","year":"2016","unstructured":"Ryan Williams . 2016 . Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation . In CCC. 2 : 1 \u2013 2 :17. Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In CCC. 2:1\u20132:17.","journal-title":"CCC."},{"key":"e_1_2_1_68_1","unstructured":"Andrew Chi-Chih Yao. 1982. Theory and applications of trapdoor functions. In FOCS. 80\u201391. Andrew Chi-Chih Yao. 1982. Theory and applications of trapdoor functions. In FOCS. 80\u201391."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470861","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":68,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470861"],"URL":"https:\/\/doi.org\/10.1145\/3470861","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}