两个拟阵的公共基能否在多项式时间内近似计数？

FPRAS 用 (1±ε) 估计替代精确计数

两个拟阵 M 和 N 共享大小为 n 的地集 U，并具有相同的秩 r。它们的基是极大独立集，所关注的量是 |B(M) ∩ B(N)|，即同时为两者基的集合个数。论文的定理 1.2 指出，对该计数存在一个 FPRAS：给定 M 和 N 的独立集预言机以及精度参数 0 < ε ≤ 1，它以至少 3/4 的概率返回满足 (1−ε)·Z ≤ Ẑ ≤ (1+ε)·Z 的估计 Ẑ，运行时间关于实例规模和 1/ε 是多项式的。

该保证是乘性的，而非加性的，并且是随机的。论文指出，在预言机模型中随机性是必要的：即使对单个拟阵，也不存在高效确定性算法能在单纯指数级乘性因子内近似 |B(M)|。同一定理还给出多项式时间算法，用于近似均匀地采样一个公共基，因为所考虑的问题在 Jerrum、Valiant 和 Vazirani 的意义下是自可归约的，使得近似计数与近似采样在多项式时间归约下等价。

运行时间为 Õ(n^13/ε^2)。作者明确指出这不是最优的，他们没有尝试优化它，而是选择尽可能简单地呈现算法和证明。这对理解该结果很重要：其贡献是多项式时间可行性，而不是有竞争力的常数或指数。

公共基比单个拟阵的基更难

单个拟阵的基的计数与采样已有多项式时间算法，由 Anari、Liu、Oveis Gharan 和 Vinzant 给出。二分图完美匹配这一情形，即两个划分拟阵的交，此前已由 Jerrum、Sinclair 和 Vigoda 解决，他们得到了非负矩阵永久值的首个 FPRAS。新结果覆盖的是两个拟阵的一般交，而非这些特殊类。

论文对一般情形为何此前难以处理给出了具体说明。对于按 λ^|S| 加权的、包含所有大小的公共独立集上的分布，存在简单的拟阵对例子，其谱独立参数为 Ω(poly(n))；作者引用了一个长度为 Θ(n^1/3) 的偶环，在 λ = 1 时每条边替换为 Θ(n^2/3) 条平行边，该二分图的匹配恰好是两个划分拟阵的公共独立集。构造具有多项式拥挤度的规范路径或流也被认为一般是困难的。因此障碍不是缺少优化，而是标准混合证明的失效。

软交把硬约束替换为重叠惩罚

第一个要素放松了交。算法不要求满足 T = U \ S 的对 (S, T)，而是使用由两个输入测度构成的乘积测度，并加入由参数 t 控制的重叠惩罚。由此得到的“软交”测度就是被分析混合性质的対象。

论文证明，该软交满足一个对所有外部场一致成立的 Poincaré 不等式，所用方法是一种积分型 Bochner 方法，通过拉普拉斯算子的平方来界定其谱隙。对所有场一致这一陈述使算法其余部分成为可能：无论优化步骤之后选择哪个外部场，同一混合保证都成立。

这种放松并非没有代价。硬约束 T = U \ S 只在软测度下以高概率被恢复，因此算法还必须证明该概率很大。这是第二个要素的任务。

外部场由对偶最大熵规划选出

第二个要素求解一个对偶最大熵凸规划，以计算在软交测度下使硬约束以高概率成立的外部场。成功概率直接由一致 Poincaré 不等式以及梯度范数的小性来界定。

具体而言，论文把任务归约为寻找一个使 ∇Φ(log z) 很小的场 z，其中 Φ 是凸的且逐坐标 1-光滑，并应用随机坐标下降。推论 5.12 指出，给定两个测度的值预言机、它们的系数范围 R_μ 和 R_ν，以及一个被支持的配对 (S_0, T_0)，一个随机算法返回这样的场或报告失败；若目标计数 Z_∩ 为正，它以至少 31/32 的概率成功，并返回满足 π_{t,z}(T = U \ S) ≥ 1/2 的场，使用 O(n^10 B^2 log(2B)) 次算术运算和预言机调用，其中 B = 2n + ⌈log_2(R_μ R_ν)⌉。

这正是该方法与退火传统不同之处。Jerrum、Sinclair 和 Vigoda 及其后续工作的永久值算法沿精心设计的退火路径学习修正权重；这里则通过随机梯度下降直接选择场。作者将其呈现为一个黑箱，一旦采样和一致 Poincaré 假设得到验证，便可服务于一大类计数问题。

计数由两个分别估计的因子组装而成

一旦固定了好的场，目标量就被分解为 Z_∩ = (Z_{t,z} / z^U) × π_{t,z}(T = U \ S)。第一个因子是归一化常数，通过对配对 (S, T) 的 2n 个隶属位应用 Jerrum、Valiant 和 Vazirani 的从采样到计数的标准归约来估计；第二个因子是采样到的配对为互补对的概率，通过抽取配对并取经验比例来估计。

两个估计的相对误差至多为 β = ε/4，它们所需的条件以至少 1 − 4δ_0 > 3/4 的概率同时成立，从而给出 (1−β)^2 ≤ Ẑ_∩/Z_∩ ≤ (1+β)^2，因此相对误差为 ε。若 Z_∩ = 0，每个被支持的配对都无法通过互补对检验，因此每次执行都返回零，要么在找场步骤，要么因为经验互补比例为零。

运行时间的核算很明确。找场花费 O(n^10 B^2 log(2B))；系数范围在自归约过程中不增加；每个受限预言机使用一次原始查询加上 O(n) 次操作；在 t^{-1} = 256n^2 时，一次条件采样的代价为 O(n^5 (n^2 B + log(n/ε)))。自归约使用 O(n^3 ε^{-2} log(2n)) 个样本，估计互补对概率又需要 O(ε^{-2}) 个。由于 B = Θ(n + log(R_μ R_ν))，总计为 O(n^10 B^2 ε^{-2} log^2(2B/ε))。

同一套机制可计数弯曲测度的 Hadamard 积

拟阵结果是关于子集卷积的一个更一般陈述的特例。对于 U 的子集上的非负权重函数 μ 和 ν，子集卷积为 (μ∗ν)(T) = Σ_{S⊆T} μ(S)·ν(T\S)，即两个多仿射生成多项式之积中 x^T 的系数。定理 1.6 对任意指定系数 Z_α = [x^α](g_μ(x)·g_ν(x))（α ∈ {0,1,2}^U）给出 FPRAS，假设 g_μ 和 g_ν 是对数凹的，使用 Õ(n^11·(n + log(R_μ·R_ν))^2 / ε^2) 次算术运算和求值预言机调用。

定理 1.2 通过令 μ(S) = 1[S ∈ B(M)] 和 ν(T) = 1[U \ T ∈ B(N)] 得到，两者都可由独立集预言机求值；两个生成多项式的对数凹性已在先前工作中建立，初始集合可通过贪心算法找到。论文还发展了一个 Hadamard 积表述，其中 (μ ⊙ ν)(S) ∝ μ(S)·ν(S) 定义在公共支撑上，并在输入测度满足 κ-谱曲率条件时，证明了相关逐坐标拉普拉斯算子的 Poincaré 不等式。

定理 1.6 的三个进一步应用被特别强调，因为它们不能直接由拟阵陈述涵盖：半正定矩阵的混合判别式，论文称这否证了此前关于 FPRAS 不存在的猜想；无环 4-正则多重图上的六顶点模型，当非负权重满足 a ≤ b+c、b ≤ a+c 和 c ≤ a+b 时，对正权重而言这补全了此前遗留的一般图近似分类；以及二分图上的 Quantum Max-Cut 连同任意图上带非负边权的 EPR 模型。拟阵定理还给出计数强定向和无向欧拉回路的 FPRAS，其加权变体适用于网络可靠性，包括有向根到全可达性以及两个终端集之间无配对顶点不相交连接。

多项式时间是结论，而非实际速度

该结果针对以独立集预言机给出的拟阵，每次预言机调用计为单位代价。运行时间依赖于系数范围 R_μ 和 R_ν，算法需要 R_μ, R_ν ≤ exp(poly(n)) 才能保证多项式时间；论文指出这在大多数关注的应用中很容易满足，并且可以使用用户提供的上界替代，运行时间界中作同样替换。公共基的 Õ(n^13/ε^2) 界被明确描述为非最优。

论文对思路的形成过程也很透明。致谢指出 GPT-5.6 Sol Ultra 和 GPT-6 Astra Ultra 被大量使用，作者提供了许多高层方向，同时强调 AI 贡献对该项目的成功至关重要，并且项目始于一个更 modest 的问题，即对所有大小的公共独立集上的 Glauber 动力学的快速混合，之后才扩展到公共基。这是关于过程的披露，而非对数学结论的限定，但它是作者选择纳入记录的一部分。

决定性转变是从特殊情形到预言机给出的拟阵对

阅读这篇论文最有用的方式，是把它看作对“什么算一般情形”的改变。在此之前，多项式时间计数与采样可用于单个拟阵的基，以及二分图完美匹配，即两个划分拟阵的交；而仅由独立集预言机给出的两个拟阵的一般交没有多项式时间近似。论文以随机 (1±ε) 倍乘性保证填补了这一空白，并且同一证明模板扩展到对数凹测度的子集卷积，以及满足非负曲率条件的测度的 Hadamard 积。

需要记住的实际门槛是黑箱所需的两条假设：相关测度的采样过程，以及一致 Poincaré 不等式。在能够验证这些的地方，找场步骤和从采样到计数的归约可按所述应用；在不能验证的地方，拟阵定理本身并不提供算法。n^13 的指数以及对 log(R_μ R_ν) 的依赖是这种一般性的代价，作者将其呈现为一个起点，而非已完成的复杂度。

本文引用的文献