10 papers
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 fi…
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
Santhoshini Velusamy
The Max-DICUT problem has gained a lot of attention in the streaming setting in recent years, and has so far served as a canonical problem for designing algorithms for general cons…
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 pr…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
Optimally detecting uniformly-distributed heavy hitters in data streams
Santhoshini Velusamy, Huacheng Yu
Given a stream of items from a Universe of size poly, and a parameter , an item is said to be an heavy hitter if its frequency…