BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Karthik C. S.

Karthik C. S. appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityData Structures and AlgorithmsComputational GeometryComputer Science and Game TheoryMachine Learningmath.MG

Catalog footprint

What is connected

5works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

5 published item(s)

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

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access