Weights of Exact Threshold Functions

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • László Babai, The University of Chicago, United States
  • Kristoffer Arnsfelt Hansen
  • Vladimir V. Podolskii, Steklov Mathematical Institute, Russian Federation
  • Xiaoming Sun, ITCS, Tsingshua University, China
  • Department of Computer Science
We consider Boolean exact threshold functions defined by linear equations, and in general degree d polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients required to represent such functions. These bounds are very close and in the linear case in particular they are almost matching. The quantity is the same as the maximum magnitude of integer coefficients of linear equations required to express every possible intersection of a hyperplane in R n and the Boolean cube {0,1} n , or in the general case intersections of hypersurfaces of degree d in R n and the Boolean cube {0,1} n . In the process we construct new families of ill-conditioned matrices. We further stratify the problem (in the linear case) in terms of the dimension k of the affine subspace spanned by the solutions, and give upper and lower bounds in this case as well. Our bounds here in terms of k leave a substantial gap, a challenge for future work.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)66-77
Publication statusPublished - 2010
EventInternational Symposium on Mathematical Foundations of Computer Science. MFCS 2010 - Brno, Czech Republic
Duration: 23 Aug 201027 Aug 2010
Conference number: 35


ConferenceInternational Symposium on Mathematical Foundations of Computer Science. MFCS 2010
CountryCzech Republic

Bibliographical note

Title of the vol.: Mathematical Foundations of Computer Science 2010. Proceedings. / Petr Hlinený and Antonín Kucera (eds.)
ISBN: 978-3-642-15154-5

See relations at Aarhus University Citationformats

ID: 22391799