{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:02Z","timestamp":1750220702911,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384328","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1349-1362","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A robust version of Hegedus\u2019s lemma, with applications"],"prefix":"10.1145","author":[{"given":"Srikanth","family":"Srinivasan","sequence":"first","affiliation":[{"name":"IIT Bombay, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.17"},{"key":"e_1_3_2_1_2_1","first-page":"87","article-title":"Coin Theorems and the Fourier Expansion","volume":"26","author":"Agrawal Rohit","year":"2019","unstructured":"Rohit Agrawal . 2019 . Coin Theorems and the Fourier Expansion . Electronic Colloquium on Computational Complexity (ECCC) , 26 (2019), 87 . https:\/\/eccc.weizmann.ac.il\/report\/2019\/087 Rohit Agrawal. 2019. Coin Theorems and the Fourier Expansion. Electronic Colloquium on Computational Complexity (ECCC), 26 (2019), 87. https:\/\/eccc.weizmann.ac.il\/report\/2019\/087","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai and Michael Ben-Or. 1984. A Theorem on Probabilistic Constant Depth Computations. In STOC. 471\u2013474.  Mikl\u00f3s Ajtai and Michael Ben-Or. 1984. A Theorem on Probabilistic Constant Depth Computations. In STOC. 471\u2013474.","DOI":"10.1145\/800057.808715"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.18"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.11"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_1_7_1","unstructured":"Richard Beigel. 1993. The polynomial method in circuit complexity. [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference 82\u201395.  Richard Beigel. 1993. The polynomial method in circuit complexity. [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference 82\u201395."},{"key":"e_1_3_2_1_8_1","first-page":"178","article-title":"Combinatorics on words: a tutorial","volume":"79","author":"Berstel Jean","year":"2003","unstructured":"Jean Berstel and Juhani Karhum\u00e4ki . 2003 . Combinatorics on words: a tutorial . Bulletin of the EATCS , 79 (2003), 178 . Jean Berstel and Juhani Karhum\u00e4ki. 2003. Combinatorics on words: a tutorial. Bulletin of the EATCS, 79 (2003), 178.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2018.5"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"volume-title":"The Coin Problem and Pseudorandomness for Branching Programs","author":"Brody Joshua","key":"e_1_3_2_1_11_1","unstructured":"Joshua Brody and Elad Verbin . 2010. The Coin Problem and Pseudorandomness for Branching Programs . In FOCS. IEEE Computer Society , 30\u201339. Joshua Brody and Elad Verbin. 2010. The Coin Problem and Pseudorandomness for Branching Programs. In FOCS. IEEE Computer Society, 30\u201339."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.22"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80016-5"},{"key":"e_1_3_2_1_14_1","volume-title":"APPROX-RANDOM (LIPIcs","volume":"629","author":"Cohen Gil","year":"2014","unstructured":"Gil Cohen , Anat Ganor , and Ran Raz . 2014 . Two Sides of the Coin Problem . In APPROX-RANDOM (LIPIcs , Vol. 28). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 618\u2013 629 . Gil Cohen, Anat Ganor, and Ran Raz. 2014. Two Sides of the Coin Problem. In APPROX-RANDOM (LIPIcs, Vol. 28). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 618\u2013629."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.7"},{"volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"Dubhashi Devdatt P","key":"e_1_3_2_1_16_1","unstructured":"Devdatt P Dubhashi and Alessandro Panconesi . 2009. Concentration of measure for the analysis of randomized algorithms . Cambridge University Press . Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.1.8"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788526"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.66"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Larry Guth. 2016. Polynomial methods in combinatorics. 64 American Mathematical Soc..  Larry Guth. 2016. Polynomial methods in combinatorics. 64 American Mathematical Soc..","DOI":"10.1090\/ulect\/064"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.32"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1556\/sscmath.2009.1134"},{"key":"e_1_3_2_1_23_1","first-page":"26","article-title":"Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits","volume":"26","author":"Hrubes Pavel","year":"2019","unstructured":"Pavel Hrubes , Sivaramakrishnan Natarajan Ramamoorthy , Anup Rao , and Amir Yehudayoff . 2019 . Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits . Electronic Colloquium on Computational Complexity (ECCC) , 26 (2019), 26 . https:\/\/eccc.weizmann.ac.il\/report\/2019\/026 Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, and Amir Yehudayoff. 2019. Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. Electronic Colloquium on Computational Complexity (ECCC), 26 (2019), 26. https:\/\/eccc.weizmann.ac.il\/report\/2019\/026","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434634"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a012"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2017.49"},{"key":"e_1_3_2_1_29_1","first-page":"157","article-title":"The Coin Problem in Constant Depth: Sample Complexity and Parity gates","volume":"25","author":"Limaye Nutan","year":"2018","unstructured":"Nutan Limaye , Karteek Sreenivasaiah , Srikanth Srinivasan , Utkarsh Tripathi , and S. Venkitesh . 2018 . The Coin Problem in Constant Depth: Sample Complexity and Parity gates . Electronic Colloquium on Computational Complexity (ECCC) , 25 (2018), 157 . https:\/\/eccc.weizmann.ac.il\/report\/2018\/157 Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. 2018. The Coin Problem in Constant Depth: Sample Complexity and Parity gates. Electronic Colloquium on Computational Complexity (ECCC), 25 (2018), 157. https:\/\/eccc.weizmann.ac.il\/report\/2018\/157","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00145-6"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a011"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2015.03.011"},{"key":"e_1_3_2_1_34_1","first-page":"96","article-title":"On the AC^0+ complexity of Andreev\u2019s Problem","volume":"26","author":"Potukuchi Aditya","year":"2019","unstructured":"Aditya Potukuchi . 2019 . On the AC^0+ complexity of Andreev\u2019s Problem . Electronic Colloquium on Computational Complexity (ECCC) , 26 (2019), 96 . https:\/\/eccc.weizmann.ac.il\/report\/2019\/096 Aditya Potukuchi. 2019. On the AC^0+ complexity of Andreev\u2019s Problem. Electronic Colloquium on Computational Complexity (ECCC), 26 (2019), 96. https:\/\/eccc.weizmann.ac.il\/report\/2019\/096","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366874"},{"key":"e_1_3_2_1_42_1","first-page":"138","article-title":"On the Probabilistic Degrees of Symmetric Boolean functions","volume":"26","author":"Srinivasan Srikanth","year":"2019","unstructured":"Srikanth Srinivasan , Utkarsh Tripathi , and S. Venkitesh . 2019 . On the Probabilistic Degrees of Symmetric Boolean functions . Electronic Colloquium on Computational Complexity (ECCC) , 26 (2019), 138 . https:\/\/eccc.weizmann.ac.il\/report\/2019\/138 Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. 2019. On the Probabilistic Degrees of Symmetric Boolean functions. Electronic Colloquium on Computational Complexity (ECCC), 26 (2019), 138. https:\/\/eccc.weizmann.ac.il\/report\/2019\/138","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90016-6"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0267-3"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.133259"},{"key":"e_1_3_2_1_47_1","volume-title":"New algorithms and lower bounds for circuits with linear threshold gates. CoRR, abs\/1401.2444","author":"Williams Ryan","year":"2014","unstructured":"Ryan Williams . 2014. New algorithms and lower bounds for circuits with linear threshold gates. CoRR, abs\/1401.2444 ( 2014 ), arxiv:1401.2444 Ryan Williams. 2014. New algorithms and lower bounds for circuits with linear threshold gates. CoRR, abs\/1401.2444 (2014), arxiv:1401.2444"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_1_49_1","volume-title":"34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS","author":"Williams Richard Ryan","year":"2014","unstructured":"Richard Ryan Williams . 2014 . The polynomial method in circuit complexity applied to algorithm design (invited talk) . In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Richard Ryan Williams. 2014. The polynomial method in circuit complexity applied to algorithm design (invited talk). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024524"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":49,"alternative-id":["10.1145\/3357713.3384328","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384328","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}