我们证明了最短s-t路径问题在以下两种情况下具有overlap-gap性质：(i)稀疏𝐆(n,p)图和(ii)具有独立同分布指数边权的完全图中。此外，我们证明了在稀疏𝐆(n,p)图中，最短路径可以通过O(log n)次多项式估计器求解，并且可以在多项式时间内采样一个均匀近似的最短路径。这是第一个例子表明，对于(非代数)平均情况优化问题，overlap-gap性质并不能预测算法难解性。
本文通过考察Hella（Ann. Pure Appl. Log., 1989）层次结构中第二Ehrenfeucht–Fraïssé双射鹅卵石游戏的力量，探索了有限群的描述复杂性理论。这是一个Spoiler–Duplicator游戏，其中Spoiler每轮可以放置最多两个鹅卵石。虽然它平凡地解决了图同构问题，但对于有限群和其他三元关系结构来说，它可能是非平凡的。我们首先提供了一个Weisfeiler–Leman（WL）着色的新颖推广，我们称之为2-ary WL。然后我们展示了2-ary WL等同于Hella层次结构中的第二Ehrenfeucht–Fraïssé双射鹅卵石游戏。我们的主要结果是，在鹅卵石游戏的特征描述中，仅需O(1)鹅卵石和O(1)轮就足以识别所有无阿贝尔正规子群的群（一类已知同构测试在𝖯中的群；Babai, Codenotti, Qiao, ICALP 2012）。实际上，我们展示了7个鹅卵石和7轮就足够了。特别是，我们展示了在前几轮中，Spoiler可以迫使Duplicator在每轮后续中选择两个这样的群之间的同构。根据Hella的结果（ibid.），这等同于说这些群是由具有广义2-ary量词的一阶逻辑公式识别的，仅使用7个变量和量词深度7。
边-测地集在网络监控和优化中扮演着关键角色，其目标是在网络的顶点上策略性地放置监控站，以确保边的完全覆盖并通过监控通信线路来减轻故障。本文阐述并探讨了监控边-测地集（MEG-set）问题，该问题涉及确定需要监控的最小顶点集以实现给定网络的测地覆盖。这一问题的重要性在于其促进高效网络监控的潜力，从而增强各种应用的整体可靠性和性能。在这项工作中，我们通过从著名的顶点覆盖问题展示一个归约，证明了MEG-set优化问题的𝒩𝒫-完全性。此外，我们提出了不可近似性结果，证明MEG-set优化问题是𝒜𝒫𝒳-难的，并且如果唯一游戏猜想成立，该问题对于任何常数ϵ > 0都不能在2-ϵ的因子内近似。尽管其𝒩𝒫-难度，我们基于著名的集合覆盖近似算法，提出了一个高效的近似算法，对于MEG-set优化问题实现了O(√(|V(G)| ·ln|V(G)|))的近似比，其中|V(G)|是MEG-set实例的节点数。
给定一个图G、一个整数k≥ 0以及一个非负整数函数f:V(G) →𝒩，向量支配问题询问是否存在一个顶点集S，其基数不超过k，使得每个顶点v ∈ V(G)∖ S在S中至少有f(v)个邻居。该问题推广了多种支配问题，并且已被证明可以推广有界度顶点删除问题（BDVD）。本文研究了当输入图为平面图时，向量支配问题的参数化版本。我们提出了一个线性问题核。一个直接的推论是BDVD的核边界仅与参数k呈线性关系。此前已知的边界是目标度数和输入参数的函数。
我们证明具有边界 γ_2 规范或边界归一化痕量规范的布尔矩阵必须包含线性大小的 all-one 或 all-zeros submatrix,验证 Hambardzumyan、Hatami 和 Hatami 的猜想。 我们还介绍了关于边界 γ_2 规范布尔矩阵的进一步结构结果,并讨论了通信复杂性、运算理论、光谱图论和极端组合中的应用。 作为一个关键的应用,我们为MaxCut建立了一个逆定理。 Edwards的一个著名结果指出,每个具有m边缘的图形G都有至少m/2+√(8m+1)-1/8的尺寸,通过具有奇数顶点的完整图形来实现平等。 为了与此形成对比,我们证明,如果G的MaxCut最多为m/2+O(√(m),那么G必须包含一个大小为Ω(√(m)的组)。
我们表明,两个单变量多项式可以通过(按片次)在任何足够大场上恒定深度和多项式大小的代数电路计算,无论特征如何。 这延续了Andrews Wigderson最近的结果,他在零或大特征的字段上显示了这样的上限。 我们的证明是基于Bhttacharjee,Kumar,Rai,Ramanathan,Saptharishi和Saraf最近的工作,该研究表明在保理下关闭恒定深度代数电路。 在我们进行证明的过程中,我们表明任何具有小常数深度代数电路的n-variate对称多项式P都可以写成具有基本对称多项式的小常数深度代数电路的组成。 这种说法是Bläser Jindal结果的恒定深度版本,他展示了无边界深度的代数电路。 作为我们技术的应用,我们还加强了Bhtacharjee等人在小特征领域工作中恒定深度电路因子的闭合结果。
参数化本地搜索将经典的本地搜索后导与参数化算法的范式相结合。 虽然大多数本地搜索算法旨在通过在给定的解决方案上执行单个操作来改进给定的解决方案,但参数化方法旨在通过执行k同时操作来改善解决方案。 在这里,k 是一个称为搜索半径的参数,用户可以选择该值。 参数化本地搜索领域的一个主要目标是概述 k 的大小与本地搜索步骤的运行时间之间的权衡。 在这项工作中,我们引入了一个抽象框架,该框架将自然参数化的本地搜索方法用于一大类分区问题:给定被分割成 b bin 的 n 项和评估当前分区质量的目标函数,请询问是否有可能通过从当前垃圾箱中删除多达 k 项并将其重新分配到其他 bin 来改进解决方案。 除其他外,我们的框架适用于集群编辑、矢量绑定和纳什社会福利等问题的本地搜索版本。 受问题矢量Bin Packing的现实应用激励,我们引入了一个称为类型数的参数τ≤n,并表明我们框架中拟合的所有问题都可以在 τ^k 2^O(k) |I|^O(1) 的时间内解决,其中|I|表示总输入大小。 在群集编辑的情况下,参数τ概括了输入图中众所周知的参数邻域多样性。 我们通过表明,对于所有考虑的问题,一个算法显着改进我们的算法与运行时间 τ^k 2^O(k) |I|^O(1) 相矛盾,这将与ETH相矛盾。 此外,我们表明,即使在非常有限的实例中,当仅通过搜索半径 k 参数化时,所有考虑的问题都是 W[1]-hard。
字符串重复性度量c的最坏情况的加法灵敏度被定义为c(w)和c(w')之间最大的差异,其中w是长度n的字符串,w'是一个字符串,可以通过在w上执行单字符编辑操作获得。 我们呈现 O(√(n)) 上限,用于最小字符串吸引器大小 γ 和最小双向方案大小 b 的最坏情况的加法灵敏度,该边界与 γ 和 b [Akagi 等人) 的已知下限 Ω(√(n) 匹配。 2023年]。 此外,我们针对LZPS和LZ-End的LZel-Ziv家族的最坏添加剂灵敏度提供了匹配的上下边界,以及LZ78的Θ(n)。
在这项工作中,我们研究计算两个顶点标记图的最大共同收缩的问题,即如何通过在两个图形中尽可能小的边缘来使它们完全相同。 我们从参数化的复杂性角度研究这个问题,使用参数,如最大度,退化,输入图的斜带宽或树width以及允许的收缩次数。 我们将这种复杂性与标记的可收缩性问题(即确定标记图是否是另一个的收缩图)进行透视。 令人惊讶的是,我们的研究结果表明这些问题在参数化复杂度状态方面的差异很小。 我们只证明它们的状态在通过退行性和允许收缩的数量进行参数化时有所不同,在这种情况下显示最大常见收缩问题的W[1]-硬度,而可收缩性问题是FPT。
作为原始操作执行小矩阵乘法的专用计算单元通常存在于现代加速器中。 然而,除了密集的矩阵乘法之外,这些单元通常未用于许多基本操作。 由于缺乏严格的计算理论模型来捕捉它们的特性,这些算法的分析目前停滞不前。 在这项工作中,我们提出了MMV-RAM,一种针对矩阵乘法加速器定制的计算模型。 MMV-RAM明智地扩展了Vector-RAM模型,增加了一个处理单元,该单元将两个大小为n× s和s×的矩阵在单个并行步骤中乘以,其中s是模型参数。 我们提供模型的详细理论分析,并仔细平衡矩阵和向量单元之间的计算能力,由电路复杂度下界引导,奇偶校验不在AC[0]。 在MMV-RAM中,我们研究分段扫描和和和的算法,两个基本的并行原语。 我们提出了一个分段扫描算法,它使用矩阵乘法来执行推测的块扫描计算,该计算以 O(log_s(n)) 步骤运行。 相比之下,我们表明任何仅使用MV-RAM的矢量单元的算法都需要Ω(log_2(n)/log_2log_2(n))步骤。 我们进一步应用这些技术来获得类似的理论加速元素向矢量乘法和矩阵乘法。 除了最坏情况的复杂性分析之外,我们还提出了分割操作的算法,这些算法可以带来高效和务实的实现。 例如,我们观察到分段和是三个基本并行原语的组合:扫描,压缩和向量分化。 作为案例研究,我们实施...
在本文中,我们提供了一个统一的框架,用于通过普通微分方程(ODE)的镜头调查小电路类和边界。 遵循最近引入的方法,通过基于ODE的递归模式捕获多项式时间可计算函数的类别,然后应用于由恒定深度的无界风扇电路(FAC^0)计算的功能上下文,我们研究了多个相关的小电路类。 特别是,我们表明,线性度和推导的自然限制以及具有特定增长率的函数对应于可以证明为各种类别的函数,从FAC^0到FAC^1。 这揭示了线性长度ODE和电路计算的限制之间的有趣联系,提供了新的工具来解决在电路层次结构中为类建立边界的复杂挑战,并可能增强我们对计数器在这个设置中的作用的理解。 此外,我们建立了几个完整性结果,特别是获得了第一个基于ODE的表征,这些函数的类可以连续深度与无边界风扇入和Mod 2门(FACC[2])和具有边界扇形布尔门(FNC1)的对数深度计算。
在大型网络中,我们希望选择一些有影响力的节点,通过在有限的预算内支付一些成本来赚取利润,这样我们就不必在选定的节点附近的一些节点上花费更多的预算;我们的问题是它的图形理论表示。 我们通过在图形上附加 Knapsack Problem with Dominating Set 来定义我们的问题。 每个顶点都与成本因素和利润金额相关联。 我们的目标是在固定预算内选择一些顶点,提供最大的利润,这样我们就不需要选择他们的1跳邻居。 我们表明,即使在仅限于Bipartite图形时,Domination Set Knapsack问题也是强烈的NP-complete,但对于Star图形来说,NP-complete弱。 我们为时间 O(n· min{s^2, (α(V))^2} 的树提出了一个伪多项式时间算法。 我们通过证明它位于 W[2]-hard 参数化由解决方案大小表示的 W[2]-hard 参数化,表明 Dominating Set Knapsack 不太可能是固定参数(FPT)。 我们开发了具有运行时间 O(4^tw· n^O(1)· min{s^2,α(V)^2})和 O(2^vck-1· n^O(1)· min{s^2,α(V)^2}的 FPT 算法,其中 tw 代表给定图形的树梢,vck 是 Vertex Cover Knapsack 的求解大小, s 是 knapsack 和 α(V)=∑_v∈ Vα(v) 的大小。
我们表明,代数公式和恒定深度电路在考虑因素下是封闭的。 换句话说,我们表明,如果一个特征零场上的多变量多项式具有小的恒定深度电路或公式,那么它的所有因子都可以分别通过小常数深度电路或公式计算。 我们的结果被证明是20世纪60年代Furstenberg的一个基本和令人惊讶的结果,它给出了双变量多项式的力量系列根源的非迭代描述。 结合代数复杂性的标准结构思想,我们观察到这个定理产生所需的闭包结果。 作为应用程序,我们获得了各种已知结果的替代(也许更简单)的证明,并加强了其中一些结果的量化界限。 这包括对代数模型(电路,分支程序和VNP)已知闭包结果的统一证明,将Kaba内茨-Impagliazzo撞击集发生器的分析扩展到公式和恒定深度电路,以及(显着)更简单的正确性证明以及对亚指数时间确定性算法中的输出的更有力的保证,用于从Bhta的最近工作中对恒定深度电路进行因子化。
我们启动了对恒定成本随机通信的集中研究,重点是它与图形表示的连接。 我们观察到,恒定成本的随机通信问题相当于遗传(即接受诱导子图下关闭)图形类,这些类允许常量相邻草图和概率通用图形(PUG),它们是经过良好研究的邻接标记方案和诱导通用图形的随机版本。 这为关于这些对象存在的长期问题提供了新的视角,包括构建相邻标签方案的新方法。 我们问三个主要的问题关于恒定成本通信,或等价的,恒定大小的PUGs:(1)除了平等和k-Hamming距离之外,是否有任何自然,非平凡的问题,具有恒定成本的通信? 我们提供了许多新示例,包括决定两个顶点是否在平面图中最多为 k 的路径距离,并显示笛卡尔产品操作保存了恒定大小的 PUG。 (2)什么结构的问题解释了恒定成本协议的存在或不存在? 我们表明,在许多情况下,大比子问题就是这样一个结构。 (3)平等问题是否完整用于持续成本的随机通信? 我们表明,它不是:存在不断的成本问题,不会降低平等。
寻找稀疏向量是一个基本问题,它出现在几个上下文中,包括代码,子空间和格子。 在这项工作中,我们使用一种甚至绕过PCP定理的新方法证明了所有这些变体的强近似结果。 我们的主要结果是,在任何恒定因子内近似真实子空间中最稀疏的向量是NP-hard(在随机还原下);使用加法可以进一步放大间隙。 我们的还原具有在完整性情况下存在布尔解决方案的属性。 作为推论,这立即恢复了晶格上最短向量问题(SVP)的最先进的不可拟性因素。 我们的证明扩展了以前已知的硬度的l_p(准)规范的范围,从p≥1到所有p≥0,回答了[Khot05]提出的问题。 SVP以前的硬度结果,以及纠错代码的相关最小距离问题(MDP),都使用格子/编码小工具,这些小工具的半径小于最小距离的球中具有丰富的编码词。 相比之下,我们的减少只需要半径略大于最小距离的球中的许多编码词。 这使我们对有限场的还原易于去随机化,为MDP提供了新的确定性硬度的基本证明。 我们认为,这种较弱的密度要求可能会提供一个有希望的方法来显示SVP的确定性硬度,这是一个长期难以实现的目标。 我们为真实子空间的结果背后的关键技术成分是一个证明,在随机的 Rademacher 矩阵的内核中,任何两个线性独立向量的支持几乎没有重叠。 这项工作背后的一个更广泛的动机是开发无法近似的技术,以解决现实问题。 我们希望我们开发的方法能够在稀疏向量的分析变体方面取得进展。
本文对闪电网络进行了正式分析,认为闪电网络是一个货币系统,在结构上与比特币的基础层结算模型不同。 我们证明,在不断增长的交易需求下,由于吞吐量限制,BTC交易费用超线性上升,而闪电网络路由成本接近边界无症状。 使用数学建模,游戏理论证明和复杂性分析,我们表明Lightning通过流动性中心寡头垄断的出现实现无限期的链外操作。 这些中心表现出不受监管的金融中介机构的特性,包括租金提取、不透明和系统性脆弱性。 战略代理模型表明,通道闭合在经济上变得不可行,路由问题在P-Space复杂性中接近硬度限制。 我们的结论是,Lightning不仅扩展了比特币,而且构成了一个具有影子银行特征的合成金融体系,缺乏储备纪律,透明度或可强制执行的结算担保。
我们研究二维沙堆模型中计时预测问题的计算复杂性。 这个问题完善了经典的预测问题,它询问一个单元格q在从给定配置的单元格 p 中添加一个粒后最终是否会变得不稳定。 预测问题在几个设置中被证明是P-complete,包括摩尔社区的子集,但它对冯诺依曼社区的复杂性仍然开放。 在之前的一项工作中,我们为这些小社区提供了交叉闸门(实现非平面单体电路的关键)的完整表征,导致8个相邻单元中只有4个和5个邻居的P完整性证明。 在本文中,我们介绍了时间设置,其中的目标是确定单元格q是否在时间t时变得不稳定。 我们区分了几个案例:一些社区支持完整的计时工具包(包括计时交叉门)并表现出P完整性;另一些社区承认计时交叉,但存在同步问题;平面社区可能不承认任何计时交叉;最后,对于一些剩余的社区,我们猜想没有计时交叉是可能的。
在证明复杂性生成器理论的激励下,我们考虑以下 Σ^p_2 搜索问题_P由命题证明系统P:给定一个分离的P-proof π ⋁_i α_i,没有两个α_i有一个原子的共同点,找到i这样的Σ^p_2 Σ^p_2 ,即α_i ∈。 我们提出了一个假设(ST),对于一些强大的证明系统P,问题 _P 在p-time学生和连续几轮的学生教师模型中无法解决。 该假设来自硬单向排列的存在。 我们使用模型理论假设证明(ST)意味着NP ≠ coNP。 该假设涉及有界算术理论模型的扩展的存在,如果它成立,它目前是开放的。
多项式因子化是计算代数的一个基本问题。 在过去的半个世纪里,已经开发了各种算法技术来解决这个问题的不同变体。 同时,代数复杂性理论根据它们感知的“硬度”将多项式分类为复杂性类。 这就提出了一个自然的问题:这些课程是否提供了有效的保理? 在这项调查中,我们重新审视了多项式因子化中的两项关键技术:Hensel提升和牛顿迭代。 虽然它们是同一主题的变体,但它们在文献中的独特应用需要单独处理。 这些技术在解决代数复杂性理论的关键保理问题方面发挥了重要作用。 我们通过这些技术的镜头检查和组织已知结果,以突出其影响。 我们还讨论了它们的等价性,同时反思它们的使用如何随问题的背景而变化。 我们专注于四个突出的复杂性类:多项式大小(VP_nb)电路,多项式大小和度(VP及其边界VP)的电路,多项式大小和度(VNP)的验证电路,以及多项式大小的代数分支程序(VBP)。 我们还研究了更受限制的模型,例如公式和边界深度电路。 在此过程中,我们列出了几个悬而未决的悬而未决的问题。
我们提供简单的确定性还原,证明在任意常数因子中近似最近的编码词问题和最小距离问题的NP硬度(假设NP不能在准多项式时间内解决的几乎多项式因素)。 起点是一个简单的NP-hardness结果,没有差距,因此是“无五氯苯酚”。 我们的方法受到Bhattiprolu和Lee [BL24]的启发,他们对整数和实数的类似问题进行了无PCP随机还原。 我们利用ε平衡代码的存在来解数,并进一步简化对有限字段的减少。
