BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Syamantak Das contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In this note, we observe that $X\in (GC)$ if $X$ admits Chebyshev center for any finite set in it. This answers the problem raised by Veselý, addressed in [{\em Generalized centers of finite sets in Banach spaces}, Acta Math. Univ. Comenian. (N.S.) {\bf 66}(1) (1997), 83--115]. We extend our observation towards the fact that the property $(GC)$ is not a 3-space property.
In this paper, we initiate the study of fair clustering that ensures distributional similarity among similar individuals. In response to improving fairness in machine learning, recent papers have investigated fairness in clustering algorithms and have focused on the paradigm of statistical parity/group fairness. These efforts attempt to minimize bias against some protected groups in the population. However, to the best of our knowledge, the alternative viewpoint of individual fairness, introduced by Dwork et al. (ITCS 2012) in the context of classification, has not been considered for clustering so far. Similar to Dwork et al., we adopt the individual fairness notion which mandates that similar individuals should be treated similarly for clustering problems. We use the notion of $f$-divergence as a measure of statistical similarity that significantly generalizes the ones used by Dwork et al. We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers. The objective is to ensure (a) low cost of clustering in expectation and (b) individuals that are close to each other in a given fairness space are mapped to statistically similar distributions. We provide an algorithm for clustering with $p$-norm objective ($k$-center, $k$-means are special cases) and individual fairness constraints with provable approximation guarantee. We extend this framework to include both group fairness and individual fairness inside the protected groups. Finally, we observe conditions under which individual fairness implies group fairness. We present extensive experimental evidence that justifies the effectiveness of our approach.
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+ε)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(c\log n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k \cdot O(c)^{2c}$ edges in time $mc^{O(c)}\log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
Given a graph $G=(V,E)$, capacities $w(e)$ on edges, and a subset of terminals $\mathcal{T} \subseteq V: |\mathcal{T}| = k$, a mimicking network for $(G,\mathcal{T})$ is a graph $(H,w')$ that contains copies of $\mathcal{T}$ and preserves the value of minimum cuts separating any subset $A, B \subseteq \mathcal{T}$ of terminals. Mimicking networks of size $2^{2^k}$ are known to exist and can be constructed algorithmically, while the best known lower bound is $2^{Ω(k)}$; therefore, an exponential size is required if one aims at preserving cuts exactly. In this paper, we study mimicking networks that preserve connectivity of the graph exactly up to the value of $c$, where $c$ is a parameter. This notion of mimicking network is sufficient for some applications, as we will elaborate. We first show that a mimicking of size $3^c \cdot k$ exists, that is, we can preserve cuts with small capacity using a network of size linear in $k$. Next, we show an algorithm that finds such a mimicking network in time $2^{O(c^2)} \operatorname{poly}(m)$.