Nov, 2009

流模型中识别好括号表达式

PDF
TL;DR研究了检查匹配括号问题 Dyck (s) ，提出了一个时间复杂度为 $\polylog (n)$、空间复杂度为 $\Order (\sqrt {n}\log n)$ 的单项式随机流算法，证明当允许双边误差时，此算法是最优的，甚至可以通过一些扭曲来证明一些困难实例的直和结果和基本情况下的组合下界之间的平衡。而当可以倒序访问输入流时，空间需求会显著缩小。
streaming algorithmsformal languagesparentheses matchingrandomized algorithmsspace complexity
发现论文，激发创造
  • 自注意力网络能够处理有界的分层语言

    证明自注意力网络可以处理具有层次结构的正式语言，例如 Dyck_k，但被证明对于近似自然语言来说过于有限，因此提出了在有限深度内捕获自然语言有界层次结构的 Dyck_(k,D) 子集，并构建了相应的硬注意力网络和软注意力网络。实验表明在此子集上训练的自注意力网络具有很好的泛化能力。

    May, 2021

  • 两趟图数据流算法的近二次下界

    研究表明，任何针对 $n$- 顶点有向图中 $s$-$t$ 可达性问题的二遍流图算法都需要近似二次的 $n^ {2-o (1)}$ 比特空间，这个相当于空间的下界也适用于其他基本问题，例如最大二分匹配和在无向图中（近似）最短路径。

    Sep, 2020

  • Gap-Hamming 距离的通信复杂度的最优下界

    本文通过引入高斯空间相关性的几何性质以及概率投影的方法证明了久负盛名的 Gap-Hamming-Distance 问题的随机通信复杂度的最优下界，并由此得出了在数据流模型中多遍通信所需的空间的最优下界。

    Sep, 2010

  • 分布式功能监测的严格界限

    通过新的直接求和定理，我们解决了数据流模型中估计频率矩阵和其它问题时的基础问题，并通过改进算法显著提高了界限。

    Dec, 2011

  • 动态图数据流中的密度最大子图

    本文提出了一种单遍算法，在动态图流模型下使用少量的空间和多项式时间精确地找到图中最大密度的 $(1+\epsilon)$ 近似值，进一步对算法的最小空间使用量进行了界定。

    Jun, 2015

  • 广播 CONGEST 网络中确定性子图检测

    本文提出了一种对于分布式计算中的广播 CONGEST 模型进行子图查找和枚举的简单确定性算法，并且给出了性能上限及其紧密性的证明。

    May, 2017

  • 频率向量上单变量几乎所有函数的流空间复杂度

    研究数据流近似算法中的函数近似问题，给出了一个条件，满足条件的函数可以进行有效的空间近似算法，解决了 Alon 等人 1996 年论文中的开放问题，并对几乎所有单变量函数进行了表征。

    Jan, 2016

  • 一种高效的空间和时间复杂度算法：在一遍动态流上维护稠密子图

    本研究针对图挖掘应用中的稠密子图问题，提出了一种动态算法，能够同时实现时间和空间效率，它是首个通过一遍流处理即可维护最稠密子图的算法。

    Apr, 2015

  • 对数直径轮并行图连通性

    研究在 MPC 模型下对图连通性问题进行优化，通过图直径参数化时间复杂度，得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法，并扩展到生成森林、DFS 序列、最小生成森林和瓶颈生成森林等相关图问题，并指出这些问题的类似界限推导可以应用于更快的布尔矩阵乘法算法。

    May, 2018

  • 置换码大小的 Gilbert-Varshamov 界的渐近优化

    研究长度为 $n$，最小汉明距离为 $d$ 的排列码的最大尺寸 $M (n,d)，$ 并探讨了 $d/n$ 比率固定的情况下，通过利用图论框架方法证明了在 $ d /n <0.5 $ 的情况下改进了 Gilbert-Varshamov bound

    Nov, 2013