Weights of exact threshold functions

doi:10.1070/IM9113

	Weights of exact threshold functions
	Babai, L.1; Hansen, K. A.2; Podolskii, V. V.3,4; Sun, Xiaoming 5
	2021-12-01
发表期刊	IZVESTIYA MATHEMATICS
ISSN	1064-5632
卷号	85 期号:6 页码:1039-1059
摘要	We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree d. 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 R-n and the Boolean cube {0, 1}(n) or, in the general case, intersections of hypersurfaces of degree d in R-n and {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. There is a substantial gap between these bounds, a challenge for future work.
关键词	computational complexity Boolean functions threshold functions polynomial threshold functions anti-Hadamard matrices
DOI	10.1070/IM9113
收录类别	SCI
语种	英语
资助项目	NSF[CCF 1718902] ; Carlsberg Foundation ; Villum Kann Rasmussen postdoc fellowship ; Basic Research Programme of the National Research University Higher School of Economics ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; Strategic Priority Research Programme of the Chinese Academy of Sciences[XDA27000000] ; K. C. Wong Education Foundation
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000745286100001
出版者	TURPION LTD
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/19013
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Babai, L.
作者单位	1.Univ Chicago, Chicago, IL 60637 USA 2.Univ Aarhus, Aarhus, Denmark 3.Russian Acad Sci, Steklov Math Inst, Moscow, Russia 4.Natl Res Univ, Higher Sch Econ, Moscow, Russia 5.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Babai, L.,Hansen, K. A.,Podolskii, V. V.,et al. Weights of exact threshold functions[J]. IZVESTIYA MATHEMATICS,2021,85(6):1039-1059.
APA	Babai, L.,Hansen, K. A.,Podolskii, V. V.,&Sun, Xiaoming.(2021).Weights of exact threshold functions.IZVESTIYA MATHEMATICS,85(6),1039-1059.
MLA	Babai, L.,et al."Weights of exact threshold functions".IZVESTIYA MATHEMATICS 85.6(2021):1039-1059.