关于k-Hamming和k-Edit距离

Jun, 2023

On the $k$-Hamming and $k$-Edit Distances

Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi...

TL;DR本文研究了加权k-Hamming和k-Edit距离级它们分别是经典Hamming和Edit距离的自然推广。研究的主要结果是，对于任何k≥2，DECIS-k-Hamming问题是P-SPACE完全的，DECIS-k-Edit问题是NEXPTIME完全的。

Abstract

In this paper we consider the weighted $k$-Hamming and $k$-Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any $k\geq 2$ the decis-$k$-Hamming problem is $\mathbb{P}$-SPACE-complete and the

发现论文，激发创造

二进制哈希中的不对称性之力

利用两个不同的编码映射，通过汉明距离逼近二进制相似性，生成更短更准确的哈希码。

Nov, 2013

极端类别的标记压缩方案

本研究针对极端分类，基于Sandwich定理构建了一个样本压缩方案，其尺寸等于其VC维度，并提出了一些有关极端分类的组合结构和无标签压缩方案存在性的问题。

May, 2015

子模哈明度量

通过利用次模性，我们探索了一类未被充分开发的函数（正多项式），它可以在二进制向量对之间定义恰当的离散度量，并且相对容易进行优化。我们还应用这些函数进行聚类和生成多样性k-best列表等任务，并在实验中证明了这些函数及相关算法的有效性。

Nov, 2015

有限闭包系统中的极大闭集和半空间分离

该论文讨论了抽象闭包系统中的半空间分离问题，并提出了一种基于贪心算法的方法来解决这一问题，并在子集包含关系的情况下进行了应用。

Jan, 2020

梯度下降的复杂性：CLS = PPAD ∩ PLS

该论文研究了在有界凸多面体域上通过梯度下降解决的搜索问题，并表明该类等于两个众所周知的类的交集：PPAD和PLS。同时证明了在区间[0,1]x[0,1]上计算连续可微函数的Karush-Kuhn-Tucker（KKT）点是PPAD和PLS完全的第一个非人工问题。该研究结果还表明，Daskalakis和Papadimitriou定义的CLS类（连续局部搜索） - 它是PPAD和PLS的更“自然”对应物，其中包含许多有趣的问题 - 本身等于PPAD和PLS。

Nov, 2020

二元CSP及其半环泛化的组件双宽度参数

本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性，探讨了基于半环的代数方法，提出了组件双宽属性的 generalization。研究表明，在受限制的条件下，该方法在多种问题中取得了优秀算法复杂度上界。

Jul, 2022

变长编码与误差检测领域的交叉

研究了与自动机同构相关的几种赋范情况下，对于给定的正则码，能否判断基于$\tau_{d,k}$的条件的变长编码的错误检测和纠正能力的问题。

Aug, 2022

图上k-中心问题的动态算法

提供了首个对动态图进行边更新的 k-中心问题的高效算法

Jul, 2023

利用SAT求解器自动寻找难度缩减

通过基于SAT的框架，我们对具有禁止子结构的符号映射的完整问题进行了首次的彻底研究，并对数千种NP完全问题的结构进行了分类，包括内部三元组系统和推广到更高维度的结构。

Feb, 2024

格罗莫夫-瓦瑟斯坦距离的NP难度

本文探讨了格罗莫夫-瓦瑟斯坦（GW）距离的NP难度问题，填补了文献中对该性质的不足说明。研究指出GW优化问题的非凸性质直接导致其NP难度，并通过多个具体示例进一步阐释了这一非凸性。研究结果有助于理解GW距离在有限空间中的复杂性，具有重要的理论意义。

Aug, 2024