Aarhus University Seal / Aarhus Universitets segl

Weights of Exact Threshold Functions

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

Standard

Weights of Exact Threshold Functions. / Babai, László; Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.; Sun, Xiaoming.

In: Lecture Notes in Computer Science, Vol. 6281, 2010, p. 66-77.

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

Harvard

Babai, L, Hansen, KA, Podolskii, VV & Sun, X 2010, 'Weights of Exact Threshold Functions', Lecture Notes in Computer Science, vol. 6281, pp. 66-77. https://doi.org/10.1007/978-3-642-15155-2_8

APA

Babai, L., Hansen, K. A., Podolskii, V. V., & Sun, X. (2010). Weights of Exact Threshold Functions. Lecture Notes in Computer Science, 6281, 66-77. https://doi.org/10.1007/978-3-642-15155-2_8

CBE

Babai L, Hansen KA, Podolskii VV, Sun X. 2010. Weights of Exact Threshold Functions. Lecture Notes in Computer Science. 6281:66-77. https://doi.org/10.1007/978-3-642-15155-2_8

MLA

Babai, László et al. "Weights of Exact Threshold Functions". Lecture Notes in Computer Science. 2010, 6281. 66-77. https://doi.org/10.1007/978-3-642-15155-2_8

Vancouver

Babai L, Hansen KA, Podolskii VV, Sun X. Weights of Exact Threshold Functions. Lecture Notes in Computer Science. 2010;6281:66-77. https://doi.org/10.1007/978-3-642-15155-2_8

Author

Babai, László ; Hansen, Kristoffer Arnsfelt ; Podolskii, Vladimir V. ; Sun, Xiaoming. / Weights of Exact Threshold Functions. In: Lecture Notes in Computer Science. 2010 ; Vol. 6281. pp. 66-77.

Bibtex

@inproceedings{353db390e68111dfa891000ea68e967b,
title = "Weights of Exact Threshold Functions",
abstract = "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.",
author = "L{\'a}szl{\'o} Babai and Hansen, {Kristoffer Arnsfelt} and Podolskii, {Vladimir V.} and Xiaoming Sun",
note = "Title of the vol.: Mathematical Foundations of Computer Science 2010. Proceedings. / Petr Hlinen{\'y} and Anton{\'i}n Kucera (eds.) ISBN: 978-3-642-15154-5 ; null ; Conference date: 23-08-2010 Through 27-08-2010",
year = "2010",
doi = "10.1007/978-3-642-15155-2_8",
language = "English",
volume = "6281",
pages = "66--77",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

RIS

TY - GEN

T1 - Weights of Exact Threshold Functions

AU - Babai, László

AU - Hansen, Kristoffer Arnsfelt

AU - Podolskii, Vladimir V.

AU - Sun, Xiaoming

N1 - Conference code: 35

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-15155-2_8

DO - 10.1007/978-3-642-15155-2_8

M3 - Conference article

VL - 6281

SP - 66

EP - 77

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

Y2 - 23 August 2010 through 27 August 2010

ER -