论文标题
关于布尔函数的部分差分编码
On Partial Differential Encodings of Boolean Functions
论文作者
论文摘要
我们介绍了布尔函数的部分差分编码，以衡量布尔函数的复杂性。这些编码使我们能够从用于指定布尔函数的部分差分编码的多项式的Chow级的小组动作中得出。我们还介绍了称为部分差异程序的部分差分编码的变体。我们表明，这样的程序最佳地描述了包括决定因素和永久物质在内的多项式的重要家族。部分差分程序还可以量化这两个多项式家族。最后，我们源自受部分差分程序启发的多项式结构，这些构造在高阶超图异构态实例与它们的副同构对应物之间表现出无条件的指数分离。
We introduce partial differential encodings of Boolean functions as a way of measuring the complexity of Boolean functions. These encodings enable us to derive from group actions non-trivial bounds on the Chow-Rank of polynomials used to specify partial differential encodings of Boolean functions. We also introduce variants of partial differential encodings called partial differential programs. We show that such programs optimally describe important families of polynomials including determinants and permanents. Partial differential programs also enables to quantitively contrast these two families of polynomials. Finally we derive from polynomial constructions inspired by partial differential programs which exhibit an unconditional exponential separation between high order hypergraph isomorhism instances and their sub-isomorphism counterparts.
