学习图上的顶点的二元分类器,特别关注具有特定抽象意义的凸分区类作为分类器,通过多项式时间算法和结构洞见,以及与底层图的关联进行学习,进行了有关监督学习、在线学习和主动学习中的凸分区类的研究和结果验证。
May, 2024
用组合算法,我们展示了任何有限类型的自相似集合都可以表示为满足开放集条件的图导向结构。
Apr, 2024
该研究证明了在符合某些要求的示例分布下,多项式的弱会混淆学习几乎不可能,即使在输出更大的概念类的假设的情况下也是如此,这种难度结果从某种程度上包括以前的研究结果,包括最近的对单项式和半空间的适当学习的难度结果。
Dec, 2010
通过与半空间和所谓的并行煎饼分布的新颖联系,我们以统一的方式获得了较强(而且令人惊讶地简单)的在不适当的情况下学习半空间交集的下界,这是过去几年强大的高维统计学中许多下界构造的核心,我们还给出了统计查询框架下的无条件难度结果。
Feb, 2024
该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题,证明了最坏情况下的性能和效率的复杂性。
May, 2015
该研究揭示了任何 Hilbert 空间上的可分离态都可被写为 N 个纯积态的凸组合,提出了一个新的混合态可分离性判据。研究了 3×3 和 2×4 系统中具有正偏转部分转置的不可分离混合态,这些状态代表比以前更微妙的纠缠。
Mar, 1997
本文介绍了量子计算文献中关于密度矩阵在张量积空间 H [N] 上的非经典行为、其 “不可分割性” 以及如何计算其到最近可分割密度矩阵的距离并量化其 “纠缠度” 等数学问题及相关研究进展。
Mar, 2001
以差分隐私为前提,对解决集合覆盖问题的可能性结果进行了研究,发现在部分集合覆盖问题中,这种难度结果会消失,从而提供了具有非平凡逼近保证的显式集合覆盖的不同隐私算法,并给出了百科拉蒂问题的私有(双目标)逼近算法,该问题是 $k$-center/$k$-supplier 的推广,该算法显示了松弛覆盖要求为仅服务人口的一部分,从而使我们能够避免本质上的困难。
Jul, 2022
本文研究了扩展时序约束问题的复杂性,并针对一组量词自由的 “小于等于(leq)” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$,$x_2$,…,$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后,作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题,并提出了独立于通用代数和模型理论的分裂定理。
Feb, 2016
对于有限维二分量子系统,找到了以 $l_p$ 范数表示的不分离(unentangled)矩阵围绕恒等矩阵的最大球的确切大小,从而得出了相关的几何充分条件:二分量子密度矩阵的纯度 $ r ho^2$ 不可过大。这意味着可以应用这些结果来解决一些算法问题,比如计算一个状态是否纠缠,或者实际应用中,可以获取 NMR 量子计算实现或其他实验情况下到达的状态中纠缠存在性或者特性的信息。
Apr, 2002