Weights of exact threshold functions
文献类型：期刊论文
| 作者 | Babai, L.4; Hansen, K. A.5; Podolskii, V. V.1,3; Sun, Xiaoming2 |
| 刊名 | IZVESTIYA MATHEMATICS
 |
| 出版日期 | 2021-12-01 |
| 卷号 | 85期号:6页码:1039-1059 |
| 关键词 | computational complexity Boolean functions threshold functions polynomial threshold functions anti-Hadamard matrices |
| ISSN号 | 1064-5632 |
| DOI | 10.1070/IM9113 |
| 英文摘要 | 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. |
| 资助项目 | 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记录号 | WOS:000745286100001 |
| 出版者 | TURPION LTD |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/19012]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Babai, L. |
| 作者单位 | 1.Russian Acad Sci, Steklov Math Inst, Moscow, Russia 2.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 3.Natl Res Univ, Higher Sch Econ, Moscow, Russia 4.Univ Chicago, Chicago, IL 60637 USA 5.Univ Aarhus, Aarhus, Denmark |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。