Skip to content

Author

Amatya Sharma

2 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 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.