{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:17Z","timestamp":1787340437560,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form $f(x)=\\mathrm{sgn}(w\\cdot x-\\theta)$. We consider halfspaces over the continuous domain $\\mathbf{R}^n$ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube $\\{-1,1\\}^n$ (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are $\\epsilon$-far from any halfspace using only $\\mathrm{poly}(\\frac{1}{\\epsilon})$ queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube $\\{-1,1\\}^n$ (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over $\\{-1,1\\}^n$ poses significant additional complications and requires other ingredients. These include \u201ccross-consistency\u201d versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103\u2013112].<\/jats:p>","DOI":"10.1137\/070707890","type":"journal-article","created":{"date-parts":[[2010,2,24]],"date-time":"2010-02-24T18:06:15Z","timestamp":1267034775000},"page":"2004-2047","source":"Crossref","is-referenced-by-count":27,"title":["Testing Halfspaces"],"prefix":"10.1137","volume":"39","author":[{"given":"Kevin","family":"Matulef","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"O'Donnell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron,\n                      Testing low-degree polynomials over GF$(2)$\n                      , in Proceedings of RANDOM, 2003, pp. 188\u2013199.","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"R2","unstructured":"R. Bhattacharya and R. Rao,\n                      Normal Approximation and Asymptotic Expansions\n                      , Robert E. Krieger, Malabar, FL, 1986."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007458528570"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.34.123"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. Chow,\n                      On the characterization of threshold functions\n                      , in Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34\u201338.","DOI":"10.1109\/FOCS.1961.24"},{"key":"R7","unstructured":"V. Chv\u00e1tal,\n                      Linear Programming\n                      , W. H. Freeman, San Francisco, 1983."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan,\n                      Testing for concise representations\n                      , in Proceedings of the 48th Annual Symposium on Computer Science (FOCS), 2007, pp. 549\u2013558.","DOI":"10.1109\/FOCS.2007.32"},{"key":"R9","unstructured":"W. Feller,\n                      An Introduction to Probability Theory and its Applications\n                      , John Wiley & Sons, New York, 1968."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Fiat and D. Pechyony,\n                      Decision trees: More theoretical justification for practical algorithms\n                      , in Algorithmic Learning Theory, 15th International Conference (ALT 2004), 2004, pp. 156\u2013170.","DOI":"10.1007\/978-3-540-30215-5_13"},{"key":"R11","unstructured":"E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky,\n                      Testing juntas\n                      , in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103\u2013112."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samrodnitsky,\n                      Monotonicity testing over general poset domains\n                      , in Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, 2002, pp. 474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103426765"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022627018023"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Ledoux and M. Talagrand,\n                      Probability in Banach Spaces\n                      , Springer, New York, 1991.","DOI":"10.1007\/978-3-642-20212-4"},{"key":"R20","unstructured":"M. Minsky and S. Papert,\n                      Perceptrons: An Introduction to Computational Geometry\n                      , MIT Press, Cambridge, MA, 1968."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(61)90702-5"},{"key":"R22","unstructured":"A. Novikoff,\n                      On convergence proofs on perceptrons\n                      , in Proceedings of the Symposium on Mathematical Theory of Automata, vol. XII, 1962, pp. 615\u2013622."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101407444"},{"key":"R24","unstructured":"V. V. Petrov,\n                      Limit Theorems of Probability Theory\n                      , Oxford Science Publications, Oxford, England, 1995."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0228-7"},{"key":"R26","unstructured":"J. Shawe-Taylor and N. Cristianini,\n                      An Introduction to Support Vector Machines\n                      , Cambridge University Press, London, 2000."},{"key":"R27","unstructured":"D. \u0160tefankovi\u010d,\n                      Fourier transform in computer science\n                      , Master's thesis, University of Chicago, Chicago, 2000."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844850"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. Yao,\n                      On ACC and threshold circuits\n                      , in Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Science, 1990, pp. 619\u2013627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070707890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:59Z","timestamp":1787337299000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070707890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070707890"],"URL":"https:\/\/doi.org\/10.1137\/070707890","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}