Skip to content

Author

Santhoshini Velusamy

4 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Nov 2026

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $\Gamma$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is de...

Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy · 0 citations
Preprint Nov 2026

XOR-Functions and Beyond in the Random Query Model

We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model. On input $x$, a branching program receives independent samples $(i,x(i))$, where $i$ is uniform in $[n]$. We want to evaluate $f(x)$ while minimizing the width $2^S$ and the length $T$ of the branching pr...

Sumegha Garg, J. Sundaresan, Santhoshini Velusamy · 0 citations
Preprint Oct 2026

Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs

We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algorithms equipped with an $\varepsilon$-accurate oracle: for each variable, the oracle outputs a label in $\{-1,1\}$ that agrees with a fixed op...

Yin-Hao Dong, Pan Peng, A. Vakilian et al. · 0 citations
Preprint Oct 2026

Cores Characterize the One-Pass Streaming Complexity of CSPs

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly...

Joshua Brakensiek, Aaron L. Putterman, Amatya Sharma et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.