Weights of exact threshold functions

L. Babai; K. A. Hansen; V. V. Podolskii; Xiaoming Sun

doi:10.1070/IM9113

Weights of exact threshold functions

L. Babai, K. A. Hansen, V. V. Podolskii, Xiaoming Sun

Institut for Datalogi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

1 Citationer (Scopus)

Abstract

We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree. 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. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of the integer coefficients of linear equations required to express every possible intersection of a hyperplane in and the Boolean cube or, in the general case, intersections of hypersurfaces of degree in and. 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 of the affine subspace spanned by the solutions and give upper and lower bounds in this case as well. There is a substantial gap between these bounds, a challenge for future work.

Originalsprog	Engelsk
Tidsskrift	Izvestiya: Mathematics
Vol/bind	85
Nummer	6
Sider (fra-til)	1039-1059
Antal sider	21
ISSN	1064-5632
DOI	https://doi.org/10.1070/IM9113
Status	Udgivet - nov. 2021

Adgang til dokumentet

10.1070/IM9113

Andre filer og links

Link to publication in Scopus

Citationsformater

@article{30ec17f33db941d1b38c74b895b54c90,

title = "Weights of exact threshold functions",

abstract = "We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree. 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. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of the integer coefficients of linear equations required to express every possible intersection of a hyperplane in and the Boolean cube or, in the general case, intersections of hypersurfaces of degree in and. 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 of the affine subspace spanned by the solutions and give upper and lower bounds in this case as well. There is a substantial gap between these bounds, a challenge for future work. ",

keywords = "anti-Hadamard matrices, Boolean functions, computational complexity, polynomial threshold functions, threshold functions",

author = "L. Babai and Hansen, {K. A.} and Podolskii, {V. V.} and Xiaoming Sun",

note = "Publisher Copyright: {\textcopyright} 2021 Russian Academy of Sciences (DoM) and London Mathematical Society.",

year = "2021",

month = nov,

doi = "10.1070/IM9113",

language = "English",

volume = "85",

pages = "1039--1059",

journal = "Izvestiya: Mathematics",

issn = "1064-5632",

publisher = "Steklov Mathematical Institute of Russian Academy of Sciences",

number = "6",

}

TY - JOUR

T1 - Weights of exact threshold functions

AU - Babai, L.

AU - Hansen, K. A.

AU - Podolskii, V. V.

AU - Sun, Xiaoming

PY - 2021/11

Y1 - 2021/11

N2 - We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree. 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. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of the integer coefficients of linear equations required to express every possible intersection of a hyperplane in and the Boolean cube or, in the general case, intersections of hypersurfaces of degree in and. 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 of the affine subspace spanned by the solutions and give upper and lower bounds in this case as well. There is a substantial gap between these bounds, a challenge for future work.

AB - We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree. 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. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of the integer coefficients of linear equations required to express every possible intersection of a hyperplane in and the Boolean cube or, in the general case, intersections of hypersurfaces of degree in and. 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 of the affine subspace spanned by the solutions and give upper and lower bounds in this case as well. There is a substantial gap between these bounds, a challenge for future work.

KW - anti-Hadamard matrices

KW - Boolean functions

KW - computational complexity

KW - polynomial threshold functions

KW - threshold functions

UR - http://www.scopus.com/inward/record.url?scp=85124191153&partnerID=8YFLogxK

U2 - 10.1070/IM9113

DO - 10.1070/IM9113

M3 - Journal article

AN - SCOPUS:85124191153

SN - 1064-5632

VL - 85

SP - 1039

EP - 1059

JO - Izvestiya: Mathematics

JF - Izvestiya: Mathematics

IS - 6

ER -

Weights of exact threshold functions

Abstract

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater