Literature Survey: Sublinear Algorithm

Domain: Data Structures & New Algorithms
Topic Search: sublinear algorithm
Timeframe: 2023 - 2026

This is a curated survey of recent publications focusing on sublinear algorithm. Results are filtered for top-tier journals and prominent conferences.

📚 Curated Peer-Reviewed Publications

1. A Sublinear-Time Quantum Algorithm for Approximating Partition Functions

Venue: SODA | Year: 2023 | Citations: 29 Authors: Arjan Cornelissen, Yassine Hamoudi

We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over the seminal nearly-linear time algorithm of \v{S}tefankovi\v{c}, Vempala and Vigoda [JACM, 2009]. Our result also preserves the quadratic speed-up in precision and spectral gap achieved in previous work by exploiting the properties of quantum Markov chains. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of $k$-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body. Our approach relies on developing new variants of the quantum phase and amplitude estimation algorithms that return nearly unbiased estimates with low variance and without destroying their initial quantum state. We extend these subroutines into a nearly unbiased quantum mean estimator that reduces the variance quadratically faster than the classical empirical mean. No such estimator was known to exist prior to our work. These properties, which are of general interest, lead to better convergence guarantees within the paradigm of simulated annealing for computing partition functions.

2. Sublinear Time Algorithms and Complexity of Approximate Maximum Matching

Venue: STOC | Year: 2023 | Citations: 27 Authors: Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O(n) time for n-vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O(n1+є) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω(n) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then. In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n1.2 − o(1) queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ(n). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds. We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n2−Ω(1). The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n1.2−o(1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n2−o(1).

3. Sublinear Algorithms for (1.5+ε)-Approximate Matching

Venue: STOC | Year: 2023 | Citations: 16 Authors: Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. [SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time. We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.

4. Sublinear Algorithms for Scheduling with Chain Precedence Constraints

Venue: COCOON | Year: 2024 | Citations: 1 Authors: Bin Fu, Yumei Huo, Hairong Zhao

With the exponential growth of data in various applications, sublinear algorithms have become a new paradigm in computing for solving problems involving large amount datasets. In this paper, we study the classical parallel machine scheduling problem subject to chain…

5. Bi-criteria Sublinear Time Algorithms for Clustering with Outliers in High Dimensions

Venue: COCOON | Year: 2024 | Citations: 1 Authors: Jiawei Huang 0009, Wenjie Liu 0008, Hu Ding 0003

Real world datasets often contain outliers, and the presence of outliers can make the clustering problems to be much more challenging. Existing algorithms that are specifically designed to handle clustering with outliers often suffer from high computational…

6. Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model

Venue: COCOON | Year: 2026 | Citations: 0 Authors: Weiming Feng 0001, Zelin Li, Pan Peng 0001

We study sublinear-time algorithms for solving linear systems

$$Sz = b$$

, where S is a diagonally dominant matrix, i.e.,

$$|S_{ii}| \ge \delta + \sum _{j \ne i} |S_{ij}|$$

for all…

7. Self-stabilizing (varDelta +1)-Coloring in Sublinear (in varDelta ) Rounds via Locally-Iterative Algorithms

Venue: COCOON | Year: 2023 | Citations: 0 Authors: Xinyu Fu 0009, Yitong Yin, Chaodong Zheng

Fault-tolerance is a central theme in distributed computing. Self-stabilization is a key property that guarantees a distributed system starting from an arbitrary state eventually converges to a desired behavior. Such strong level of fault-tolerance is often desirable…

8. Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs

Venue: WADS | Year: 2023 | Citations: 0 Authors: Xiuge Chen, Rajesh Chitnis, Patrick Eades, Anthony Wirth

In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters – maximum independent set, minimum dominating set and maximum matching – on sparse graph classes, i.e., graphs which satisfy…

⚡ Latest Pre-Prints

1. Sublinear-Time Algorithms for Compressive Phase Retrieval

Published: 2017-09-09 Authors: Yi Li, Vasileios Nakos

In the compressive phase retrieval problem, or phaseless compressed sensing, or compressed sensing from intensity only measurements, the goal is to reconstruct a sparse or approximately $k$-sparse vector $x \in \mathbb{R}^n$ given access to $y= |Φx|$, where $|v|$ denotes the vector obtained from taking the absolute value of $v\in\mathbb{R}^n$ coordinate-wise. In this paper we present sublinear-time algorithms for different variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements.

2. Finding Cycles and Trees in Sublinear Time

Published: 2010-07-23 Authors: Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq 3$ and tree-minors in bounded-degree graphs. The complexity of these algorithms is related to the distance of the graph from being $C_k$-minor-free (resp., free from having the corresponding tree-minor). In particular, if the graph is far (i.e., $Ω(1)$-far) {from} being cycle-free, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time $\tilde{O}(\sqrt{N})$, where $N$ denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of {\em one-sided error} property testing algorithms in the bounded-degree graphs model. For example, we show that cycle-freeness of $N$-vertex graphs can be tested with one-sided error within time complexity $\tilde{O}(\frac{1}{\epsilon}\cdot\sqrt{N})$. This matches the known $Ω(\sqrt{N})$ query lower bound, and contrasts with the fact that any minor-free property admits a {\em two-sided error} tester of query complexity that only depends on the proximity parameter $\epsilon$. For any constant $k\geq3$, we extend this result to testing whether the input graph has a simple cycle of length at least $k$. On the other hand, for any fixed tree $T$, we show that $T$-minor-freeness has a one-sided error tester of query complexity that only depends on the proximity parameter $\epsilon$. Our algorithm for finding cycles in bounded-degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree-minors in $o(\sqrt{N})$ complexity.

3. Sublinear Algorithms for (Δ+ 1) Vertex Coloring

Published: 2018-07-24 Authors: Sepehr Assadi, Yu Chen, Sanjeev Khanna

Any graph with maximum degree $Δ$ admits a proper vertex coloring with $Δ+ 1$ colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We answer this fundamental question in the affirmative for several canonical classes of sublinear algorithms including graph streaming, sublinear time, and massively parallel computation (MPC) algorithms. In particular, we design: - A single-pass semi-streaming algorithm in dynamic streams using $\tilde{O}(n)$ space. The only known semi-streaming algorithm prior to our work was a folklore O(log n)-pass algorithm obtained by simulating classical distributed algorithms in the streaming model. - A sublinear-time algorithm in the standard query model that allows neighbor queries and pair queries using $\tilde{O}(n\sqrt{n})$ time. We further show that any algorithm that outputs a valid coloring with sufficiently large constant probability requires $Ω(n\sqrt{n})$ time. No non-trivial sublinear time algorithms were known prior to our work. - A parallel algorithm in the massively parallel computation (MPC) model using $\tilde{O}(n)$ memory per machine and $O(1)$ MPC rounds. Our number of rounds significantly improves upon the recent $O(\log\logΔ\cdot\log^*{(n)})$-round algorithm of Parter [ICALP 2018]. At the core of our results is a remarkably simple meta-algorithm for the $(Δ+1)$ coloring problem: Sample $O(\log{n})$ colors for each vertex from the $Δ+1$ colors; find a proper coloring of the graph using only the sampled colors. We prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in the corresponding models.

4. Sublinear classical and quantum algorithms for general matrix games

Published: 2020-12-11 Authors: Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, Xiaodi Wu

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $A\in\mathbb{R}^{n\times d}$, sublinear algorithms for the matrix game $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}} y^{\top} Ax$ were previously known only for two special cases: (1) $\mathcal{Y}$ being the $\ell_{1}$-norm unit ball, and (2) $\mathcal{X}$ being either the $\ell_{1}$- or the $\ell_{2}$-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed $q\in (1,2]$, we solve the matrix game where $\mathcal{X}$ is a $\ell_{q}$-norm unit ball within additive error $ε$ in time $\tilde{O}((n+d)/{ε^{2}})$. We also provide a corresponding sublinear quantum algorithm that solves the same task in time $\tilde{O}((\sqrt{n}+\sqrt{d})\textrm{poly}(1/ε))$ with a quadratic improvement in both $n$ and $d$. Both our classical and quantum algorithms are optimal in the dimension parameters $n$ and $d$ up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the $\ell_{q}$-margin support vector machines as applications.

5. Sublinear Algorithms for (1.5+ε)-Approximate Matching

Published: 2022-12-01 Authors: Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation factor of $2$. Very recently, Behnezhad et al.[SODA'23] improved the approximation factor to $(2-\frac{1}{2^{O(1/γ)}})$ using $n^{1+γ}$ time. This improvement over the factor $2$ is, however, minuscule and they asked if even $1.99$-approximation is possible in $n^{2-Ω(1)}$ time. We give a strong affirmative answer to this open problem by showing $(1.5+ε)$-approximation algorithms that run in $n^{2-Θ(ε^{2})}$ time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and streaming [Bernstein ICALP'20] settings, but never before in the sublinear setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23] independently showed sublinear algorithms similar to our Theorem 1.2 in both adjacency list and matrix models. Furthermore, in [BRR'23], they show additional results on strictly better-than-1.5 approximate matching algorithms in both upper and lower bound sides.

6. Sublinear Algorithms for Hierarchical Clustering

Published: 2022-06-15 Authors: Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil

Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in domains such as phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources. The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) MPC model where the graph edges are partitioned over several machines connected via a communication channel. We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing better algorithms in each of these models.

7. Metric Sublinear Algorithms via Linear Sampling

Published: 2018-07-24 Authors: Hossein Esfandiari, Michael Mitzenmacher

In this work we provide a new technique to design fast approximation algorithms for graph problems where the points of the graph lie in a metric space. Specifically, we present a sampling approach for such metric graphs that, using a sublinear number of edge weight queries, provides a {\em linear sampling}, where each edge is (roughly speaking) sampled proportionally to its weight. For several natural problems, such as densest subgraph and max cut among others, we show that by sparsifying the graph using this sampling process, we can run a suitable approximation algorithm on the sparsified graph and the result remains a good approximation for the original problem. Our results have several interesting implications, such as providing the first sublinear time approximation algorithm for densest subgraph in a metric space, and improving the running time of estimating the average distance.

8. Almost Optimal Sublinear Time Algorithm for Semidefinite Programming

Published: 2012-08-26 Authors: Dan Garber, Elad Hazan

We present an algorithm for approximating semidefinite programs with running time that is sublinear in the number of entries in the semidefinite instance. We also present lower bounds that show our algorithm to have a nearly optimal running time.

9. Sublinear Algorithms for Gap Edit Distance

Published: 2019-10-02 Authors: Elazar Goldenberg, Robert Krauthgamer, Barna Saha

The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. A simple dynamic programming computes the edit distance between two strings of length $n$ in $O(n^2)$ time, and a more sophisticated algorithm runs in time $O(n+t^2)$ when the edit distance is $t$ [Landau, Myers and Schmidt, SICOMP 1998]. In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Koucký and Saks, FOCS 2018]. We study sublinear-time algorithms for small edit distance, which was investigated extensively because of its numerous applications. Our main result is an algorithm for distinguishing whether the edit distance is at most $t$ or at least $t^2$ (the quadratic gap problem) in time $\tilde{O}(\frac{n}{t}+t^3)$. This time bound is sublinear roughly for all $t$ in $[ω(1), o(n^{1/3})]$, which was not known before. The best previous algorithms solve this problem in sublinear time only for $t=ω(n^{1/3})$ [Andoni and Onak, STOC 2009]. Our algorithm is based on a new approach that adaptively switches between uniform sampling and reading contiguous blocks of the input strings. In contrast, all previous algorithms choose which coordinates to query non-adaptively. Moreover, it can be extended to solve the $t$ vs $t^{2-ε}$ gap problem in time $\tilde{O}(\frac{n}{t^{1-ε}}+t^3)$.

10. Sublinear algorithms for local graph centrality estimation

Published: 2014-04-07 Authors: Marco Bressan, Enoch Peserico, Luca Pretto

We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of $m$ arcs, with probability $(1-δ)$ computes a multiplicative $(1\pmε)$-approximation of its score by examining only $\tilde{O}(\min(m^{2/3} Δ^{1/3} d^{-2/3},\, m^{4/5} d^{-3/5}))$ nodes/arcs, where $Δ$ and $d$ are respectively the maximum and average outdegree of the graph (omitting for readability $\operatorname{poly}(ε^{-1})$ and $\operatorname{polylog}(δ^{-1})$ factors). A similar bound holds for computational complexity. We also prove a lower bound of $Ω(\min(m^{1/2} Δ^{1/2} d^{-1/2}, \, m^{2/3} d^{-1/3}))$ for both query complexity and computational complexity. Moreover, our technique yields a $\tilde{O}(n^{2/3})$ query complexity algorithm for the graph access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.

🧠 Architectural & Methodological Insights

The field of sublinear algorithms is undergoing a fundamental theoretical shift, moving beyond basic randomized sampling and simple property testing toward sophisticated structural relaxations, adaptive query strategies, and cross-model theoretical frameworks.

1. Cross-Model Primitive Translation: Methodological breakthroughs are increasingly driven by adapting dynamic, streaming, and distributed primitives into sublinear query models. A prime example is the adaptation of the Edge-Degree Constrained Subgraph (EDCS) and cut sparsifiers. Originally developed for dynamic and streaming environments, these structural tools are now used in sublinear time algorithms to break fundamental approximation barriers for graph matching and hierarchical clustering.

2. Adaptive and Weighted Sampling Dynamics: Earlier sublinear frameworks relied heavily on uniform, non-adaptive sampling. Modern algorithms incorporate adaptive mechanics—such as dynamically alternating between uniform random sampling and reading contiguous blocks of input in gap edit distance—or weight-proportional linear sampling in metric spaces. This adaptivity enables algorithms to bypass worst-case structural bottlenecks that defeat static query patterns.

3. Quantum Mechanics for Algorithmic Speedups: Quantum techniques are expanding the operational boundary of sublinear computation. By leveraging quantum Markov chains, quantum phase and amplitude estimation, and state-preserving estimators, recent quantum algorithms achieve quadratic variance reduction over classical empirical means. This enables sublinear-time estimation of partition functions and matrix games where classical sublinear bounds hit lower-bound barriers.

4. Correlation Decay in Super-Linear Query Bounds: A key innovation on the lower-bound frontier is the application of correlation decay techniques to sublinear complexity. Proving super-linear in n lower bounds (such as n^1.2 queries for matching) moves the domain beyond standard localized property-testing bounds and provides fine-grained lower bounds for constant-factor approximations.

🚀 Critical Research Gaps

1. The Complexity Exponent Gap in Approximate Matching While recent work has successfully surpassed the long-standing 1/2-approximation threshold for maximum matching in sublinear time, a substantial gap exists between known lower and upper bounds. Current algorithms achieve a (1.5+eps)-approximation in n^(2-Theta(eps^2)) time or a (2/3+Omega(1))-approximation in strongly sublinear time, whereas the strongest lower bound establishes an n^1.2 bound for a (2/3+Omega(1))-approximation. Closing the gap between n^1.2 and n^2 query complexity for better-than-1.5 approximations remains an open theoretical bottleneck. Motivating papers: Sublinear Time Algorithms and Complexity of Approximate Maximum Matching and Sublinear Algorithms for (1.5+ε)-Approximate Matching.

2. Generality of Sublinear Optimization Solvers Quantum algorithms achieve quadratic improvements in dimension parameters for matrix games, while classical sublinear algorithms remain restricted to specific geometric domains (such as l_q unit balls for 1 < q <= 2) or diagonally dominant matrices. A critical unresolved gap is developing classical sublinear algorithms that extend to general non-diagonally dominant linear systems or non-convex matrix optimization without requiring structural diagonal dominance or quantum hardware. Motivating papers: Sublinear classical and quantum algorithms for general matrix games and Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model.

3. Formal Limits of Adaptivity in Sequence and Metric Problems Adaptive sampling has proved effective for distinguishing edit distance gaps (e.g., distinguishing distance t from t^2) in sublinear time. However, there is no unified theoretical framework establishing the exact lower bounds for adaptive versus non-adaptive query models across sequence alignment and metric graph problems. The precise trade-offs between query adaptivity, metric sparsification distortion, and query complexity remain uncharacterized. Motivating papers: Sublinear Algorithms for Gap Edit Distance and Metric Sublinear Algorithms via Linear Sampling.

4. Model Translation Theorems Across Distributed, Streaming, and Query Models Structural tools like vertex color sampling and cut sparsifiers exhibit similar guarantees across semi-streaming, Massively Parallel Computation (MPC), and sublinear query models. However, the literature lacks a general compiler or reduction framework that translates resource bounds (such as MPC round complexity or streaming space) directly into sublinear query lower and upper bounds across arbitrary graph parameters. Motivating papers: Sublinear Algorithms for (Δ+ 1) Vertex Coloring and Sublinear Algorithms for Hierarchical Clustering.

💡 High-Impact Open Problems

1. Tight Query Complexity Bounds for Sub-1.5 Approximate Matching Develop an algorithm or establish a tight lower bound for achieving a (1.5 - eps)-approximation of maximum matching size. Specifically, investigate whether the Edge-Degree Constrained Subgraph (EDCS) framework can be constructed using O(n^1.5) queries, or if correlation decay lower-bound techniques can be extended to prove an n^(1.5 - o(1)) lower bound in the adjacency list query model.

2. Sublinear Solvers for General Weakly Dominant Linear Systems Design a sublinear-time classical algorithm for solving linear systems Sz = b where matrix S relaxes the strict diagonal dominance condition to weak dominance or bounded spectral graph conditions. Evaluate whether localized linear algebra techniques can achieve sublinear performance on network opinion dynamics and graph-based linear systems beyond the Friedkin-Johnsen model.

3. Adaptive Sublinear Sparsification for Metric Graphs with Noise and Outliers Formulate an adaptive metric sampling primitive that achieves sublinear query complexity for graph optimization problems (such as densest subgraph or hierarchical clustering) in high dimensions subject to adversarial outliers. The goal is to provide bi-criteria approximation guarantees matching offline techniques while maintaining sublinear running time relative to dataset size and dimensionality.