Source author record

Santhoshini Velusamy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Computer Science and Game Theory math.NT

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $Θ(q)$ -approximation, even when restricted to instances that are the intersection of $q$ partition matroids, and with i.i.d.~Bernoulli random variables. The previous best-known lower bound is $Θ(\sqrt{q})$ due to a simple construction of [Kleinberg-Weinberg STOC 2012] (which uses i.i.d.~Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of $q^{1/2+Ω(1/\log \log q)}$ by writing the construction of [Kleinberg-Weinberg STOC 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with $p^p$ disjoint cliques of size $p$ , using recent techniques developed in [Alon-Alweiss European Journal of Combinatorics 2020].

preprint2022arXiv

Approximability of all Boolean CSPs with linear sketches

In this work we consider the approximability of $\textsf{Max-CSP}(f)$ in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given $f$ , $γ$ and $β$ we show that either (1) the $(γ,β)$ -approximation version of $\textsf{Max-CSP}(f)$ has a linear sketching algorithm using $O(\log n)$ space, or (2) for every $ε> 0$ the $(γ-ε,β+ε)$ -approximation version of $\textsf{Max-CSP}(f)$ requires $Ω(\sqrt{n})$ space for any sketching algorithm. We also prove lower bounds against streaming algorithms for several CSPs. In particular, we recover the streaming dichotomy of [CGV20] for $k=2$ and show streaming approximation resistance of all CSPs for which $f^{-1}(1)$ supports a distribution with uniform marginals. Our positive results show wider applicability of bias-based algorithms used previously by [GVV17] and [CGV20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [KKS15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.

preprint2022arXiv

Sketching Approximability of (Weak) Monarchy Predicates

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 variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every $k \geq 5$ , we show that CSPs where the underlying predicate is a pure monarchy function on $k$ variables have no non-trivial sketching approximation algorithm in $o(\sqrt{n})$ space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by $O(\log(n))$ space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.

preprint2021arXiv

Elementary analysis of isolated zeroes of a polynomial system

Wooley ({\em J. Number Theory}, 1996) gave an elementary proof of a Bezout like theorem allowing one to count the number of isolated integer roots of a system of polynomial equations modulo some prime power. In this article, we adapt the proof to a slightly different setting. Specifically, we consider polynomials with coefficients from a polynomial ring $\mathbb{F}[t]$ for an arbitrary field $\mathbb{F}$ and give an upper bound on the number of isolated roots modulo $t^s$ for an arbitrary positive integer $s$ . In particular, using $s=1$ , we can bound the number of isolated roots of a system of polynomials over an arbitrary field $\mathbb{F}$ .

preprint2021arXiv

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant $α$ , s.t. for any $ε>0$ (i) there is an $(α-ε)$ -streaming approximation using space $O(\log{n})$ ; and (ii) any $(α+ε)$ -streaming approximation requires space $Ω(\sqrt{n})$ . This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was $1/2$ . Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DCUT problem, there was a gap between an upper bound of $1/2$ and a lower bound of $2/5$ [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DCUT is $4/9$ . We also establish that the tight approximation for Max-2SAT is $\sqrt{2}/2$ , and for Exact Max-2SAT it is $3/4$ . As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for \mksat{} is $\sqrt{2}/2$ for every $k\geq2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Santhoshini Velusamy

Research overview

Is this your work?

5 publications

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

Approximability of all Boolean CSPs with linear sketches

Sketching Approximability of (Weak) Monarchy Predicates

Elementary analysis of isolated zeroes of a polynomial system

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT

See the researcher in context

Building this map preview