BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gary Miller

Gary Miller appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational GeometryComputer VisionDiscrete Mathematicsmath.FAmath.OCSocial and Information Networks

Catalog footprint

What is connected

10works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

Exact Computation of a Manifold Metric, via Lipschitz Embeddings and Shortest Paths on a Graph

Data-sensitive metrics adapt distances locally based the density of data points with the goal of aligning distances and some notion of similarity. In this paper, we give the first exact algorithm for computing a data-sensitive metric called the nearest neighbor metric. In fact, we prove the surprising result that a previously published $3$-approximation is an exact algorithm. The nearest neighbor metric can be viewed as a special case of a density-based distance used in machine learning, or it can be seen as an example of a manifold metric. Previous computational research on such metrics despaired of computing exact distances on account of the apparent difficulty of minimizing over all continuous paths between a pair of points. We leverage the exact computation of the nearest neighbor metric to compute sparse spanners and persistent homology. We also explore the behavior of the metric built from point sets drawn from an underlying distribution and consider the more general case of inputs that are finite collections of path-connected compact sets. The main results connect several classical theories such as the conformal change of Riemannian metrics, the theory of positive definite functions of Schoenberg, and screw function theory of Schoenberg and Von Neumann. We develop novel proof techniques based on the combination of screw functions and Lipschitz extensions that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Empirical Study of Cycle Toggling Based Laplacian Solvers

We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solution to this linear system through a sequence of flow adjustments along cycles. We study both data structure oriented and recursive methods for handling these adjustments. The primary difficulty faced by this approach, updating and querying long cycles, motivated us to study an important special case: instances where all cycles are formed by fundamental cycles on a length $n$ path. Our methods demonstrate significant speedups over previous implementations, and are competitive with standard numerical routines.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Geometric Median in Nearly Linear Time

In this paper we provide faster algorithms for solving the geometric median problem: given $n$ points in $\mathbb{R}^{d}$ compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite an abundance of research the previous fastest algorithms for computing a $(1+ε)$-approximate geometric median were $O(d\cdot n^{4/3}ε^{-8/3})$ by Chin et. al, $\tilde{O}(d\exp{ε^{-4}\logε^{-1}})$ by Badoiu et. al, $O(nd+\mathrm{poly}(d,ε^{-1})$ by Feldman and Langberg, and $O((nd)^{O(1)}\log\frac{1}ε)$ by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute a $(1+ε)$-approximate geometric median in time $O(nd\log^{3}\frac{1}ε)$ and $O(dε^{-2})$. While our $O(dε^{-2})$ is a fairly straightforward application of stochastic subgradient descent, our $O(nd\log^{3}\frac{1}ε)$ time algorithm is a novel long step interior point method. To achieve this running time we start with a simple $O((nd)^{O(1)}\log\frac{1}ε)$ time interior point method and show how to improve it, ultimately building an algorithm that is quite non-standard from the perspective of interior point literature. Our result is one of very few cases we are aware of outperforming traditional interior point theory and the only we are aware of using interior point methods to obtain a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time. We hope our work leads to further improvements in this line of research.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Routing under Balance

We introduce the notion of balance for directed graphs: a weighted directed graph is $α$-balanced if for every cut $S \subseteq V$, the total weight of edges going from $S$ to $V\setminus S$ is within factor $α$ of the total weight of edges going from $V\setminus S$ to $S$. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with $α= 1$) and residual graphs of $(1+ε)$-approximate undirected maximum flows (with $α=O(1/ε)$). We use the notion of balance to give a more fine-grained understanding of several well-studied routing questions that are considerably harder in directed graphs. We first revisit oblivious routings in directed graphs. Our main algorithmic result is an oblivious routing scheme for single-source instances that achieve an $O(α\cdot \log^3 n / \log \log n)$ competitive ratio. In the process, we make several technical contributions which may be of independent interest. In particular, we give an efficient algorithm for computing low-radius decompositions of directed graphs parameterized by balance. We also define and construct low-stretch arborescences, a generalization of low-stretch spanning trees to directed graphs. On the negative side, we present new lower bounds for oblivious routing problems on directed graphs. We show that the competitive ratio of oblivious routing algorithms for directed graphs is $Ω(n)$ in general; this result improves upon the long-standing best known lower bound of $Ω(\sqrt{n})$ given by Hajiaghayi, Kleinberg, Leighton and Räcke in 2006. We also show that our restriction to single-source instances is necessary by showing an $Ω(\sqrt{n})$ lower bound for multiple-source oblivious routing in Eulerian graphs. We also give a fast algorithm for the maximum flow problem in balanced directed graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scalable Constrained Clustering: A Generalized Spectral Method

We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Generalized Cheeger Inequality

The generalized conductance $ϕ(G,H)$ between two graphs $G$ and $H$ on the same vertex set $V$ is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_H(S,\bar{S})}, $$ where $cap_G(S,\bar{S})$ is the total weight of the edges crossing from $S$ to $\bar{S}=V-S$. We show that the minimum generalized eigenvalue $λ(L_G,L_H)$ of the pair of Laplacians $L_G$ and $L_H$ satisfies $$ λ(L_G,L_H) \geq ϕ(G,H) ϕ(G)/8, $$ where $ϕ(G)$ is the usual conductance of $G$. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to $λ(L_G,L_H)$. The inequality complements a recent proof that $ϕ(G)$ cannot be replaced by $Θ(ϕ(G,H))$ in the above inequality, unless the Unique Games Conjecture is false.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximate Maximum Flow on Separable Undirected Graphs

We present faster algorithms for approximate maximum flow in undirected graphs with good separator structures, such as bounded genus, minor free, and geometric graphs. Given such a graph with $n$ vertices, $m$ edges along with a recursive $\sqrt{n}$-vertex separator structure, our algorithm finds an $1-ε$ approximate maximum flow in time $\tilde{O}(m^{6/5} \poly{ε^{-1}})$, ignoring poly-logarithmic terms. Similar speedups are also achieved for separable graphs with larger size separators albeit with larger run times. These bounds also apply to image problems in two and three dimensions. Key to our algorithm is an intermediate problem that we term grouped $L_2$ flow, which exists between maximum flows and electrical flows. Our algorithm also makes use of spectral vertex sparsifiers in order to remove vertices while preserving the energy dissipation of electrical flows. We also give faster spectral vertex sparsification algorithms on well separated graphs, which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows

The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a $1-ε$ approximation to the multicommodity flow problem on graphs is a well-studied problem. In this paper we present an adaptation of recent advances in single-commodity flow algorithms to this problem. As the underlying linear systems in the electrical problems of multicommodity flow problems are no longer Laplacians, our approach is tailored to generate specialized systems which can be preconditioned and solved efficiently using Laplacians. Given an undirected graph with m edges and k commodities, we give algorithms that find $1-ε$ approximate solutions to the maximum concurrent flow problem and the maximum weighted multicommodity flow problem in time $\tilde{O}(m^{4/3}\poly(k,ε^{-1}))$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Runtime Guarantees for Regression Problems

We study theoretical runtime guarantees for a class of optimization problems that occur in a wide variety of inference problems. these problems are motivated by the lasso framework and have applications in machine learning and computer vision. Our work shows a close connection between these problems and core questions in algorithmic graph theory. While this connection demonstrates the difficulties of obtaining runtime guarantees, it also suggests an approach of using techniques originally developed for graph algorithms. We then show that most of these problems can be formulated as a grouped least squares problem, and give efficient algorithms for this formulation. Our algorithms rely on routines for solving quadratic minimization problems, which in turn are equivalent to solving linear systems. Finally we present some experimental results on applying our approximation algorithm to image processing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A nearly-mlogn time solver for SDD linear systems

We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$ such that $A\bar{x} = b$ for some (unknown) vector $\bar{x}$, our algorithm computes a vector $x$ such that $||{x}-\bar{x}||_A < ε||\bar{x}||_A $ {$||\cdot||_A$ denotes the A-norm} in time $${\tilde O}(m\log n \log (1/ε)).$$ The solver utilizes in a standard way a `preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties. We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time $\tilde{O}(m\log{n})$, a factor of $O(\log{n})$ faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.

0 citations0 reviewsNo code linkedOpen access