Inconsistency Probability of Sparse Equations over F2
This work addresses theoretical properties of sparse equations relevant to SAT solving and cryptanalysis, but it appears incremental as it builds on known methods like inclusion-exclusion for specific graph structures.
The paper studies the inconsistency probability of randomly generated sparse polynomial systems over the binary field, showing it depends on hypergraph structure and deriving bounds and asymptotics, with explicit formulas for specific cases like paths and stars.
Let n denote the number of variables and m the number of equations in a sparse polynomial system over the binary field. We study the inconsistency probability of randomly generated sparse polynomial systems over the binary field, where each equation depends on at most k variables and the number of variables grows. Associating the system with a hypergraph, we show that the inconsistency probability depends strongly on structural properties of this hypergraph, not only on n,m, and k. Using inclusion--exclusion, we derive general bounds and obtain tight asymptotics for complete k-uniform hypergraphs. In the 2-sparse case, we provide explicit formulas for paths and stars, characterize extremal trees and forests, and conjecture a formula for cycles. These results have implications for SAT solving and cryptanalysis.