{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:36Z","timestamp":1781077836679,"version":"3.54.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T00:00:00Z","timestamp":1396310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CNS-0716245, CCF-0915929, and CCF-1115703"],"award-info":[{"award-number":["CNS-0716245, CCF-0915929, and CCF-1115703"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0716245, CCF-0915929, and CCF-1115703"],"award-info":[{"award-number":["CNS-0716245, CCF-0915929, and CCF-1115703"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,4]]},"abstract":"<jats:p>\n            The\n            <jats:italic>Chow parameters<\/jats:italic>\n            of a Boolean function\n            <jats:italic>f<\/jats:italic>\n            :{\u22121, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {\u22121, 1} are its\n            <jats:italic>n<\/jats:italic>\n            +1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Chow 1961; Tannenbaum 1961] that the (exact values of the) Chow parameters of any linear threshold function\n            <jats:italic>f<\/jats:italic>\n            uniquely specify\n            <jats:italic>f<\/jats:italic>\n            within the space of all Boolean functions, but until recently [O'Donnell and Servedio 2011] nothing was known about efficient algorithms for\n            <jats:italic>reconstructing<\/jats:italic>\n            <jats:italic>f<\/jats:italic>\n            (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the\n            <jats:italic>Chow Parameters Problem.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function\n            <jats:italic>f<\/jats:italic>\n            , runs in time \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) \u22c5 (1\/\u03f5)\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (log\n              <jats:sup>2<\/jats:sup>\n              (1\/\u03f5))\n            <\/jats:sup>\n            and with high probability outputs a representation of an LTF\n            <jats:italic>f<\/jats:italic>\n            \u2032 that is \u03f5-close to\n            <jats:italic>f<\/jats:italic>\n            in Hamming distance. The only previous algorithm [O'Donnell and Servedio 2011] had running time poly(\n            <jats:italic>n<\/jats:italic>\n            ) \u22c5 2\n            <jats:sup>\n              2\n              <jats:sup>\n                \u00d5(1\/\u03f5\n                <jats:sup>2<\/jats:sup>\n                )\n              <\/jats:sup>\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            As a byproduct of our approach, we show that for any linear threshold function\n            <jats:italic>f<\/jats:italic>\n            over {-1, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            , there is a linear threshold function\n            <jats:italic>f<\/jats:italic>\n            \u2032 which is \u03f5-close to\n            <jats:italic>f<\/jats:italic>\n            and has all weights that are integers of magnitude at most \u221an \u22c5 (1\/\u03f5)\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (log\n              <jats:sup>2<\/jats:sup>\n              (1\/\u03f5))\n            <\/jats:sup>\n            . This significantly improves the previous best result of Diakonikolas and Servedio [2009] which gave a poly(\n            <jats:italic>n<\/jats:italic>\n            ) \u22c5 2\n            <jats:sup>\n              \u00d5(1\/\u03f5\n              <jats:sup>2\/3<\/jats:sup>\n              )\n            <\/jats:sup>\n            weight bound, and is close to the known lower bound of max{\u221an, (1\/\u03f5)\n            <jats:sup>\u03a9(log log (1\/\u03f5))<\/jats:sup>\n            } [Goldberg 2006; Servedio 2007]. Our techniques also yield improved algorithms for related problems in learning theory.\n          <\/jats:p>\n          <jats:p>\n            In addition to being significantly stronger than previous work, our results are obtained using conceptually simpler proofs. The two main ingredients underlying our results are (1) a new structural result showing that for\n            <jats:italic>f<\/jats:italic>\n            any linear threshold function and\n            <jats:italic>g<\/jats:italic>\n            any bounded function, if the Chow parameters of\n            <jats:italic>f<\/jats:italic>\n            are close to the Chow parameters of\n            <jats:italic>g<\/jats:italic>\n            then\n            <jats:italic>f<\/jats:italic>\n            is close to\n            <jats:italic>g<\/jats:italic>\n            ; (2) a new boosting-like algorithm that given approximations to the Chow parameters of a linear threshold function outputs a bounded function whose Chow parameters are close to those of\n            <jats:italic>f<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2590772","type":"journal-article","created":{"date-parts":[[2014,4,22]],"date-time":"2014-04-22T13:37:45Z","timestamp":1398173865000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces"],"prefix":"10.1145","volume":"61","author":[{"given":"Anindya","family":"De","sequence":"first","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilias","family":"Diakonikolas","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vitaly","family":"Feldman","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,4,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Multitopic Conference. 1--6.","author":"Aziz H.","unstructured":"H. Aziz , M. Paterson , and D. Leech . 2007. Efficient algorithm for designing weighted voting games . In Proceedings of the IEEE International Multitopic Conference. 1--6. H. Aziz, M. Paterson, and D. Leech. 2007. Efficient algorithm for designing weighted voting games. In Proceedings of the IEEE International Multitopic Conference. 1--6."},{"key":"e_1_2_1_2_1","first-page":"317","article-title":"Weighted voting doesn't work: A mathematical analysis","volume":"19","author":"Banzhaf J.","year":"1965","unstructured":"J. Banzhaf . 1965 . Weighted voting doesn't work: A mathematical analysis . Rutgers Law Rev. 19 , 317 -- 343 . J. Banzhaf. 1965. Weighted voting doesn't work: A mathematical analysis. Rutgers Law Rev. 19, 317--343.","journal-title":"Rutgers Law Rev."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1569"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007458528570"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403015"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860400344"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'10)","author":"Cheraghchi M.","unstructured":"M. Cheraghchi , J. H\u00e5stad , M. Isaksson , and O. Svensson . 2010. Approximating linear threshold predicates . In Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'10) . 110--123. M. Cheraghchi, J. H\u00e5stad, M. Isaksson, and O. Svensson. 2010. Approximating linear threshold predicates. In Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'10). 110--123."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1961.24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_23"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. (AAMAS'10)","volume":"1","author":"de Keijzer B.","unstructured":"B. de Keijzer , T. Klos , and Y. Zhang . 2010. Enumeration and exact design of weighted voting games . In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. (AAMAS'10) . Vol. 1 , 391--398. B. de Keijzer, T. Klos, and Y. Zhang. 2010. Enumeration and exact design of weighted voting games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. (AAMAS'10). Vol. 1, 391--398."},{"key":"e_1_2_1_12_1","volume-title":"Threshold Logic: A Synthesis Approach","author":"Dertouzos M.","year":"1965","unstructured":"M. Dertouzos . 1965 . Threshold Logic: A Synthesis Approach . MIT Press , Cambridge, MA . M. Dertouzos. 1965. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00092-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01268159"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1961.39"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Conference on Innovations in Computer Science. 241--250","author":"Feldman V.","year":"2010","unstructured":"V. Feldman . 2010 . Distribution-specific agnostic boosting . In Proceedings of the Conference on Innovations in Computer Science. 241--250 . V. Feldman. 2010. Distribution-specific agnostic boosting. In Proceedings of the Conference on Innovations in Computer Science. 241--250."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of Conference on Learning Theory. 17","author":"Feldman V.","year":"2012","unstructured":"V. Feldman . 2012 . Learning DNF expressions from Fourier spectrum . In Proceedings of Conference on Learning Theory. 17 .1--17.19. V. Feldman. 2012. Learning DNF expressions from Fourier spectrum. In Proceedings of Conference on Learning Theory. 17.1--17.19."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748055"},{"key":"e_1_2_1_21_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","unstructured":"W. Feller . 1968. An Introduction to Probability Theory and Its Applications . Wiley . W. Feller. 1968. An Introduction to Probability Theory and Its Applications. Wiley."},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"A priori voting power: What is it all about&quest; Polit","volume":"2","author":"Felsenthal D.","year":"2004","unstructured":"D. Felsenthal and M. Machover . 2004 . A priori voting power: What is it all about&quest; Polit . Stud. Rev. 2 , 1, 1 -- 23 . D. Felsenthal and M. Machover. 2004. A priori voting power: What is it all about&quest; Polit. Stud. Rev. 2, 1, 1--23.","journal-title":"Stud. Rev."},{"key":"e_1_2_1_23_1","first-page":"201","article-title":"Different ways to represent weighted majority games","volume":"5","author":"Freixas J.","year":"1997","unstructured":"J. Freixas . 1997 . Different ways to represent weighted majority games . J. Span. Soc. Stat. Oper. Res. 5 , 2, 201 -- 212 . J. Freixas. 1997. Different ways to represent weighted majority games. J. Span. Soc. Stat. Oper. Res. 5, 2, 201--212.","journal-title":"J. Span. Soc. Stat. Oper. Res."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103426765"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018403"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192235878"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/16.2.165"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796290"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.13"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1965.264254"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)80014-5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2011.587008"},{"key":"e_1_2_1_34_1","unstructured":"S. Kurz and S. Napel. 2012. Heuristic and exact solutions to the inverse power index problem for small voting bodies. arxiv report http:\/\/arxiv.org\/abs\/1202.6245.  S. Kurz and S. Napel. 2012. Heuristic and exact solutions to the inverse power index problem for small voting bodies. arxiv report http:\/\/arxiv.org\/abs\/1202.6245."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1972-0287916-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"A. Laruelle and M. Widgren. 1998. Is the allocation of voting power among EU states fair&quest; Public Choice 94 317--339.  A. Laruelle and M. Widgren. 1998. Is the allocation of voting power among EU states fair&quest; Public Choice 94 317--339.","DOI":"10.1023\/A:1004965310450"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020877015060"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016324824094"},{"key":"e_1_2_1_39_1","unstructured":"D. Leech. 2003. Power indices as an aid to institutional design: The generalised apportionment problem. In Yearbook on New Political Economy M. Holler H. Kliemt D. Schmidtchen and M. Streit (Eds.).  D. Leech. 2003. Power indices as an aid to institutional design: The generalised apportionment problem. In Yearbook on New Political Economy M. Holler H. Kliemt D. Schmidtchen and M. Streit (Eds.)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707890"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-62-99195-0"},{"key":"e_1_2_1_42_1","volume-title":"Tech. Rep. 245. Univ. Illinois","author":"Muroga S.","year":"1967","unstructured":"S. Muroga , T. Tsuboi , and C. R. Baugh . 1967 . Enumeration of threshold functions of eight variables. Tech. Rep. 245. Univ. Illinois , Urbana . S. Muroga, T. Tsuboi, and C. R. Baugh. 1967. Enumeration of threshold functions of eight variables. Tech. Rep. 245. Univ. Illinois, Urbana."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(88)90046-5"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756466"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/2981392"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1095"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0228-7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"I. S. Shiganov. 1986. Refinement of the upper bound of the constant in the central limit theorem. J. Sov. Math. 2545--2550.  I. S. Shiganov. 1986. Refinement of the upper bound of the constant in the central limit theorem. J. Sov. Math. 2545--2550.","DOI":"10.1007\/BF01121471"},{"key":"e_1_2_1_49_1","volume-title":"Tech. Rep. 653. The Institute of Social and Economic Research","author":"Takamiya K.","year":"2006","unstructured":"K. Takamiya and A. Tanaka . 2006 . Computational complexity in the design of voting games. Tech. Rep. 653. The Institute of Social and Economic Research , Osaka University . K. Takamiya and A. Tanaka. 2006. Computational complexity in the design of voting games. Tech. Rep. 653. The Institute of Social and Economic Research, Osaka University."},{"key":"e_1_2_1_50_1","first-page":"1","article-title":"The establishment of a unique representation for a linearly separable function","volume":"20","author":"Tannenbaum M.","year":"1961","unstructured":"M. Tannenbaum . 1961 . The establishment of a unique representation for a linearly separable function . Tech. Rep. Lockheed Missiles and Space Co. Threshold Switching Techniques Note 20 , 1 -- 5 . M. Tannenbaum. 1961. The establishment of a unique representation for a linearly separable function. Tech. Rep. Lockheed Missiles and Space Co. Threshold Switching Techniques Note 20, 1--5.","journal-title":"Tech. Rep. Lockheed Missiles and Space Co. Threshold Switching Techniques Note"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.169.595"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1992-1092927-0"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_2_1_54_1","volume-title":"Artificial Intelligence","author":"Winder R. O.","unstructured":"R. O. Winder . 1963. Threshold logic in artificial intelligence . In Artificial Intelligence , IEEE Publication S- 142, 107--128. R. O. Winder. 1963. Threshold logic in artificial intelligence. In Artificial Intelligence, IEEE Publication S-142, 107--128."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222665"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/321637.321647"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2590772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2590772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:24Z","timestamp":1750234224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2590772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1145\/2590772"],"URL":"https:\/\/doi.org\/10.1145\/2590772","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}