Jul, 2019

超立方体的诱导子图及敏感性猜想的证明

PDF
TL;DR本文通过研究 n 维立方体图中每个 $(2^{n-1}+1)$- 顶点诱导子图的最大度数，证明了布尔函数的灵敏度和度数之间存在多项式关系，从而解决了一个理论计算机科学中的基础性问题：感度猜想。
cube graphmaximum degreesensitivity conjectureboolean functiontheoretical computer science
发现论文，激发创造
  • 通过 SOS 和 Frankl--Rödl 图的超对比不等式

    SUMMARY IN SIMPLIFIED CHINESE HERE

    Dec, 2012

  • 在稀疏图中列出所有极大团在近优时间内

    该论文研究了 $n$ 个顶点的图的退化度，提出了基于 Bron-Kerbosch 算法的近似最优固定参数可跟踪算法，用以枚举所有最大团，并给出算法的时间复杂度、最大团的数量及匹配的上下界。

    Jun, 2010

  • 光滑布尔函数很容易：低灵敏度函数的高效算法

    该文章证明了计算平滑的布尔函数的计算上界、点态噪声稳定性保证和局部纠正误差，为攻击布尔函数判断树猜想提供了新的证据和新方向。

    Aug, 2015

  • 贝叶斯网络近似最优度数测试

    本文研究了在给定概率分布 P（{0,1}^n 上），并具有样本访问的情况下，测试潜在贝叶斯网络的最大入度的问题。研究表明，该问题的样本复杂度为 Θ(2^(n/2)/ε^2) 。我们的算法依赖于先前用于获得样本最优测试器的测试通过学习框架；为了应用该框架，我们开发了新的算法来进行 “近似适当” 的贝叶斯网络学习，并在 χ^2 差异下高概率学习，这具有独立兴趣。

    Apr, 2023

  • 边独立随机图的谱

    本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质，其中包括对 Erdős-Rényi 图的分析，证明了矩阵与其期望的偏差在一定条件下的上界，并对已有的结果进行了改进。

    Apr, 2012

  • 通过更高的特征值实现许多的稀疏割

    该论文研究了通过 Laplacian 矩阵中的特征值来优化图的分割，提出了基于谱投影和随机取整的多项式时间算法，并证明得到的上限是最优的。

    Nov, 2011

  • 测试图的聚类结构

    在有界度模型的性质测试框架中研究了识别图的集群结构问题，提出了一个亚线性算法，可识别由参数 k, phi, epsilon 制定的 (d) 有界度图，并且是渐近最优的，关键是集群内外的 conductance。

    Apr, 2015

  • 最大独立集合的最佳低阶硬度

    研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

    Oct, 2020

  • 二次时间内识别偏立方体

    本研究介绍了如何在 O (n^2) 的时间复杂度内测试一个由 n 个顶点和 m 条边组成的图是否为 partial cube，并在此基础上找到一个将该图转化为 distance-preserving embedding 进而嵌入到 hypercube 中的方法，从而实现优化。

    May, 2007

  • 最大化固定大小独立集的数量

    研究独立集的数量及其最大化问题，通过证明假设得出其在最小度至少为 δ 的完全二分图中实现最大化。

    Nov, 2013