Dan Spielman

About

Dan Spielman is a Sterling Professor of Computer Science, as well as a Professor of Statistics and Data Science and of Mathematics at Yale University. His contact information includes his email, daniel.spielman@yale.edu, and his office is located at 219 Prospect Street in Kline Tower. As a senior faculty member, he contributes to multiple departments, reflecting a broad expertise in computer science, statistics, data science, and mathematics. The page indicates his involvement in Yale's academic community, but does not provide specific details about his research focus, background, or key contributions.

Research topics

• Artificial Intelligence
• Mathematics
• Computer Science
• Discrete mathematics
• Econometrics
• Pure mathematics
• Combinatorics
• Statistics

Selected publications

• Interlacing families I: Bipartite Ramanujan graphs of all degrees

  Annals of Mathematics · 2015-04-15 · 230 citations

  article

  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…

  PublisherDOI

• Sparsified Cholesky and multigrid solvers for connection laplacians

  2016-06-10 · 94 citations

  articleOpen accessSenior author

  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 eve…

  PublisherOA PDFDOI

• Finite free convolutions of polynomials

  Probability Theory and Related Fields · 2022-02-18 · 28 citations

  preprintOpen access

  We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric additive and multiplicative convolutions were introduced by Walsh and Szegö in different contexts, and have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, is new. By developi…

  PublisherOA PDFDOI

• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

  SIAM Journal on Computing · 2018-01-01 · 27 citations

  article

  We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on an analysis of 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…

  PublisherDOI

• Algorithms for Lipschitz Learning on Graphs

  Conference on Learning Theory · 2015-06-26 · 26 citations

  articleSenior author

  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 extens ion 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 expe…

  Publisher

Recent grants

• AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond

  NSF · $773k · 2011–2016

• ITR: Collaborative Research: Smoothed Analysis of Algorithms

  NSF · $382k · 2006–2009

• AF: Medium: Generalized Algebraic Graph Theory: Algorithms and Analysis

  NSF · $774k · 2016–2021

Frequent coauthors

• Shang‐Hua Teng

  University of Southern California

  51 shared

• Nikhil Srivastava

  University of California, Berkeley

  27 shared

• Richard Beigel

  Temple University

  21 shared

• Grigorii Margulis

  16 shared

• Adam W. Marcus

  École Polytechnique Fédérale de Lausanne

  16 shared

• Nikhil Srivastava

  Berkeley College

  9 shared

• Richard Peng

  University of Waterloo

  8 shared

• Michael Luby

  International Computer Science Institute

  7 shared

Similar researchers at Yale University

• Ronald Coifmanh-74
• Vladimir Rokhlinh-60
• Wilhelm Schlagh-53