首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Boolean constant degree functions on the slice are juntas
Authors:Yuval Filmus  Ferdinand Ihringer
Abstract:We show that a Boolean degree d function on the “slice” n]k?{(x1,,xn){0,1}:i=1nxi=k} is a junta (depends on a constant number γ(d) of coordinates), assuming that k,n?k are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube {0,1}n. Moreover, we show that the maximum number of coordinates that a Boolean degree d function can depend on is the same on the slice and on the hypercube.
Keywords:Corresponding author    05E30  Boolean function  Johnson scheme  Slice  Degree  Junta
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号