All reports by Author Santhoshini Velusamy:

__
TR22-100
| 14th July 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming complexity of CSPs with randomly ordered constraints

__
TR22-068
| 5th May 2022
__

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy#### Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

__
TR21-086
| 22nd June 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy#### Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

__
TR21-064
| 5th May 2021
__

Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming approximation resistance of every ordering CSP

Revisions: 2

__
TR21-063
| 3rd May 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 4
,
Comments: 1

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of DICUT requires $\Omega(\sqrt{n})$ space with ... more >>>

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

Noah Singer, Madhu Sudan, Santhoshini Velusamy

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>