8 citations · 31 across the 14 of their papers we have counts for
17 papers
Nodal decompositions of a symmetric matrix
Theo McKenzie, John Urschel
Analyzing nodal domains is a way to discern the structure of eigenvectors of operators on a graph. We give a new definition extending the concept of nodal domains to arbitrary sign…
Representing the Special Linear Group with Block Unitriangular Matrices
John Urschel
We prove that every element of the special linear group can be represented as the product of at most six block unitriangular matrices, and that there exist matrices for which six p…
Some New Results on the Maximum Growth Factor in Gaussian Elimination
Alan Edelman, John Urschel
This paper combines modern numerical computation with theoretical results to improve our understanding of the growth factor problem for Gaussian elimination. On the computational s…
Hamilton Powers of Eulerian Digraphs
Enrico Celestino Colón, John Urschel
In this note, we prove that the power of a connected -vertex Eulerian digraph is Hamiltonian, and provide an infinite famil…
Multidimensional Scaling: Approximation and Complexity
Erik Demaine, Adam Hesterberg, Frederic Koehler +2
Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in th…
Maximum spread of graphs and bipartite graphs
Jane Breen, Alex W. N. Riasanovsky, Michael Tait +1
Given any graph , the (adjacency) spread of is the maximum absolute difference between any two eigenvalues of the adjacency matrix of . In this paper, we resolve a pair o…
Regarding two conjectures on clique and biclique partitions
Dhruv Rohatgi, John C. Urschel, Jake Wellens
For a graph , let denote the minimum number of cliques of needed to cover the edges of exactly once. Similarly, let denote the minimum number of bicliq…
Uniform Error Estimates for the Lanczos Method
John C. Urschel
The Lanczos method is one of the most powerful and fundamental techniques for solving an extremal symmetric eigenvalue problem. Convergence-based error estimates depend heavily on…
Discrete Trace Theorems and Energy Minimizing Spring Embeddings of Planar Graphs
John C. Urschel, Ludmil T. Zikatanov
Tutte's spring embedding theorem states that, for a three-connected planar graph, if the outer face of the graph is fixed as the complement of some convex region in the plane, and…
Testing Gap k-planarity is NP-complete
John C. Urschel, Jake Wellens
For all , we show that deciding whether a graph is -planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show…
Rates of estimation for determinantal point processes
Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet +1
Determinantal point processes (DPPs) have wide-ranging applications in machine learning, where they are used to enforce the notion of diversity in subset selection problems. Many e…
Learning Determinantal Point Processes with Moments and Cycles
John Urschel, Victor-Emmanuel Brunel, Ankur Moitra +1
Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where retu…
Maximum likelihood estimation of determinantal point processes
Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet +1
Determinantal point processes (DPPs) have wide-ranging applications in machine learning, where they are used to enforce the notion of diversity in subset selection problems. Many e…
Constructing Frequency Domains on Graphs in Near-Linear Time
John C. Urschel, Wenfang Xu, Ludmil T. Zikatanov
Analysis of big data has become an increasingly relevant area of research, with data often represented on discrete networks both constructed and organic. While for structured domai…
On the Approximation of Laplacian Eigenvalues in Graph Disaggregation
Xiaozhe Hu, John C. Urschel, Ludmil T. Zikatanov
Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple…
On the Maximal Error of Spectral Approximation of Graph Bisection
John C. Urschel, Ludmil T. Zikatanov
Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a…
A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians
John C. Urschel, Xiaozhe Hu, Jinchao Xu +1
In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smalle…