Spanoids - an abstraction of spanning structures, and a barrier for LCCs

Zeev Dvir, Sivakanth Gopi, Yuzhou Gu +1

We introduce a simple logical inference structure we call a $\text{spanoid}$ (generalizing the notion of a matroid), which captures well-studied problems in several areas. These…