本文提出了一种基于二进制编码的非线性降维方法，能够在保留原始空间结构的同时，将高维数据嵌入到汉明立方体中，实现对任意集合中点的编码，并在理论上证明了该方法的最优位数下界及哈明距离下的非遗忘式编码，同时针对一般点集甚至无限点集提供了分析结果，并通过实验验证了理论结论的有效性。

Feb, 2015

通过在最小割问题和最大生成树包裹之间使用半对偶关系，结合我们先前开发的随机采样技术，我们显着提高了解决无向图上最小割问题的已知时间界限，通过随机算法在 O (mlog^3n) 时间内高概率找到 m 边 n 顶点图中的最小割，并使用 O (n^2logn) 时间内高概率找到所有最小割。

Dec, 1998

本文介绍了如何使用 Fourier 转换，尤其是环移矩阵来进行二进制嵌入，即将高维空间中的点映射到低维的 Hamming 立方体中以保留成对距离。作者提出了优化的方法，可以通过使用 k ~ δ^(-3) logN 个样本将 N 个 R^n 中的点正确地嵌入到 Hamming 立方体中，优于最优距离依赖关系 δ^(-2)，适用于标准条件 logN≲n^(1/3)。此外，如果满足 logN≲sqrt (n) 的较宽松条件，则可以将除随机小分数以外的所有点置于最优位置。该文认为此任务可以应用于其他非线性嵌入问题，并提出它可能有用的保证改进技术。

Mar, 2016

本文提出一种快速、距离保持的二进制嵌入算法，通过对稀疏矩阵进行稳定的噪音形状量化，实现将高维数据集转换为二进制序列，准确地表示了主题和研究领域。

Oct, 2020

本文提出了一种基于量化的快速 Johnson-Lindenstrauss 嵌入法，该方法使用有界正交系统和部分循环集合进行快速的嵌入，并利用噪声整形实现积极的降噪机制，该方法的误差多项式和指数衰减，是当前二进制嵌入和汉明距离所能达到的巅峰效果；此外，本文还提出了一种基于噪声整形机制的量化压缩感知度量方法，该方法在测量值的数量和比特数上实现了误差的多项式和指数衰减，是目前处理有限正交系统的最优表现。

Jan, 2018

研究了将单位球面子集嵌入到 Hamming 立方体中的方法，利用高斯宽度表征了失真和样本复杂度之间的权衡关系，并提供了嵌入点的局部嵌入以及更快的二进制嵌入等改进方案。

Dec, 2015

本文通过研究 n 维立方体图中每个 $(2^{n-1}+1)$- 顶点诱导子图的最大度数，证明了布尔函数的灵敏度和度数之间存在多项式关系，从而解决了一个理论计算机科学中的基础性问题：感度猜想。

Jul, 2019

研究了如何利用随机超平面对区域进行均匀的镶嵌，并利用超平面将欧氏空间中的有界集嵌入哈明空间中，从而实现对欧氏空间中集合的离散化降维。

Nov, 2011

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

Apr, 2015

设计一种子线性时间算法以估算一个图中三角形的数量，使用度查询、顶点对查询和邻居查询作为对图的查询，并证明该算法的查询复杂度是最优的。

Apr, 2015