{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:39:40Z","timestamp":1758267580351,"version":"3.40.5"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"TCS Fellowship"},{"DOI":"10.13039\/501100001409","name":"Department of Science and Technology, Ministry of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001409","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1137\/19m1271348","type":"journal-article","created":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T16:42:58Z","timestamp":1655224978000},"page":"820-848","source":"Crossref","is-referenced-by-count":1,"title":["A Short List of Equalities Induces Large Sign-Rank"],"prefix":"10.1137","volume":"51","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9520-7340","authenticated-orcid":true,"given":"Nikhil S.","family":"Mande","sequence":"additional","affiliation":[]}],"member":"351","published-online":{"date-parts":[[2022,6,14]]},"reference":[{"volume-title":"CoRR, abs\/1704.03176","year":"2017","author":"Ada A.","key":"atypb1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055484"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.30"},{"key":"atypb4","first-page":"47","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT","author":"Alon N.","year":"2016"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_11"},{"key":"atypb6","first-page":"337","volume-title":"Proceedings of the 27th Annual Symposium on Foundations of Computer Science, FOCS","author":"Babai L.","year":"1986"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263422"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/12.755000"},{"key":"atypb9","first-page":"S17","volume":"49","author":"Bouland A.","year":"2019","journal-title":"SIAM J. Comput."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0403015"},{"key":"atypb11","first-page":"24","volume-title":"Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, CCC '07, IEEE Computer Society","author":"Buhrman H.","year":"2007"},{"key":"atypb12","first-page":"1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP","author":"Bun M.","year":"2016"},{"key":"atypb13","first-page":"S17","volume":"49","author":"Bun M.","year":"2019","journal-title":"SIAM J. Comput."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a007"},{"key":"atypb15","first-page":"24","volume-title":"Electron. Colloq. Comput. Complexity (ECCC)","author":"Chattopadhyay A.","year":"2017"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00014"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/3396695"},{"volume-title":"CoRR, abs\/1805.10698","year":"2018","author":"Chen L.","key":"atypb18"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a009"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055425"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01111276"},{"key":"atypb23","first-page":"100","volume-title":"Proceedings of the 16th Annual IEEE Conference on Computational Complexity, CCC","author":"Forster J.","year":"2001"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45294-X_15"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200426"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794274519"},{"volume-title":"private communication","year":"2017","author":"G\u00f6\u00f6s M.","key":"atypb27"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0175-5"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0166-6"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.33"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.008"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395118"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136869"},{"volume-title":"CoRR, abs\/1704.00777","year":"2017","author":"Hatami H.","key":"atypb35"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61332-3_146"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.32"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897636"},{"key":"atypb39","first-page":"1","volume-title":"Proceedings of the 33rd Computational Complexity Conference, CCC","author":"Kannan S.","year":"2018"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214415"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"atypb42","first-page":"587","volume":"7","author":"Klivans A. R.","year":"2006","journal-title":"J. Mach. Learning Res."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0203-0"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050015"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3"},{"volume-title":"Perceptrons---An Introduction to Computational Geometry","year":"1987","author":"Minsky M.","key":"atypb46"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"volume-title":"CoRR, abs\/0909.3392","year":"2009","author":"Montanaro A.","key":"atypb48"},{"volume-title":"Threshold Logic and Its Applications","year":"1971","author":"Muroga S.","key":"atypb49"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90046-2"},{"volume-title":"private communication","year":"2013","author":"Pudl\u00e1k P.","key":"atypb52"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55706-7_4"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/BF00058680"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/0703024"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.81"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2580-0"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"atypb61","series-title":"SIAM J. Comput.","volume-title":"Near-Optimal Lower Bounds on the Threshold Degree and Sign-rank of \\(AC^0\\)","author":"Sherstov A. A.","year":"2021"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1137\/0404038"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188822"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.136"},{"key":"atypb65","first-page":"255","volume":"9","author":"Zhang Z.","year":"2009","journal-title":"Quantum Inf. Comput."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T20:46:33Z","timestamp":1709066793000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1271348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/19M1271348"],"URL":"https:\/\/doi.org\/10.1137\/19m1271348","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"type":"print","value":"0097-5397"},{"type":"electronic","value":"1095-7111"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}