This paper describes a purely functional library for computing level-$p$-complexity of Boolean functions, and applies it to two-level iterated majority. Boolean functions are simply functions from $n$ bits to one bit, and they can describe digital circuits, voting systems, etc. An example of a Boolean function is majority, which returns the value that has majority among the $n$ input bits for odd $n$. The complexity of a Boolean function $f$ measures the cost of evaluating it: how many bits of the input are needed to be certain about the result of $f$. There are many competing complexity measures but we focus on level-$p$-complexity -- a function of the probability $p$ that a bit is 1. The level-$p$-complexity $D_p(f)$ is the minimum expected cost when the input bits are independent and identically distributed with Bernoulli($p$) distribution. We specify the problem as choosing the minimum expected cost of all possible decision trees -- which directly translates to a clearly correct, but very inefficient implementation. The library uses thinning and memoization for efficiency and type classes for separation of concerns. The complexity is represented using polynomials, and the order relation used for thinning is implemented using polynomial factorisation and root-counting. Finally we compute the complexity for two-level iterated majority and improve on an earlier result by J.~Jansson.


翻译:使用瘦化,记忆化和多项式计算布尔函数的级别-p-复杂度 翻译摘要: 这篇论文介绍了一种纯函数库,用于计算布尔函数的级别-p-复杂度,并将其应用于两级迭代大多数。布尔函数仅是从n位到一个比特的函数,它们可以描述数字电路、投票系统等。布尔函数的一个例子是多数,对于奇数n,它返回在n个输入比特中具有多数的值。 布尔函数的复杂度度量其计算的成本:需要多少输入比特才能确定$f$的结果。有许多竞争的复杂度度量,但我们专注于级别-p-复杂度——一个与比特$p$的概率相关的函数。级别-p-复杂度$D_p(f)$是当输入比特独立且带有Bernoulli分布($p$)时,期望成本的最小值。我们将问题规定为选择所有可能决策树中的最小预期成本——这直接转化为一个明确正确但效率极低的实现。该库使用了瘦化和记忆化来提高效率,使用类型类来分离关注点。复杂度使用多项式表示,用于瘦化的顺序关系使用多项式分解和根计数实现。最后,我们计算了两级迭代大多数的复杂度,并改进了J.~Jansson的早期结果。

0
下载
关闭预览

相关内容

在数学中,布尔函数(Boolean function)描述如何基于对布尔输入的某种逻辑计算确定布尔值输出,它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色,特别是在对称密钥算法的设计中(参见S-box)。
机器学习损失函数概述,Loss Functions in Machine Learning
专知会员服务
82+阅读 · 2022年3月19日
【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
Code Smell 重构你的日常代码-圈复杂度高多层嵌套
阿里技术
1+阅读 · 2022年11月11日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
笔记 | Deep active learning for named entity recognition
黑龙江大学自然语言处理实验室
24+阅读 · 2018年5月27日
上百份文字的检测与识别资源,包含数据集、code和paper
数据挖掘入门与实战
17+阅读 · 2017年12月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月18日
VIP会员
相关资讯
Code Smell 重构你的日常代码-圈复杂度高多层嵌套
阿里技术
1+阅读 · 2022年11月11日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
笔记 | Deep active learning for named entity recognition
黑龙江大学自然语言处理实验室
24+阅读 · 2018年5月27日
上百份文字的检测与识别资源,包含数据集、code和paper
数据挖掘入门与实战
17+阅读 · 2017年12月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员