BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Karthik C. S.

Karthik C. S. contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityData Structures and AlgorithmsComputational GeometryComputer Science and Game TheoryMachine Learningmath.MG

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

4 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