Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinite Volume Spaces and Sparsification
151
0
0.0
(
0
)
Added by
Ilan Newman
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes. We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgains theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $ell_1$-volume with distortion smaller than $tilde{Omega}(n^{1/5})$. We further address the problem of $ell_1$-dimension reduction in the context of $ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $ell_1$ metric on $n$ points can be $(1+ epsilon)$-approximated by a sum of $O(n/epsilon^2)$ cut metrics, improving over the best previously known bound of $O(n log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{u}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.
rate research
Read More
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_alpha(G)=D-sum_{r=1}^dalpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $alpha=(alpha_1...alpha_d)$ are nonnegative coefficients with $sum_{r=1}^dalpha_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of $L_alpha(G)$ appears to be algorithmically challenging as the matrix power $(D^{-1}A)^r$ is defined by all paths of length $r$, whose precise calculation would be prohibitively expensive. In this paper, we develop the first nearly linear time algorithm for this sparsification problem: For any $G$ with $n$ vertices and $m$ edges, $d$ coefficients $alpha$, and $epsilon > 0$, our algorithm runs in time $O(d^2mlog^2n/epsilon^{2})$ to construct a Laplacian matrix $tilde{L}=D-tilde{A}$ with $O(nlog n/epsilon^{2})$ non-zeros such that $tilde{L}approx_{epsilon}L_alpha(G)$. Matrix polynomials arise in mathematical analysis of matrix functions as well as numerical solutions of matrix equations. Our work is particularly motivated by the algorithmic problems for speeding up the classic Newtons method in applications such as computing the inverse square-root of the precision matrix of a Gaussian random field, as well as computing the $q$th-root transition (for $qgeq1$) in a time-reversible Markov model. The key algorithmic step for both applications is the construction of a spectral sparsifier of a constant degree random-walk matrix-polynomials introduced by Newtons method. Our algorithm can also be used to build efficient data structures for effective resistances for multi-step time-reversible Markov models, and we anticipate that it could be useful for other tasks in network analysis.
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Delta+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+varepsilon) Delta$ coloring, sampling only $O_{varepsilon}(sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Delta+1)$ are triangle-free graphs which are $O(frac{Delta}{ln{Delta}})$ colorable. We prove that sampling $O(Delta^{gamma} + sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_{gamma}(frac{Delta}{ln{Delta}})$ coloring of triangle-free graphs. * We show that sampling $O_{varepsilon}(log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+varepsilon) cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets ${1,ldots,deg(v)+1}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
A tantalizing conjecture in discrete mathematics is the one of Komlos, suggesting that for any vectors $mathbf{a}_1,ldots,mathbf{a}_n in B_2^m$ there exist signs $x_1, dots, x_n in { -1,1}$ so that $|sum_{i=1}^n x_imathbf{a}_i|_infty le O(1)$. It is a natural extension to ask what $ell_q$-norm bound to expect for $mathbf{a}_1,ldots,mathbf{a}_n in B_p^m$. We prove that, for $2 le p le q le infty$, such vectors admit fractional colorings $x_1, dots, x_n in [-1,1]$ with a linear number of $pm 1$ coordinates so that $|sum_{i=1}^n x_imathbf{a}_i|_q leq O(sqrt{min(p,log(2m/n))}) cdot n^{1/2-1/p+ 1/q}$, and that one can obtain a full coloring at the expense of another factor of $frac{1}{1/2 - 1/p + 1/q}$. In particular, for $p in (2,3]$ we can indeed find signs $mathbf{x} in { -1,1}^n$ with $|sum_{i=1}^n x_imathbf{a}_i|_infty le O(n^{1/2-1/p} cdot frac{1}{p-2})$. Our result generalizes Spencers theorem, for which $p = q = infty$, and is tight for $m = n$. Additionally, we prove that for any fixed constant $delta>0$, in a centrally symmetric body $K subseteq mathbb{R}^n$ with measure at least $e^{-delta n}$ one can find such a fractional coloring in polynomial time. Previously this was known only for a small enough constant -- indeed in this regime classical nonconstructive arguments do not apply and partial colorings of the form $mathbf{x} in { -1,0,1}^n$ do not necessarily exist.
Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, r-rank perturbed graphic matroid M is a binary matroid that can be represented in the form I +P, where I is the incidence matrix of some graph and P is a binary matrix of rank at most r. Such matroids naturally appear in a number of theoretical and applied settings. The main motivation behind our work is an attempt to understand which parameterized algorithms for various problems on graphs could be lifted to perturbed graphic matroids. We study the parameterized complexity of a natural generalization (for matroids) of the following fundamental problems on graphs: Steiner Tree and Multiway Cut. In this generalization, called the Space Cover problem, we are given a binary matroid M with a ground set E, a set of terminals Tsubseteq E, and a non-negative integer k. The task is to decide whether T can be spanned by a subset of Esetminus T of size at most k. We prove that on graphic matroid perturbations, for every fixed r, Space Cover is fixed-parameter tractable parameterized by k. On the other hand, the problem becomes W[1]-hard when parameterized by r+k+|T| and it is NP-complete for rleq 2 and |T|leq 2. On cographic matroids, that are the duals of graphic matroids, Space Cover generalizes another fundamental and well-studied problem, namely Multiway Cut. We show that on the duals of perturbed graphic matroids the Space Cover problem is fixed-parameter tractable parameterized by r+k.
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+epsilon)$-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(clog 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
