8 citations · 8 across the 7 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of th…
cs.CC2018
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 (generalizing the notion of a matroid), which captures well-studied problems in several areas. These…