布尔函数分析
本文介绍了量子布尔函数的研究,包括量子性质测试、寻找布尔函数的大傅里叶系数的 Goldreich-Levin 算法的量子版本和 Friedgut,Kalai 和 Naor 关于布尔函数傅里叶谱的一个定理的两个量子版本。为了得到其中的一个推广,我们证明了 Bonami、Gross 和 Beckner 的超协调不等式的量子扩展。
Oct, 2008
FourierSAT 是一种基于布尔函数的傅里叶分析的不完全的 SAT 求解器,其提出一种用于解决具有不同类型限制的系统的代数框架,并通过实验证明在某些基准测试上,它比其他解算器更具鲁棒性。
Dec, 2019
该研究提出了一种称为真实解释的新概念,应用布尔函数的傅里叶分析来提供严谨的保证,以支持 ML 解释的 what-if 场景,并通过实验表明,与其他方法相比,我们的方法在各种半径大小的邻域中实现了 2 倍 - 50 倍左右的更低的解释误差。
Oct, 2022
该研究提出了一种基于代理模型和傅立叶展开的算法,用于优化纯分类型变量的黑盒函数,并在 RNA 序列优化和设计问题中取得了竞争性或优越性能,显著提高了计算成本和样本效率。
Feb, 2022
该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限,证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限,同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。
Apr, 2015
研究了在积概率空间中具有低影响力函数的问题,证明了具有低影响力和有界次数的多线性多项式的不变性原理,且边际条件下的分布在所有乘积空间中实质上是不变的,从而解决了在理论计算机科学中构建概率可检验证明和经济社会选择理论中的问题。
Mar, 2005
本论文提出了一种基于同调理论的函数同之间的复杂性分离,并利用组合和同调交换代数及 Stanley-Reisner 理论发展了该基础理论,并推导出关于多项式阈值函数的最大定理,并给出了同调 Farkas 引理,以及一些关注的应用实例。
Jan, 2017
本文考虑了对布尔函数进行随机评估问题,提出了一些近似算法,并基于随机次模集盖问题提出了一种新的适应性双贪心算法,新算法取得了更好的近似度,其中包括线性阈值公式的 3 近似算法,CDNF 公式 (和决策树) 的 O (log kd) 近似算法以及对线性函数的评分算法。
Mar, 2013
作者推崇他的流行课程和联合教材《离散数学》中的两个具体数学符号:1. 扩展 Iverson 的想法,用于特征函数和 Kronecker 三角洲在求和和积分中的使用;2. 将斯特林数与二项式系数放在同一水平线上,以更清楚的呈现与二项式系数类似的功能关系。
May, 1992