This content will become publicly available on June 1, 2024
 NSFPAR ID:
 10440642
 Date Published:
 Journal Name:
 Inventiones mathematicae
 Volume:
 232
 Issue:
 3
 ISSN:
 00209910
 Page Range / eLocation ID:
 1027 to 1160
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

Abstract This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals.
The following summarizes the main results proved under suitable partition hypotheses.
If
is a cardinal,$\kappa $ ,$\epsilon < \kappa $ ,${\mathrm {cof}}(\epsilon ) = \omega $ and$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the almost everywhere short length continuity property: There is a club$\Phi $ and a$C \subseteq \kappa $ so that for all$\delta < \epsilon $ , if$f,g \in [C]^\epsilon _*$ and$f \upharpoonright \delta = g \upharpoonright \delta $ , then$\sup (f) = \sup (g)$ .$\Phi (f) = \Phi (g)$ If
is a cardinal,$\kappa $ is countable,$\epsilon $ holds and$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the strong almost everywhere short length continuity property: There is a club$\Phi $ and finitely many ordinals$C \subseteq \kappa $ so that for all$\delta _0, ..., \delta _k \leq \epsilon $ , if for all$f,g \in [C]^\epsilon _*$ ,$0 \leq i \leq k$ , then$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$ .$\Phi (f) = \Phi (g)$ If
satisfies$\kappa $ ,$\kappa \rightarrow _* (\kappa )^\kappa _2$ and$\epsilon \leq \kappa $ , then$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$ satisfies the almost everywhere monotonicity property: There is a club$\Phi $ so that for all$C \subseteq \kappa $ , if for all$f,g \in [C]^\epsilon _*$ ,$\alpha < \epsilon $ , then$f(\alpha ) \leq g(\alpha )$ .$\Phi (f) \leq \Phi (g)$ Suppose dependent choice (
),$\mathsf {DC}$ and the almost everywhere short length club uniformization principle for${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$ hold. Then every function${\omega _1}$ satisfies a finite continuity property with respect to closure points: Let$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$ be the club of$\mathfrak {C}_f$ so that$\alpha < {\omega _1}$ . There is a club$\sup (f \upharpoonright \alpha ) = \alpha $ and finitely many functions$C \subseteq {\omega _1}$ so that for all$\Upsilon _0, ..., \Upsilon _{n  1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$ , for all$f \in [C]^{\omega _1}_*$ , if$g \in [C]^{\omega _1}_*$ and for all$\mathfrak {C}_g = \mathfrak {C}_f$ ,$i < n$ , then$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$ .$\Phi (g) = \Phi (f)$ Suppose
satisfies$\kappa $ for all$\kappa \rightarrow _* (\kappa )^\epsilon _2$ . For all$\epsilon < \kappa $ ,$\chi < \kappa $ does not inject into$[\kappa ]^{<\kappa }$ , the class of${}^\chi \mathrm {ON}$ length sequences of ordinals, and therefore,$\chi $ . As a consequence, under the axiom of determinacy$[\kappa ]^\chi  < [\kappa ]^{<\kappa }$ , these two cardinality results hold when$(\mathsf {AD})$ is one of the following weak or strong partition cardinals of determinacy:$\kappa $ ,${\omega _1}$ ,$\omega _2$ (for all$\boldsymbol {\delta }_n^1$ ) and$1 \leq n < \omega $ (assuming in addition$\boldsymbol {\delta }^2_1$ ).$\mathsf {DC}_{\mathbb {R}}$ 
Chakrabarti, Amit ; Swamy, Chaitanya (Ed.)A Boolean maximum constraint satisfaction problem, MaxCSP(f), is specified by a predicate f:{1,1}^k → {0,1}. An nvariable instance of MaxCSP(f) consists of a list of constraints, each of which applies f to k distinct literals drawn from the n variables. For k = 2, Chou, Golovnev, and Velusamy [Chou et al., 2020] obtained explicit ratios characterizing the √ nspace streaming approximability of every predicate. For k ≥ 3, Chou, Golovnev, Sudan, and Velusamy [Chou et al., 2022] proved a general dichotomy theorem for √ nspace sketching algorithms: For every f, there exists α(f) ∈ (0,1] such that for every ε > 0, MaxCSP(f) is (α(f)ε)approximable by an O(log n)space linear sketching algorithm, but (α(f)+ε)approximation sketching algorithms require Ω(√n) space. In this work, we give closedform expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting α'_k = 2^{(k1)} (1k^{2})^{(k1)/2}, we show that for odd k ≥ 3, α(kAND) = α'_k, and for even k ≥ 2, α(kAND) = 2α'_{k+1}. Thus, for every k, kAND can be (2o(1))2^{k}approximated by O(log n)space sketching algorithms; we contrast this with a lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy [Chou et al., 2022] implying that streaming (2+ε)2^{k}approximations require Ω(n) space! We also resolve the ratio for the "atleast(k1)1’s" function for all even k; the "exactly(k+1)/21’s" function for odd k ∈ {3,…,51}; and fifteen other functions. We stress here that for general f, the dichotomy theorem in [Chou et al., 2022] only implies that α(f) can be computed to arbitrary precision in PSPACE, and thus closedform expressions need not have existed a priori. Our analyses involve identifying and exploiting structural "saddlepoint" properties of this dichotomy. Separately, for all threshold functions, we give optimal "biasbased" approximation algorithms generalizing [Chou et al., 2020] while simplifying [Chou et al., 2022]. Finally, we investigate the √ nspace streaming lower bounds in [Chou et al., 2022], and show that they are incomplete for 3AND, i.e., they fail to rule out (α(3AND})ε)approximations in o(√ n) space.more » « less

Over the last two decades, frameworks for distributedmemory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing prevalence of large network datasets. The Massively Parallel Computation (MPC) model is the defacto standard for studying graph algorithms in these frameworks theoretically. Subgraph counting is one such fundamental problem in analyzing massive graphs, with the main algorithmic challenges centering on designing methods which are both scalable and accurate. Given a graph G = (V, E) with n vertices, m edges and T triangles, our first result is an algorithm that outputs a (1+ε)approximation to T, with asymptotically optimal round and total space complexity provided any S ≥ max{(√ m, n²/m)} space per machine and assuming T = Ω(√{m/n}). Our result gives a quadratic improvement on the bound on T over previous works. We also provide a simple extension of our result to counting any subgraph of k size for constant k ≥ 1. Our second result is an O_δ(log log n)round algorithm for exactly counting the number of triangles, whose total space usage is parametrized by the arboricity α of the input graph. We extend this result to exactly counting kcliques for any constant k. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most 5 can be implemented in the MPC model in Õ_δ(√{log n}) rounds, O(n^δ) space per machine and O(mα³) total space. In addition to our theoretical results, we simulate our triangle counting algorithms in realworld graphs obtained from the Stanford Network Analysis Project (SNAP) database. Our results show that both our approximate and exact counting algorithms exhibit improvements in terms of round complexity and approximation ratio, respectively, compared to two previous widely used algorithms for these problems.more » « less