Showing 2026Show all
3 papers · 1 filter
cs.CC2026
Cores Characterize the One-Pass Streaming Complexity of CSPs
Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1
We study the one-pass streaming complexity of CSPs over a fixed finite relation under three natural objectives: , deciding whether all constraints can be satis…
cs.DS2026
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Amatya Sharma, Santhoshini Velusamy
Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems () that governs kerneli…
cs.DS2026
Characterizing Streaming Decidability of CSPs via Non-Redundancy
Amatya Sharma, Santhoshini Velusamy
We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language , that is, a fin…