Source author record

Karthik C. S.

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 Computational Geometry Computer Science and Game Theory Machine Learning math.MG

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On Communication Complexity of Fixed Point Computation

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from $[0,1]^n$ to $[0,1]^n$ , and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of $2^{Ω(n)}$ for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n/2}$ , and their goal is to find an approximate fixed point of the concatenation of the functions. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n}$ , and their goal is to find an approximate fixed point of the interpolation of the functions. We show a randomized communication complexity lower bound of $2^{Ω(n)}$ for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation $T$ of the $d$ -simplex is publicly known and one player is given a set $S_A\subset T$ and a coloring function from $S_A$ to $\{0,\ldots ,d/2\}$ , and the other player is given a set $S_B\subset T$ and a coloring function from $S_B$ to $\{d/2+1,\ldots ,d\}$ , such that $S_A\dot\cup S_B=T$ , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of $|T|^{Ω(1)}$ for the aforementioned problem as well (when $d$ is large).

preprint2020arXiv

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

preprint2020arXiv

On Efficient Low Distortion Ultrametric Embedding

A classic problem in unsupervised learning and data analysis is to find simpler and easy-to-visualize representations of the data that preserve its essential properties. A widely-used method to preserve the underlying hierarchical structure of the data while reducing its complexity is to find an embedding of the data into a tree or an ultrametric. The most popular algorithms for this task are the classic linkage algorithms (single, average, or complete). However, these methods on a data set of $n$ points in $Ω(\log n)$ dimensions exhibit a quite prohibitive running time of $Θ(n^2)$ . In this paper, we provide a new algorithm which takes as input a set of points $P$ in $\mathbb{R}^d$ , and for every $c\ge 1$ , runs in time $n^{1+\fracρ{c^2}}$ (for some universal constant $ρ>1$ ) to output an ultrametric $Δ$ such that for any two points $u,v$ in $P$ , we have $Δ(u,v)$ is within a multiplicative factor of $5c$ to the distance between $u$ and $v$ in the "best" ultrametric representation of $P$ . Here, the best ultrametric is the ultrametric $\tildeΔ$ that minimizes the maximum distance distortion with respect to the $\ell_2$ distance, namely that minimizes $\underset{u,v \in P}{\max}\ \frac{\tildeΔ(u,v)}{\|u-v\|_2}$ . We complement the above result by showing that under popular complexity theoretic assumptions, for every constant $\varepsilon>0$ , no algorithm with running time $n^{2-\varepsilon}$ can distinguish between inputs in $\ell_\infty$ -metric that admit isometric embedding and those that incur a distortion of $\frac{3}{2}$ . Finally, we present empirical evaluation on classic machine learning datasets and show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.

preprint2020arXiv

On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes

In the $(k,h)$ -SetCover problem, we are given a collection $\mathcal{S}$ of sets over a universe $U$ , and the goal is to distinguish between the case that $\mathcal{S}$ contains $k$ sets which cover $U$ , from the case that at least $h$ sets in $\mathcal{S}$ are needed to cover $U$ . Lin (ICALP'19) recently showed a gap creating reduction from the $(k,k+1)$ -SetCover problem on universe of size $O_k(\log |\mathcal{S}|)$ to the $\left(k,\sqrt[k]{\frac{\log|\mathcal{S}|}{\log\log |\mathcal{S}|}}\cdot k\right)$ -SetCover problem on universe of size $|\mathcal{S}|$ . In this paper, we prove a more scalable version of his result: given any error correcting code $C$ over alphabet $[q]$ , rate $ρ$ , and relative distance $δ$ , we use $C$ to create a reduction from the $(k,k+1)$ -SetCover problem on universe $U$ to the $\left(k,\sqrt[2k]{\frac{2}{1-δ}}\right)$ -SetCover problem on universe of size $\frac{\log|\mathcal{S}|}ρ\cdot|U|^{q^k}$ . Lin established his result by composing the input SetCover instance (that has no gap) with a special threshold graph constructed from extremal combinatorial object called universal sets, resulting in a final SetCover instance with gap. Our reduction follows along the exact same lines, except that we generate the threshold graphs specified by Lin simply using the basic properties of the error correcting code $C$ . We use the same threshold graphs mentioned above to prove inapproximability results, under W[1] $\neq$ FPT and ETH, for the $k$ -MaxCover problem introduced by Chalermsook et al. (SICOMP'20). Our inapproximaiblity results match the bounds obtained by Karthik et al. (JACM'19), although their proof framework is very different, and involves generalization of the distributed PCP framework. Prior to this work, it was not clear how to adopt the proof strategy of Lin to prove inapproximability results for $k$ -MaxCover.

preprint2016arXiv

Building Efficient and Compact Data Structures for Simplicial Complexes

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree (MxST) and the Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.

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.

Karthik C. S.

Research overview

Is this your work?

5 publications

On Communication Complexity of Fixed Point Computation

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

On Efficient Low Distortion Ultrametric Embedding

On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes

Building Efficient and Compact Data Structures for Simplicial Complexes

See the researcher in context

Building this map preview