14 citations · 27 across the 20 of their papers we have counts for
5 papers · 1 filter
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Yinhao Dong, Pan Peng, Ali Vakilian +2
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algori…
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…
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…
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…
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
For an arbitrary family of predicates and any , we prove a single-pass, linear-space streaming lower bound against the gap promise pro…