On the modulo degree complexity of Boolean functions

doi:10.1016/j.tcs.2018.04.049

	On the modulo degree complexity of Boolean functions
	Li, Qian 1,2; Sun, Xiaoming 1,2
	2020-05-24
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	818 页码:32-40
摘要	For each integer m >= 2, every Boolean function f can be expressed as a unique multilinear polynomial modulo m, and the degree of this multilinear polynomial is called its modulo m degree. In this paper we investigate the modulo degree complexity of total Boolean functions initiated by Parikshit Gopalan et al. [9], in which they asked the following question: whether the degree complexity of a Boolean function is polynomially related with its modulo m degree. For m be a power of primes, it is already known that the module m degree can be arbitrarily smaller compare to the degree complexity (see Section 2 for details). When m has at least two distinct prime factors, the question remains open. Towards this question, our results include: (1) we obtain some nontrivial equivalent forms of this question; (2) we affirm this question for some special classes of functions; (3) we prove a no-go theorem, explaining why this problem is difficult to attack from the computational complexity point of view; (4) we show a super-linear separation between the degree complexity and the modulo m degree. (C) 2018 Elsevier B.V. All rights reserved.
关键词	Boolean function Degree complexity Polynomial Decision tree complexity Hypergraph property
DOI	10.1016/j.tcs.2018.04.049
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61502449] ; National Natural Science Foundation of China[61602440] ; Ministry of Science and Technology of the People's Republic of China ; 973 Program of China[2016YFB1000201]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000524291300005
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/14250
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Qian; Sun, Xiaoming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Li, Qian,Sun, Xiaoming. On the modulo degree complexity of Boolean functions[J]. THEORETICAL COMPUTER SCIENCE,2020,818:32-40.
APA	Li, Qian,&Sun, Xiaoming.(2020).On the modulo degree complexity of Boolean functions.THEORETICAL COMPUTER SCIENCE,818,32-40.
MLA	Li, Qian,et al."On the modulo degree complexity of Boolean functions".THEORETICAL COMPUTER SCIENCE 818(2020):32-40.