Arrow Research search

Author name cluster

Daniel A. Spielman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

FOCS Conference 2015 Conference Paper

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

  • Adam W. Marcus
  • Daniel A. Spielman
  • Nikhil Srivastava

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 an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

Details

IJCAI Conference 2013 Conference Paper

Exact Recovery of Sparsely-Used Dictionaries

  • Daniel A. Spielman
  • Huan Wang
  • John Wright

We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that O(n log n) samples are sufficient to uniquely determine the coefficient matrix. Based on this proof, we design a polynomial-time algorithm, called Exact Recovery of Sparsely-Used Dictionaries (ER- SpUD), and prove that it probably recovers the dictionary and coefficient matrix when the coefficient matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the true dictionary as well as the coefficients with probability higher than many state-of-the-art algorithms.

PDF Details DOI

FOCS Conference 2013 Conference Paper

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

  • Adam W. Marcus
  • Daniel A. Spielman
  • Nikhil Srivastava

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 infinite families of (c, d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by √c-1+√d-1, for all c, d ≥ q 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials".

Details

ICML Conference 2009 Conference Paper

Fitting a graph to vector data

  • Samuel I. Daitch
  • Jonathan A. Kelner
  • Daniel A. Spielman

We introduce a measure of how well a combinatorial graph fits a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2( d + 1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classification, regression and clustering problems.

Details

STOC Conference 2009 Conference Paper

Twice-ramanujan sparsifiers

  • Joshua D. Batson
  • Daniel A. Spielman
  • Nikhil Srivastava

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,~{w}) with at most ⌈d(n-1)⌉ edges such that for every x ∈ R V , [x T L G x ≤ x T L H x ≤ ((d+1+2√d)/(d+1-2√d)) • x T L G x] where L G and L H are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

Details

STOC Conference 2008 Conference Paper

Faster approximate lossy generalized flow via interior point algorithms

  • Samuel I. Daitch
  • Daniel A. Spielman

We present asymptotically faster approximation algorithms for the generalized flow problems in which multipliers on edges are at most 1. For this lossy version of the maximum generalized flow problem, we obtain an additive ε approximation of the maximum flow in time O{m 3/2 log (U/ε) 2 }, where m is the number of edges in the graph, all capacities are integers in the range {1, ..., U}, and all loss multipliers are ratios of integers in this range. For minimum cost lossy generalized flow with costs in the range {1,...,U}, we obtain a flow that has value within an additive ε of the maximum value and cost at most the optimal cost. In many parameter ranges, these algorithms improve over the previously fastest algorithms for the generalized maximum flow problem by a factor of m 1/2 and for the minimum cost generalized flow problem by a factor of approximately m 1/2 / ε 2 . The algorithms work by accelerating traditional interior point algorithms by quickly solving the system of linear equations that arises in each step. The contributions of this paper are twofold. First, we analyze the performance of interior point algorithms with approximate linear system solvers. This analysis alone provides an algorithm for the standard minimum cost flow problem that runs in time Om 3/2 log U}--an improvement of roughly O{n / m 1/2 } over previous algorithms. Second, we examine the linear equations that arise when using an interior point algorithm to solve generalized flow problems. We observe that these belong to the family of symmetric M-matrices, and we then develop Om-time algorithms for solving linear systems in these matrices. These algorithms reduce the problem of solving a linear system in a symmetric M-matrix to that of solving O{log n} linear systems in symmetric diagonally-dominant matrices, which we can do in time Om using the algorithm of Spielman and Teng. All of our algorithms operate on numbers of bit length at most O{log n U / ε}.

Details

FOCS Conference 2007 Conference Paper

Spectral Graph Theory and its Applications

  • Daniel A. Spielman

Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.

Details

FOCS Conference 2005 Conference Paper

Improved Smoothed Analysis of the Shadow Vertex Simplex Method

  • Amit Deshpande 0001
  • Daniel A. Spielman

Spielman and Teng (JACM '04), proved that the smoothed complexity of a two-phase shadow-vertex method for linear programming is polynomial in the number of constraints n, the number of variables d, and the parameter of perturbation 1//spl sigma/. The key geometric result in their proof was an upper bound of O(nd/sup 3//min (/spl sigma/, (9d ln n)/sup 1/2 /)/sup 6/) on the expected size of the shadow of the polytope defined by the perturbed linear program. In this paper, we give a much simpler proof of a better bound: O(n/sup 2/ d ln n/min (/spl sigma/, (4d ln n)/sup 1/2 /)/sup 2/). When evaluated at /spl sigma/ = (9d ln n)/sup 1/2 /, this improves the size estimate from O(nd/sup 6/ ln/sup 3/ n) to O(n/sup 2/d/sup 2/ ln n). The improvement only becomes better as /spl sigma/ decreases. The bound on the running time of the two-phase shadow vertex proved by Spielman and Teng is dominated by the exponent of /spl sigma/ in the shadow-size bound. By reducing this exponent from 6 to 2, we decrease the exponent in the smoothed complexity of the two-phase shadow vertex method by a multiplicative factor of 3.

Details

FOCS Conference 2003 Conference Paper

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m 1. 31 )

  • Daniel A. Spielman
  • Shang-Hua Teng

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 b, produces a vector x/spl tilde/ within relative distance /spl epsi/ of the solution to Ax = b in time O(m/sup 1. 31/log(n//spl epsi/)b/sup O(1)/), where b is the log of the ratio of the largest to smallest non-zero entry of A. If the graph of A has genus m/sup 2/spl theta// or does not have a K/sub m/spl theta// minor, then the exponent of m can be improved to the minimum of 1 + 5/spl theta/ and (9/8)(1 + /spl theta/). The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.

Details

FOCS Conference 1996 Conference Paper

Highly Fault-Tolerant Parallel Computation (extended abstract)

  • Daniel A. Spielman

We re-introduce the coded model of fault-tolerant computation in which the input and output of a computational device are treated as words in an error-correcting code. A computational device correctly computes a function in the coded model if its input and output, once decoded, are a valid input and output of the function. In the coded model, it is reasonable to hope to simulate all computational devices by devices whose size is greater by a constant factor but which are exponentially reliable even if each of their components can fail with some constant probability. We consider fine-grained parallel computations in which each processor has a constant probability of producing the wrong output at each time step. We show that any parallel computation that runs for time t on w processors can be performed reliably on a faulty machine in the coded model using wlog/sup 0(1/)w processors and time tlog/sup 0(1)/w. The failure probability of the computation will be at most t/spl middot/exp(-w/sup 1/4 /). The codes used to communicate with our fault-tolerant machines are generalized Reed-Solomon codes and can thus be encoded and decoded in O(nlog/sup 0(1)/n) sequential time and are independent of the machine they are used to communicate with. We also show how coded computation can be used to self-correct many linear functions in parallel with arbitrarily small overhead.

Details

FOCS Conference 1996 Conference Paper

Spectral Partitioning Works: Planar Graphs and Finite Element Meshes

  • Daniel A. Spielman
  • Shang-Hua Teng

Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scientific numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and finite element meshes-the classes of graphs to which they are usually applied. While active spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce separators whose ratio of vertices removed to edges cut is O(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 1/d/) for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs: we prove a bound of O(1/n) for bounded-degree planar graphs and O(1/n/sup 2/d/) for well-shaped d-dimensional meshes.

Details

FOCS Conference 1994 Conference Paper

Expander Codes

  • Michael Sipser
  • Daniel A. Spielman

We present a new class of asymptotically good, linear error-correcting codes based upon expander graphs. These codes have linear time sequential decoding algorithms, logarithmic time parallel decoding algorithms with a linear number of processors, and are simple to understand. We present both randomized and explicit constructions for some of these codes. Experimental results demonstrate the extremely good performance of the randomly chosen codes. >

Details