70
70

Sep 18, 2013
09/13

by
Daniel A. Spielman; Nikhil Srivastava

texts

#
eye 70

#
favorite 0

#
comment 0

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of $G$ such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and for all vectors $x\in\R^V$ $(1-\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}\le \sum_{uv\in\tilde{E}}(x(u)-x(v))^2\tilde{w}_{uv} \le (1+\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}. (*)$ This improves upon the...

Source: http://arxiv.org/abs/0803.0929v4

78
78

Sep 23, 2013
09/13

by
Daniel A Spielman; Jaeoh Woo

texts

#
eye 78

#
favorite 0

#
comment 0

Boman and Hendrickson observed that one can solve linear systems in Laplacian matrices in time $\bigO{m^{3/2 + o (1)} \ln (1/\epsilon)}$ by preconditioning with the Laplacian of a low-stretch spanning tree. By examining the distribution of eigenvalues of the preconditioned linear system, we prove that the preconditioned conjugate gradient will actually solve the linear system in time $\softO{m^{4/3} \ln (1/\epsilon)}$.

Source: http://arxiv.org/abs/0903.2816v1

55
55

Sep 19, 2013
09/13

by
Miklós Bóna; Daniel A. Spielman

texts

#
eye 55

#
favorite 0

#
comment 0

We constructively prove that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain.

Source: http://arxiv.org/abs/math/9812073v1

102
102

Sep 22, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 102

#
favorite 0

#
comment 0

We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative distance $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{f} (A)) = O (b \log n)$, where...

Source: http://arxiv.org/abs/cs/0310036v2

60
60

Sep 19, 2013
09/13

by
Samuel I. Daitch; Daniel A. Spielman

texts

#
eye 60

#
favorite 0

#
comment 0

We use support theory, in particular the fretsaw extensions of Shklarski and Toledo, to design preconditioners for the stiffness matrices of 2-dimensional truss structures that are stiffly connected. Provided that all the lengths of the trusses are within constant factors of each other, that the angles at the corners of the triangles are bounded away from 0 and $\pi$, and that the elastic moduli and cross-sectional areas of all the truss elements are within constant factors of each other, our...

Source: http://arxiv.org/abs/cs/0703119v2

53
53

Sep 20, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 53

#
favorite 0

#
comment 0

We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large as $m$. We include an introduction to...

Source: http://arxiv.org/abs/cs/0301019v1

60
60

Sep 21, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 60

#
favorite 0

#
comment 0

We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time...

Source: http://arxiv.org/abs/0808.4134v3

49
49

Sep 20, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 49

#
favorite 0

#
comment 0

We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive...

Source: http://arxiv.org/abs/cs/0607105v5

50
50

Sep 22, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 50

#
favorite 0

#
comment 0

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

Source: http://arxiv.org/abs/cs/0111050v7

38
38

Sep 18, 2013
09/13

by
Samuel I. Daitch; Daniel A. Spielman

texts

#
eye 38

#
favorite 0

#
comment 0

We present faster approximation algorithms for generalized network flow problems. A generalized flow is one in which the flow out of an edge differs from the flow into the edge by a constant factor. We limit ourselves to the lossy case, when these factors are at most 1. Our algorithm uses a standard interior-point algorithm to solve a linear program formulation of the network flow problem. The system of linear equations that arises at each step of the interior-point algorithm takes the form of...

Source: http://arxiv.org/abs/0803.0988v2

73
73

Sep 18, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 73

#
favorite 0

#
comment 0

Spielman and Teng introduced the smoothed analysis of algorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.

Source: http://arxiv.org/abs/math/0212413v1

51
51

Sep 18, 2013
09/13

by
Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 51

#
favorite 0

#
comment 0

We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster...

Source: http://arxiv.org/abs/0809.3232v1

22
22

Jun 27, 2018
06/18

by
Adam Marcus; Daniel A. Spielman; Nikhil Srivastava

texts

#
eye 22

#
favorite 0

#
comment 0

We study three convolutions of polynomials that are inspired by free probability. We define these to be the expected characteristic polynomials of certain random matrices. The symmetric additive and multiplicative convolutions have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, appears new. We prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1504.00350

94
94

Jul 20, 2013
07/13

by
Adam Marcus; Daniel A. Spielman; Nikhil Srivastava

texts

#
eye 94

#
favorite 0

#
comment 0

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of...

Source: http://arxiv.org/abs/1304.4132v1

81
81

Sep 21, 2013
09/13

by
Joshua Batson; Daniel A. Spielman; Nikhil Srivastava

texts

#
eye 81

#
favorite 0

#
comment 0

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\ceil{d(n-1)}$ edges such that for every $x \in...

Source: http://arxiv.org/abs/0808.0163v3

17
17

Jun 28, 2018
06/18

by
Yin Tat Lee; Richard Peng; Daniel A. Spielman

texts

#
eye 17

#
favorite 0

#
comment 0

We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form $L L^{T}$, where $L$ is a lower-triangular matrix with a number of nonzero entries linear in its dimension. Furthermore linear systems in $L$ and $L^{T}$ can be solved in $O (n)$ work and $O(\log{n}\log^2\log{n})$ depth, where $n$ is the dimension of the matrix. We present...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1506.08204

70
70

Sep 21, 2013
09/13

by
Afonso S. Bandeira; Amit Singer; Daniel A. Spielman

texts

#
eye 70

#
favorite 0

#
comment 0

The O(d) Synchronization problem consists of estimating a set of unknown orthogonal transformations O_i from noisy measurements of a subset of the pairwise ratios O_iO_j^{-1}. We formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the O(d) synchronization problem with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method to solve this...

Source: http://arxiv.org/abs/1204.3873v2

4
4.0

Jun 30, 2018
06/18

by
Adam W. Marcus; Daniel A. Spielman; Nikhil Srivastava

texts

#
eye 4

#
favorite 0

#
comment 0

We survey the techniques used in our recent resolution of the Kadison-Singer problem and proof of existence of Ramanujan Graphs of every degree: mixed characteristic polynomials and the method of interlacing families of polynomials. To demonstrate the method of interlacing families of polynomials, we give a simple proof of Bourgain and Tzafriri's restricted invertibility principle in the isotropic case.

Topics: Mathematics, Spectral Theory, Combinatorics, Operator Algebras

Source: http://arxiv.org/abs/1408.4421

18
18

Jun 27, 2018
06/18

by
Adam W. Marcus; Nikhil Srivastava; Daniel A. Spielman

texts

#
eye 18

#
favorite 0

#
comment 0

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1505.08010

84
84

Sep 19, 2013
09/13

by
John Dunagan; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 84

#
favorite 0

#
comment 0

We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).

Source: http://arxiv.org/abs/cs/0302011v2

52
52

Sep 22, 2013
09/13

by
Arvind Sankar; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 52

#
favorite 0

#
comment 0

Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prove it is unlikely that $A$ has large growth factor under Gaussian elimination without pivoting. By combining these results, we bound the smoothed precision needed by Gaussian elimination without pivoting. Our results improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan...

Source: http://arxiv.org/abs/cs/0310022v4

16
16

Jun 27, 2018
06/18

by
Rasmus Kyng; Anup Rao; Sushant Sachdeva; Daniel A. Spielman

texts

#
eye 16

#
favorite 0

#
comment 0

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large $p$ of $p$-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in...

Topics: Metric Geometry, Computing Research Repository, Learning, Data Structures and Algorithms,...

Source: http://arxiv.org/abs/1505.00290

45
45

Sep 23, 2013
09/13

by
Michael Elkin; Yuval Emek; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 45

#
favorite 0

#
comment 0

We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).

Source: http://arxiv.org/abs/cs/0411064v5

8
8.0

Jun 28, 2018
06/18

by
Rasmus Kyng; Yin Tat Lee; Richard Peng; Sushant Sachdeva; Daniel A. Spielman

texts

#
eye 8

#
favorite 0

#
comment 0

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1512.01892

41
41

Sep 19, 2013
09/13

by
Paul Christiano; Jonathan A. Kelner; Aleksander Madry; Daniel A. Spielman; Shang-Hua Teng

texts

#
eye 41

#
favorite 0

#
comment 0

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges,...

Source: http://arxiv.org/abs/1010.2921v2

51
51

Sep 19, 2013
09/13

by
Andrew M. Childs; Richard Cleve; Enrico Deotto; Edward Farhi; Sam Gutmann; Daniel A. Spielman

texts

#
eye 51

#
favorite 0

#
comment 0

We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph....

Source: http://arxiv.org/abs/quant-ph/0209131v2