布尔匹匹配对于数字集成电路设计非常重要。即使对于只有几个变量的函数，粗糙的布尔匹匹配的详尽方法也是昂贵的，因为这种算法对于N变量布尔函数的算法的时间复杂度是$ O（2 ^ {n + 1} n！）$。灵敏度是一个重要的特征，以及布尔函数复杂性的衡量标准。它已被用于分析不同领域算法的复杂性。该措施可以被视为布尔函数的签名，并且具有很大的潜力，可以帮助减少布尔匹匹配的搜索空间。在本文中，我们将布尔敏感性介绍到布尔匹配和设计几个相关的相关象征中，以增强快速布尔匹匹配。首先，我们提出了一些与布尔等价的敏感性相关的新签名。然后，我们证明了这些签名是布尔匹匹配的先决条件，我们可以使用它来减少匹配问题的搜索空间。此外，我们开发了一种快速的灵敏度计算方法来计算和比较两个布尔函数的这些签名。与传统的辅助因子和对称检测方法相比，灵敏度是另一个维度的一系列签名。我们还表明，可以轻松地集成到传统方法中的灵敏度，并将不匹配的布尔函数更快地区分。据我们所知，这是第一个向布尔匹配引入敏感性的工作。实验结果表明，我们在本文中提出的敏感性相关签名可以在很大程度上将搜索空间减少，并且通过最先进的布尔匹匹配方法执行高达3倍的加速。

Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras. In subsequent work with Kleinberg and Szegedy, they connected this to the search for combinatorial objects called strong uniquely solvable puzzles (strong USPs). We begin a systematic computer-aided search for these objects. We develop and implement constraint-based algorithms build on reductions to $\mathrm{SAT}$ and $\mathrm{IP}$ to verify that puzzles are strong USPs, and to search for large strong USPs. We produce tight bounds on the maximum size of a strong USP for width $k \le 5$, construct puzzles of small width that are larger than previous work, and improve the upper bounds on strong USP size for $k \le 12$. Although our work only deals with puzzles of small-constant width, the strong USPs we find imply matrix multiplication algorithms that run in $O(n^\omega)$ time with exponent $\omega \le 2.66$. While our algorithms do not beat the fastest algorithms, our work provides evidence and, perhaps, a path to finding families of strong USPs that imply matrix multiplication algorithms that are more efficient than those currently known.

结构分解方法，例如普遍的高树木分解，已成功用于解决约束满意度问题（CSP）。由于可以重复使用分解以求解具有相同约束范围的CSP，因此即使计算本身很难，将资源投资于计算良好的分解是有益的。不幸的是，即使示波器仅略有变化，当前方法也需要计算全新的分解。在本文中，我们迈出了解决CSP $ P $分解的问题的第一步，以使其成为由$ P $修改产生的新CSP $ P'$的有效分解。即使从理论上讲问题很难，我们还是提出并实施了一个有效更新GHD的框架。我们算法的实验评估强烈提出了实际适用性。

图形神经网络（GNNS）是关于图形机器学习问题的深度学习架构。最近已经表明，GNN的富有效力可以精确地由组合Weisfeiler-Leman算法和有限可变计数逻辑来表征。该对应关系甚至导致了对应于更高维度的WL算法的新的高阶GNN。本文的目的是解释GNN的这些描述性特征。

大多数-AT是确定联合正常形式（CNF）中输入$ N $的最低价公式的问题至少为2 ^ {n-1} $令人满意的作业。在对概率规划和推论复杂性的各种AI社区中，广泛研究了多数饱和问题。虽然大多数饱满为期40多年来，但自然变体的复杂性保持开放：大多数 - $ k $ SAT，其中输入CNF公式仅限于最多$ k $的子句宽度。我们证明，每辆$ k $，大多数 - $ k $ sat是在p的。事实上，对于任何正整数$ k $和ratic $ \ rho \ in（0,1）$ in（0,1）$与有界分比者，我们给出了算法这可以确定给定的$ k $ -cnf是否至少有$ \ rho \ cdot 2 ^ n $令人满意的分配，在确定性线性时间（而先前的最着名的算法在指数时间中运行）。我们的算法对计算复杂性和推理的复杂性具有有趣的积极影响，显着降低了相关问题的已知复杂性，例如E-Maj-$ K $ Sat和Maj-Maj- $ K $ Sat。在我们的方法中，通过提取在$ k $ -cnf的相应设置系统中发现的向日葵，可以通过提取向日葵来解决阈值计数问题的有效方法。我们还表明，大多数 - $ k $ sat的易腐烂性有些脆弱。对于密切相关的gtmajority-sat问题（我们询问给定公式是否超过2 ^ {n-1} $满足分配），这已知是pp-cleanting的，我们表明gtmajority-$ k $ sat在p for $ k \ le 3 $，但为$ k \ geq 4 $完成np-cleante。这些结果是违反直觉的，因为这些问题的“自然”分类将是PP完整性，因为GTMAJority的复杂性存在显着差异 - $ k $ SAT和MOSTION- $ K $ SAT为所有$ k \ ge 4 $。

工作流程满意度问题（WSP）是一个充分研究的问题，在访问控制方面寻求授权用户分配工作流程的每个步骤，但要受工作流规范约束。人们注意到，与WSP的现实世界实例中的用户数量相比，数字$ k $通常很少。因此，$ k $被认为是WSP参数复杂性研究中的参数。虽然通常证明WSP为W [1] -HARD，但WSP仅限于用户独立的（UI）约束的特殊情况，是固定参数可拖动的（FPT）。但是，对UI限制的限制可能是不切实际的。为了有效处理非UI约束，我们介绍了约束的分支因素的概念。只要约束的分支因子相对较小，并且非UI约束的数量是合理的，那么WSP就可以在fpt时间内解决。扩展了Karapetyan等人的结果。 （2019年），我们证明了通用求解器能够在与适当的配方一起使用时在WSP上实现与FPT一样的性能。这使人们能够解决大多数实用的WSP实例。尽管本身很重要，但我们希望这一结果还将激励研究人员寻找其他FPT问题的FPT感知表述。

随着神经网络作为任务至关重要系统中组成部分的越来越多的整合，越来越需要确保它们满足各种安全性和livesice要求。近年来，已经提出了许多声音和完整的验证方法，但这些方法通常受到严重的可伸缩性限制。最近的工作提出了通过抽象 - 再填充功能增强这种验证技术的增强，这些功能已被证明可以提高可伸缩性：而不是验证大型且复杂的网络，而是验证者构造，然后验证一个较小的网络，其正确性意味着原始的正确性网络。这种方案的缺点是，如果验证较小的网络失败，则验证者需要执行改进步骤，以增加验证网络的大小，然后开始从SCRATCH验证新网络 - 有效地``'浪费''它的早期工作在验证较小的网络方面。在本文中，我们通过使用\ emph {残留推理}来提高基于抽象的神经网络验证的增强：在验证抽象网络时使用信息的过程，以加快对精制网络的验证。本质上，该方法允许验证者存储有关确保正确行为的搜索空间部分的信息，并允许其专注于可能发现错误的区域。我们实施了我们的方法，以扩展到Marabou验证者，并获得了有希望的结果。

学习优化是一个快速增长的领域，旨在使用机器学习（ML）来解决优化问题或改善现有的优化算法。特别是，图形神经网络（GNN）被认为是用于优化问题的合适ML模型，其变量和约束是置换的 - 例如线性程序（LP）。尽管文献报道了令人鼓舞的数值结果，但本文确定了将GNN应用于解决LP的理论基础。给定LPS的任何尺寸限制，我们构造了一个GNN，该GNN将不同的LP映射到不同的输出。我们表明，正确构建的GNN可以可靠地预测广泛类别中每个LP的可行性，界限和最佳解决方案。我们的证明是基于最近发现的Weisfeiler-Lehman同构测试与GNN之间的联系。为了验证我们的结果，我们培训了一个简单的GNN，并提出了将LP映射到其可行性和解决方案中的准确性。

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ mathfrak {c} $是一类多项式大小概念，假设$ \ mathfrak {c} $可以在统一分布下的成员查询，错误$ 1/2 - \ gamma $通过时间$ t $量子算法。我们证明如果$ \ gamma ^ 2 \ cdot t \ ll 2 ^ n / n $，则$ \ mathsf {bqe} \ nsubseteq \ mathfrak {c} $，其中$ \ mathsf {bqe} = \ mathsf {bque} [2 ^ {o（n）}] $是$ \ mathsf {bqp} $的指数时间模拟。在$ \ gamma $和$ t $中，此结果是最佳的，因为它不难学习（经典）时间$ t = 2 ^ n $（没有错误） ，或在Quantum Time $ t = \ mathsf {poly}（n）$以傅立叶采样为单位为1/2美元（2 ^ { - n / 2}）$。换句话说，即使对这些通用学习算法的边际改善也会导致复杂性理论的主要后果。我们的证明在学习理论，伪随机性和计算复杂性的几个作品上构建，并且至关重要地，在非凡的经典学习算法与由Oliveira和Santhanam建立的电路下限之间的联系（CCC 2017）。扩展他们对量子学习算法的方法，结果产生了重大挑战。为此，我们展示了伪随机发电机如何以通用方式意味着学习到较低的连接，构建针对均匀量子计算的第一个条件伪随机发生器，并扩展了Impagliazzo，JaiSwal的本地列表解码算法。 ，Kabanets和Wigderson（Sicomp 2010）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

决策树学习是机器学习中广泛使用的方法，在需要简洁明了的模型的应用中受到青睐。传统上，启发式方法用于快速生产具有相当高准确性的模型。然而，一个普遍的批评是，从精度和大小方面，所产生的树可能不一定是数据的最佳表示。近年来，这激发了最佳分类树算法的发展，这些算法与执行一系列本地最佳决策的启发式方法相比，在全球范围内优化决策树。我们遵循这一工作线，并提供了一种基于动态编程和搜索的最佳分类树的新颖算法。我们的算法支持对树的深度和节点数量的约束。我们方法的成功归因于一系列专门技术，这些技术利用了分类树独有的属性。传统上，最佳分类树的算法受到了高运行时的困扰和有限的可伸缩性，但我们在一项详细的实验研究中表明，我们的方法仅使用最先进的时间所需的时间，并且可以处理数十个数据集的数据集在数千个实例中，提供了几个数量级的改进，并特别有助于实现最佳决策树的实现。

我们从逻辑和公式大小方面概念化了解释性，在非常一般的环境中给出了许多相关的解释性定义。我们的主要兴趣是所谓的特殊解释问题，旨在解释输入模型中输入公式的真实价值。解释是一个最小尺寸的公式，（1）与输入模型上的输入公式一致，（2）将所涉及的真实价值传输到全球输入公式，即每个模型上。作为一个重要的例子，我们在这种情况下研究了命题逻辑，并表明在多项式层次结构的第二级中，特殊的解释性问题是完整的。我们还将在答案集编程中提供了此问题的实施，并研究了其与解释N-Queens和主导集合问题的答案有关的能力。

在过去十年中，图形内核引起了很多关注，并在结构化数据上发展成为一种快速发展的学习分支。在过去的20年中，该领域发生的相当大的研究活动导致开发数十个图形内核，每个图形内核都对焦于图形的特定结构性质。图形内核已成功地成功地在广泛的域中，从社交网络到生物信息学。本调查的目标是提供图形内核的文献的统一视图。特别是，我们概述了各种图形内核。此外，我们对公共数据集的几个内核进行了实验评估，并提供了比较研究。最后，我们讨论图形内核的关键应用，并概述了一些仍有待解决的挑战。

伊瓦玛（Iwama）引入的命中公式是一类不寻常的命题CNF公式。它们的可满足性不仅可以在多项式时间内确定，而且甚至可以以封闭形式计算其模型。这与其他多项式定义类别形成鲜明对比，这些类别通常具有基于回溯和分辨率的算法，并且模型计数仍然很难，例如2-SAT和HORN-SAT。但是，那些基于分辨率的算法通常很容易地暗示着在分辨率复杂性上的上限，这对于达到公式而缺少。击中公式难以解决吗？在本文中，我们采取了第一步，回答这个问题。我们表明，击中公式的分辨率复杂性由Kullmann和Zhao首先研究的所谓不可约合的击球公式主导，这些配方不能由较小的击球公式组成。但是，根据定义，很难构建大型不可理解的击中公式。甚至还不知道是否存在无限的许多。基于我们的理论结果，我们在Nauty软件包之上实施了有效的算法，以列举所有不可约14个条款的不可约束的击中公式。我们还通过将已知的SAT编码用于我们的目的来确定生成的击中公式的确切分辨率复杂性。我们的实验结果表明，击中公式确实很难解决。

本文研究了一般D-均匀的HyperGraph随机块模型（D-HSBM）中精确恢复的基本限制，其中n个节点被分配到具有相对大小的k差异群落中（p1，...，pk）。具有基数d的节点的每个子集都是独立生成的，作为订单-D超边，其一定概率取决于D节点所属的地面真相群落。目标是根据观察到的超图准确地恢复K隐藏的社区。我们表明存在一个尖锐的阈值，因此可以在阈值之上实现精确的恢复，而不可能在阈值以下（除了将精确指定的小参数制度之外）。该阈值是根据我们称为社区之间普遍的Chernoff-Hellinger分歧的数量来表示的。我们对该通用模型的结果恢复了标准SBM和D-HSBM的先前结果，其中两个对称群落作为特殊情况。在证明我们的可实现结果的途径中，我们开发了一种符合阈值的多项式两阶段算法。第一阶段采用某种超图光谱聚类方法来获得社区的粗略估计，第二阶段通过局部细化步骤单独完善每个节点，以确保精确恢复。

最近已经提出了几个查询和分数来解释对ML模型的个人预测。鉴于ML型号的灵活，可靠和易于应用的可解释性方法，我们预见了需要开发声明语言以自然地指定不同的解释性查询。我们以原则的方式通过源于逻辑，称为箔，允许表达许多简单但重要的解释性查询，并且可以作为更具表现力解释性语言的核心来实现这一语言。我们研究箔片查询的两类ML模型的计算复杂性经常被视为容易解释：决策树和OBDD。由于ML模型的可能输入的数量是尺寸的指数，因此箔评估问题的易易性是精细的，但是可以通过限制模型的结构或正在评估的箔片段来实现。我们还以高级声明语言包装的箔片的原型实施，并执行实验，表明可以在实践中使用这种语言。

在本文中，我们介绍了两级晶格神经网络（FAST BATLLLNN）的刀具快速箱分析，作为两级格子（TLL）神经网络（NNS）的盒状输出约束的快速验证器。特别地，快速Batllnn可以验证给定TLL NN的输出是否始终在指定的超矩形内呈现，只要其输入约束到指定的凸多特级（不一定是超矩形）。 FAST BATLLNN使用TLL架构的唯一语义和盒状输出约束的解耦性质，从而显着提高具有通用多粒输出约束的TLL的已知多项式验证算法的验证性能。在本文中，我们评估了快速Batllnn的性能和可扩展性，无论是自身的权利，也与应用于TLL NNS的最先进的NN Verifers相比。快速的Batllnn比较最快的NN Verifiers非常有利地比较，完成我们的合成TLL测试台超过400倍，而不是最近的竞争对手。

对于应用智能，公用事业驱动的模式发现算法可以识别数据库中有见地和有用的模式。但是，在这些用于模式发现的技术中，模式的数量可能很大，并且用户通常只对其中一些模式感兴趣。因此，有针对性的高实数项目集挖掘已成为一个关键的研究主题，其目的是找到符合目标模式约束而不是所有模式的模式的子集。这是一项具有挑战性的任务，因为在非常大的搜索空间中有效找到量身定制的模式需要有针对性的采矿算法。已经提出了一种称为Targetum的第一种算法，该算法采用了类似于使用树结构进行后处理的方法，但是在许多情况下，运行时间和内存消耗都不令人满意。在本文中，我们通过提出一种带有模式匹配机制的新型基于列表的算法（名为Thuim（有针对性的高实用项目集挖掘））来解决此问题，该机制可以在挖掘过程中迅速匹配高实用项，以选择目标模式。在不同的数据集上进行了广泛的实验，以将所提出算法的性能与最新算法进行比较。结果表明，THUIM在运行时和内存消耗方面表现良好，并且与Targetum相比具有良好的可扩展性。

在本文档中，我们介绍了Pycsp $ 3 $，是一个Python库，它允许我们以声明方式编写组合受限问题的模型。目前，使用Pycsp $ 3 $，您可以编写约束满足和优化问题的模型。更具体地说，您可以构建CSP（约束满足问题）和COP（约束优化问题）模型。重要的是，建模和解决阶段之间存在完整的分离：您编写模型，您可以编译它（同时提供一些数据）以生成XCSP $ 3 $ instance（文件），并且您通过方法解决该问题实例约束求解器。您还可以直接在Pycsp $ 3 $中试驾解决程序，可能进行增量解决策略。在本文档中，您将找到您需要了解的所有关于Pycsp $ 3 $的所有信息，具有超过50个说明性型号。

High-utility sequential pattern mining (HUSPM) has emerged as an important topic due to its wide application and considerable popularity. However, due to the combinatorial explosion of the search space when the HUSPM problem encounters a low utility threshold or large-scale data, it may be time-consuming and memory-costly to address the HUSPM problem. Several algorithms have been proposed for addressing this problem, but they still cost a lot in terms of running time and memory usage. In this paper, to further solve this problem efficiently, we design a compact structure called sequence projection (seqPro) and propose an efficient algorithm, namely discovering high-utility sequential patterns with the seqPro structure (HUSP-SP). HUSP-SP utilizes the compact seq-array to store the necessary information in a sequence database. The seqPro structure is designed to efficiently calculate candidate patterns' utilities and upper bound values. Furthermore, a new upper bound on utility, namely tighter reduced sequence utility (TRSU) and two pruning strategies in search space, are utilized to improve the mining performance of HUSP-SP. Experimental results on both synthetic and real-life datasets show that HUSP-SP can significantly outperform the state-of-the-art algorithms in terms of running time, memory usage, search space pruning efficiency, and scalability.

我们考虑了一个类别级别的感知问题，其中给定的2D或3D传感器数据描绘了给定类别的对象（例如，汽车），并且必须重建尽管级别的可变性，但必须重建对象的3D姿势和形状（即，不同的汽车模型具有不同的形状）。我们考虑了一个主动形状模型，其中 - 对于对象类别 - 我们获得了一个潜在的CAD模型库，描述该类别中的对象，我们采用了标准公式，其中姿势和形状是通过非非2D或3D关键点估算的-convex优化。我们的第一个贡献是开发PACE3D*和PACE2D*，这是第一个使用3D和2D关键点进行姿势和形状估计的最佳最佳求解器。这两个求解器都依赖于紧密（即精确）半决赛的设计。我们的第二个贡献是开发两个求解器的异常刺激版本，命名为PACE3D＃和PACE2D＃。为了实现这一目标，我们提出了Robin，Robin是一种一般的图理论框架来修剪异常值，该框架使用兼容性超图来建模测量的兼容性。我们表明，在类别级别的感知问题中，这些超图可以是通过关键点（以2D）或其凸壳（以3D为单位）构建的，并且可以通过最大的超级计算来修剪许多异常值。最后的贡献是广泛的实验评估。除了在模拟数据集和Pascal数据集上提供消融研究外，我们还将求解器与深关键点检测器相结合，并证明PACE3D＃在Apolloscape数据集中在车辆姿势估算中改进了最新技术，并且其运行时间是兼容的使用实际应用。