Traditional clustering methods assume that precise pairwise distances for the input data are readily available. However, this assumption is often impractical in real-world scenarios where data points cannot be measured accurately. For instance, machine learning-based techniques for estimating distances may fail when the dataset consists of images, videos, or natural language. This paper studies clustering and graph problems in settings where direct access to pairwise distances between all pairs is expensive. We adopt oracle-based methods as defined by Galhotra et al. (2024), focusing on two types of oracles: the quadruplet oracle, a weak and inexpensive comparator that answers binary queries of the form "Is A closer to B or C closer to D?" and the distance oracle, a stronger but costlier oracle that returns exact pairwise distances. The quadruplet oracle can be implemented via crowdsourcing, trained classifiers, or other predictive models. As these sources are often unreliable, the oracle’s responses may be noisy; we consider both probabilistic and adversarial noise models. Consider a finite metric space $\Sigma=(\mathcal{V},d)$ of size $|\mathcal{V}|=n$ that supports the quadruplet and the distance oracle. When the input dataset has low intrinsic (doubling) dimension, for each of the $k$-center, $k$-median, and $k$-means clustering problem on $\mathcal{V}$, we design constant approximation algorithms that perform $\widetilde{O}(n+k^2)$ calls to the quadruplet oracle and $\widetilde{O}(1)$ calls to the distance oracle in both noise models. For general metric spaces, our algorithms achieve constant approximation while making $\widetilde{O}(nk)$ calls to the quadruplet oracle and $\widetilde{O}(1)$ calls to the distance oracle. In all cases, we improve the quadruplet oracle query complexity by a factor of $k$ and the distance oracle call complexity by a factor of $k^2$ compared to Galhotra et al. (2024). Furthermore, in low dimensional settings, if the spread of the input data is polynomially bounded, we construct a data structure performing $\widetilde{O}(n)$ queries to the quadruplet oracle and $\widetilde{O}(1)$ queries to the distance oracle, such that given any query pair of vertices $(u,v)\in \mathcal{V}\times \mathcal{V}$, it approximates the distance $d(u,v)$ without using any oracle queries. Once the data structure is constructed, we can emulate standard algorithms for various graph problems on $\Sigma$ without additional oracle queries. In summary, our results show that access to a noisy pairwise ranker for distances is to sufficient to efficiently solve a large class of problems while almost entirely bypassing exact distance computations.

The potential harms of algorithmic decisions have ignited algorithmic fairness as a central topic in computer science. One of the fundamental problems in computer science is Set Cover, which has numerous applications with societal impacts, such as assembling a small team of individuals that collectively satisfy a range of expertise requirements. However, despite its broad application spectrum and significant potential impact, set cover has yet to be studied through the lens of fairness.

Effective data discovery is a cornerstone of modern data-driven decision-making. Yet, identifying datasets with specific distributional characteristics, such as percentiles or preferences, remains challenging. While recent proposals have enabled users to search based on percentile predicates, much of the research in data discovery relies on heuristic methods, which often result in biased outcomes. This paper presents the first theoretically backed framework that unifies data discovery under centralized and decentralized settings. More specifically, let P ={P 1 ,..., P N } be a repository of N datasets, such that each P i ⊂ ℝ d , where d is a constant. We study the percentile-aware indexing (Ptile) problem and the preference-aware indexing (Pref) problem under the centralized and the federated setting. In the centralized setting, we assume direct access to the datasets in P . In the federated setting we are given a synopsis S P i which is a compressed representation of P i that captures the structure of P i , for every i ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query rectangle R and an interval θ) report all indexes J such that j ∈ J if and only if |P j ∩ R|/|P j | ∈ [N]. For the Ptile problem, the goal is to construct a data structure such that given a predicate (query vector v → and an interval θ) report all indexes J such that j ∈ J if and only if ω k (P j ,v → )∈ θ, where ω k (p j ,v → ) is the score (inner-product) of the k -th largest projection of P j on v → . We first show lower bounds for the Ptile and Pref problems in the centralized setting, showing that we cannot hope for near-linear data structures with polylogarithmic query time. Then we focus on approximate data structures for both problems in both settings. We show Ø(N) space data structures with Ø(N) preprocessing time, that can answer Ptile and Pref queries in Ø(1+OUT) time, where OUT is the output size. The data structures return a set of indexes J such that: i) for every P i that satisfies the predicate, i ∈ J and ii) if j ∈ J then P j satisfies the predicate up to an additive error of ε+2δ, where ε is an arbitrarily small constant and δ is the error of the synopses.

We are given a set $\mathcal{Z}=\{(R_1,s_1),\ldots, (R_n,s_n)\}$, where each $R_i$ is a \emph{range} in $\Re^d$, such as rectangle or ball, and $s_i \in [0,1]$ denotes its \emph{selectivity}. The goal is to compute a small-size \emph{discrete data distribution} $\mathcal{D}=\{(q_1,w_1),\ldots, (q_m,w_m)\}$, where $q_j\in \Re^d$ and $w_j\in [0,1]$ for each $1\leq j\leq m$, and $\sum_{1\leq j\leq m}w_j= 1$, such that $\mathcal{D}$ is the most \emph{consistent} with $\mathcal{Z}$, i.e., $\mathrm{err}_p(\mathcal{D},\mathcal{Z})=\frac{1}{n}\sum_{i=1}^n\! \lvert{s_i-\sum_{j=1}^m w_j\cdot 1(q_j\in R_i)}\rvert^p$ is minimized. In a database setting, $\mathcal{Z}$ corresponds to a workload of range queries over some table, together with their observed selectivities (i.e., fraction of tuples returned), and $\mathcal{D}$ can be used as compact model for approximating the data distribution within the table without accessing the underlying contents. In this paper, we obtain both upper and lower bounds for this problem. In particular, we show that the problem of finding the best data distribution from selectivity queries is $\mathsf{NP}$-complete. On the positive side, we describe a Monte Carlo algorithm that constructs, in time $O((n+δ^{-d})δ^{-2}\mathop{\mathrm{polylog}})$, a discrete distribution $\tilde{\mathcal{D}}$ of size $O(δ^{-2})$, such that $\mathrm{err}_p(\tilde{\mathcal{D}},\mathcal{Z})\leq \min_{\mathcal{D}}\mathrm{err}_p(\mathcal{D},\mathcal{Z})+δ$ (for $p=1,2,\infty$) where the minimum is taken over all discrete distributions. We also establish conditional lower bounds, which strongly indicate the infeasibility of relative approximations as well as removal of the exponential dependency on the dimension for additive approximations. This suggests that significant improvements to our algorithm are unlikely.

Let B = (b1,…, bn} be a set of n axis-aligned boxes in ℝd where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ∪ ℝd that hits every box in B, i.e., N ∩ bi ≠ ϕ, for i = 1,…, n. The problem is known to be NP-Hard. Let p := p (B), the piercing number be the minimum size of a piercing set of B. We first present a randomized O(log log p)-approximation algorithm with expected running time O(nd/2 polylog(n)). Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if p = O(n1/(d-1)). Specifically, in the plane, the improved running time is O(n log p), assuming p < n/ logΩ(1) n. Finally, we study the dynamic version of the piercing problem where boxes can be inserted or deleted. For boxes in ℝ2, we obtain a randomized O(log log p)-approximation algorithm with O(n1/2 polylog(n)) amortized expected update time for insertion or deletion of boxes. For squares in ℝ2, the update time can be improved to O(n1/3 polylog(n)).

In this paper, we address clustering problems in scenarios where accurate direct access to the full dataset is impractical or impossible. Instead, we leverage oracle-based methods, which are particularly valuable in real-world applications where the data may be noisy, restricted due to privacy concerns or sheer volume. We utilize two oracles, the quadruplet and the distance oracle. The quadruplet oracle is a weaker oracle that only approximately compares the distances of two pairs of vertices. In practice, these oracles can be implemented using crowdsourcing or training classifiers or other predictive models. On the other hand, the distance oracle returns exactly the distance of two vertices, so it is a stronger and more expensive oracle to implement. We consider two noise models for the quadruplet oracle. In the adversarial noise model, if two pairs have similar distances, the response is chosen by an adversary. In the probabilistic noise model, the pair with the smaller distance is returned with a constant probability. We consider a set V of n vertices in a metric space that supports the quadruplet and the distance oracle. For each of the k-center, k-median, and k-means clustering problem on V, we design constant approximation algorithms that perform roughly O(nk) calls to the quadruplet oracle and O(k^2) calls to the distance oracle in both noise models. When the dataset has low intrinsic dimension, we significantly improve the approximation factors of our algorithms by performing a few additional calls to the distance oracle. We also show that for k-median and k-means clustering there is no hope to return any sublinear approximation using only the quadruplet oracle. Finally, we give constant approximation algorithms for estimating the clustering cost induced by any set of k vertices, performing roughly O(nk) calls to the quadruplet oracle and O(k^2) calls to the distance oracle.

Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser, and Ron. Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of tolerant bipartite testing problem: Given two parameters ε, δ ∈ (0,1), with δ > ε, and access to the adjacency matrix of a graph G, we have to decide whether G can be made bipartite by editing at most ε n² entries of the adjacency matrix of G, or we have to edit at least δ n² entries of the adjacency matrix to make G bipartite. In this paper, we prove that for δ = (2+Ω(1))ε, tolerant bipartite testing can be decided by performing 𝒪̃(1/ε³) many adjacency queries and in 2^𝒪̃(1/ε) time complexity. This improves upon the state-of-the-art query and time complexities of this problem of 𝒪̃(1/ε⁶) and 2^𝒪̃(1/ε²), respectively, due to Alon, Fernandez de la Vega, Kannan and Karpinski, where 𝒪̃(⋅) hides a factor polynomial in log (1/ε).

Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For $α\leq 1$ and $k \in \mathbb{Z}^+$, we say that a graph $G=(V,E)$ is $α$-partially $k$-colorable, if there exists a subset $S\subset V$ of cardinality $ |S | \geq α| V |$ such that the graph induced on $S$ is $k$-colorable. Partial $k$-colorability is a more robust structural property of a graph than $k$-colorability. For graphs that arise in practice, partial $k$-colorability might be a better notion to use than $k$-colorability, since data arising in practice often contains various forms of noise. We give a polynomial time algorithm that takes as input a $(1 - ε)$-partially $3$-colorable graph $G$ and a constant $γ\in [ε, 1/10]$, and colors a $(1 - ε/γ)$ fraction of the vertices using $\tilde{O}\left(n^{0.25 + O(γ^{1/2})} \right)$ colors. We also study natural semi-random families of instances of partially $3$-colorable graphs and partially $2$-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances.