Arrow Research search

Author name cluster

Gary L. Miller

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.

44 papers
1 author row

Possible papers

44

FOCS Conference 2018 Conference Paper

Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm

  • Matthew Fahrbach
  • Gary L. Miller
  • Richard Peng
  • Saurabh Sawlani
  • Junxing Wang
  • Shen Chen Xu

Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in polylogarithmic time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating interleaved queries and updates to this randomized data structure may be of independent interest.

Details

STOC Conference 2016 Conference Paper

Geometric median in nearly linear time

  • Michael B. Cohen
  • Yin Tat Lee
  • Gary L. Miller
  • Jakub Pachocki
  • Aaron Sidford

In this paper we provide faster algorithms for solving the geometric median problem: given n points in 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 a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O ( d · n 4/3 є −8/3 ) by Chin et. al, Õ( d expє −4 logє −1 ) by Badoiu et. al, O ( nd + poly ( d ,є −1 )) by Feldman and Langberg, and the polynomial running time of O (( nd ) O (1) log1/є) by Parrilo and Sturmfels and Xue and Ye.

Details

STOC Conference 2016 Conference Paper

Routing under balance

  • Alina Ene
  • Gary L. Miller
  • Jakub Pachocki
  • Aaron Sidford

We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut S ⊆ V , the total weight of edges going from S to V ∖ S is within factor α of the total weight of edges going from V ∖ 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/є)).

Details

SODA Conference 2014 Conference Paper

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

  • Michael B. Cohen
  • Brittany Terese Fasy
  • Gary L. Miller
  • Amir Nayyeri
  • Richard Peng
  • Noel Walkington

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ 3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

Details

STOC Conference 2014 Conference Paper

Solving SDD linear systems in nearly m log 1/2 n time

  • Michael B. Cohen
  • Rasmus Kyng
  • Gary L. Miller
  • Jakub Pachocki
  • Richard Peng
  • Anup B. Rao
  • Shen Chen Xu

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non-zero entries to a relative error of ε in O ( m log 1/2 n log c n log(1/ ε )) time. Our approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows.

Details

SODA Conference 2013 Conference Paper

Approximate Maximum Flow on Separable Undirected Graphs

  • Gary L. Miller
  • Richard Peng

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 -vertex separator structure, our algorithm finds an 1 − ∊ approximate maximum flow in time Õ ( 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.

Details

FOCS Conference 2013 Conference Paper

Iterative Row Sampling

  • Mu Li
  • Gary L. Miller
  • Richard Peng

There has been significant interest and progress recently in algorithms that solve regression problems involving tall and thin matrices in input sparsity time. Given a n * d matrix where n ≥ d, these algorithms find an approximation with fewer rows, allowing one to solve a poly(d) sized problem instead. In practice, the best performances are often obtained by invoking these routines in an iterative fashion. We show these iterative methods can be adapted to give theoretical guarantees comparable to and better than the current state of the art. Our approaches are based on computing the importances of the rows, known as leverage scores, in an iterative manner. We show that alternating between computing a short matrix estimate and finding more accurate approximate leverage scores leads to a series of geometrically smaller instances. This gives an algorithm whose runtime is input sparsity plus an overhead comparable to the cost of solving a regression problem on the smaller approximation. Our results build upon the close connection between randomized matrix algorithms, iterative methods, and graph sparsification.

Details

STOC Conference 2013 Conference Paper

Solving large optimization problems using spectral graph theory

  • Gary L. Miller

Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is a nearly linear time solver for Symmetric Diagonally Dominate systems (SDD). This seemingly restrictive class of systems has received much interest in the last 15 years. Both algorithm design theory and practical implementations have made substantial progress. There is also a growing number of problems that can be efficiently solved using SDD solvers including: image segmentation, image denoising, finding solutions to elliptic equations, computing maximum flow in a graph, graph sparsification, and graphics. All these examples can be viewed as special case of convex optimization problems.

Details

STOC Conference 2012 Conference Paper

Faster approximate multicommodity flow using quadratically coupled flows

  • Jonathan A. Kelner
  • Gary L. Miller
  • Richard Peng

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 maximum weighted multicommodity flow problem in time O(m 4/3 poly(k,ε -1 )).

Details

FOCS Conference 2011 Conference Paper

A Nearly-m log n Time Solver for SDD Linear Systems

  • Ioannis Koutis
  • Gary L. Miller
  • Richard Peng

We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an n×n symmetric diagonally dominant matrix A with m non-zero entries and a vector b such that Ax̅ = b for some (unknown) vector x̅, our algorithm computes a vector x such that ∥x-x̅∥ A ≤ϵ∥x̅∥ A 1 in time Õ (m log n log (1/ϵ)) 2. 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 Õ (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.

Details

SODA Conference 2011 Conference Paper

Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition

  • Gary L. Miller
  • Richard Peng
  • Russell Schwartz
  • Charalampos E. Tsourakakis

We consider the problem of approximating a signal P with another signal F consisting of a few piecewise constant segments. This problem arises naturally in applications including databases (e. g. , histogram construction), speech recognition, computational biology (e. g. , denoising aCGH data) and many more. Specifically, let P = (P 1, P 2, …, P n ), P i ∊ ℝ for all i, be a signal and let C be a constant. Our goal is to find a function F: [ n ] → ℝ which optimizes the following objective function: The above optimization problem reduces to solving the following recurrence, which can be done using dynamic programming in O ( n 2 ) time: This recurrence arises naturally in several applications where one wants to approximate a given signal P with a signal F which ideally consists of few piecewise constant segments. Such applications include histogram construction in databases, determining DNA copy numbers in cancer cells from micro-array data, speech recognition, data mining and many others. In this work we present two new techniques for optimizing dynamic programming that can handle cost functions not treated by other standard methods. The basis of our first algorithm is the definition of a constant-shifted variant of the objective function that can be efficiently approximated using state of the art methods for range searching. Our technique approximates the optimal value of our objective function within additive ∊ error and runs in time, where δ is an arbitrarily small positive constant and. The second algorithm we provide solves a similar recurrence that's within a multiplicative factor of (1+∊) and runs in O ( n log n /∊). The new technique introduced by our algorithm is the decomposition of the initial problem into a small (logarithmic) number of Monge optimization subproblems which we can speed up using existing techniques.

Details

FOCS Conference 2010 Conference Paper

Approaching Optimality for Solving SDD Linear Systems

  • Ioannis Koutis
  • Gary L. Miller
  • Richard Peng

We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier G with n-1+m/k edges, such that the condition number of G with G is bounded above by Õ(k log 2 n), with probability 1-p. The algorithm runs in time Õ((m log n + n log n) log(1/p)). As a result, we obtain an algorithm that on input of an n × n symmetric diagonally dominant matrix A with m non-zero entries and a vector b, computes a vector x satisfying ||x-A + b||A + b||A, in expected time Õ(m log 2 n log(1/ϵ)). The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.

Details

FOCS Conference 1997 Conference Paper

Parallelizing Elimination Orders with Linear Fill

  • Claudson F. Bornstein
  • Bruce M. Maggs
  • Gary L. Miller
  • R. Ravi 0001

This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. In general, the input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an order with height at most O(log/sup 3/ n) times optimal, fill at most O(m), and work at most O(W*(G)), where W*(G) is the minimum possible work over all elimination orders for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Details

FOCS Conference 1991 Conference Paper

A Unified Geometric Approach to Graph Separators

  • Gary L. Miller
  • Shang-Hua Teng
  • Stephen A. Vavasis

A class of graphs called k-overlap graphs is proposed. Special cases of k-overlap graphs include planar graphs, k-nearest neighbor graphs, and earlier classes of graphs associated with finite element methods. A separator bound is proved for k-overlap graphs embedded in d dimensions. The result unifies several earlier separator results. All the arguments are based on geometric properties of embedding. The separator bounds come with randomized linear-time and randomized NC algorithms. Moreover, the bounds are the best possible up to the leading term. >

Details

FOCS Conference 1989 Conference Paper

Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract)

  • Gary L. Miller
  • Joseph Naor

Given a planar network with many sources and sinks, the problem of computing the maximum flow from the sources to the sinks is investigated. An algorithm that runs in O(log/sup 2/n) time using O(n/sup 1. 5/) processors on an exclusive-read-exclusive-write parallel random-access machine (EREW PRAM) is obtained, when the amount of flow (demand) at each source and sink is assumed as input. When the demands are unknown, the problem remains open. However, in the special case in which the sources and sinks are all on one face (and the demands unknown), an algorithm that computes the maximum flow with time complexity O(log/sup 3/n log log n) using O(n/sup 1. 5/) processors is given. The results also hold for more general networks, namely, when the edge capacities have both lower and upper bounds. >

Details

FOCS Conference 1987 Conference Paper

A Parallel Algorithm for Finding a Separator in Planar Graphs

  • Hillel Gazit
  • Gary L. Miller

We present a randomized parallel algorithm for finding a simple cycle separator in a planar graph. The size of the separator is O(√n) and it separates the graph so that the largest part contains at most 2/8 · n vertices. Our algorithm takes T = O(log2(n)) time and P = O(n + f1+ε) processors, where n is the number of vertices, f is the number of faces and ε is any positive constant. The algorithm is based on the solution of Lipton and Tarjan [8] for the sequential case which takes O(n) time. Combining our algorithm with the Pan and Reif [12] algorithm, enables us to find a BFS of planar graph in time O(log3(n)) using n1. 5/log(n) processors. Using a variation of our algorithm we can construct a simple cycle separator of size O(d · √f) were d is maximum face size.

Details

STOC Conference 1987 Conference Paper

Dynamic Parallel Complexity of Computational Circuits

  • Gary L. Miller
  • Shang-Hua Teng

The dynamic parallel complexity of general computational circuits (defined in introduction) is discussed. We exhibit some relationships between parallel circuit evaluation and some uniform closure properties of a certain class of unary functions and present a systematic method for the design of processor efficient parallel algorithms for circuit evaluation. Using this method: (1) we improve the algorithm for parallel Boolean circuit evaluation; (2) we give a nontrivial upper bound for parallel min-max-plus circuit evaluation; (3) we partially answer the first open question raised in [MiRK85] by showing that all circuits over finite noncommutative semi-ring and circuits over infinite non-commutative semi-ring which has finite dimension over a commutative semi-ring can be evaluated in polylogarithmic time in its size and degree using M ( n ) processors. Moreover, we develop a theory for determining closure properties of certain classes of unary functions.

Details

FOCS Conference 1984 Conference Paper

Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers

  • Ravindran Kannan
  • Gary L. Miller
  • Larry Rudolph

The advent of practical parallel processors has caused a reexamination of many existing algorithms with the hope of discovering a parallel implementation. One of the oldest and best known algorithms is Euclid's algorithm for computing the greatest common divisor (GCD). In this paper we present a parallel algorithm to compute the GCD of two integers. The two salient features of the algorithm are: the observation based on the pigeon hole principle that we can easily find an integer combination of the two integers A and B which has fewer bits than n and the idea of working in phases so as to perform arithmetics on n-bit integers only once every phase, the more frequent operations being performed on O(log/sup 2/n)-bit integers. It appears that yet another approach is needed if the GCD is to be computed in poly-log parallel time.

Details

STOC Conference 1983 Conference Paper

Solvability by Radicals is in Polynomial Time

  • Susan Landau 0001
  • Gary L. Miller

Every high school student knows how to express the roots of a quadratic equation in terms of radicals; what is less well-known is that this solution was found by the Babylonians a millenia and a half before Christ [Ne]. Three thousand years elapsed before European mathematicians determined how to express the roots of cubic and quartic equations in terms of radicals, and there they stopped, for their techniques did not extend. Lagrange published a treatise which discussed why the methods that worked for polynomials of degree less than five did not work for quintic polynomials [Lag],

Details

STOC Conference 1980 Conference Paper

Isomorphism Testing for Graphs of Bounded Genus

  • Gary L. Miller

We present an algorithm which determines isomorphism of graphs in v O(g) steps where v is the number of vertices and g is the genus of the graphs. In [FMR 79] an algorithm was presented for embedding graph on surfaces of genus g in v O(g) steps. Here we show how to extend this algorithm to isomorphism testing for graphs of small genus. This result is noteworthy for at least two reasons. First, this extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces. Second, this gives one of the few known natural decompositions of the isomorphism problem into an infinite hierarchy of problems P o ,P 1 ,... such that isomorphism testing of problems in P 1 is decidable in time v O(i) .

Details

STOC Conference 1979 Conference Paper

On Determining the Genus of a Graph in O(v^O(g)) Steps

  • I. S. Filotti
  • Gary L. Miller
  • John H. Reif

In this paper we present an algorithm which on input a graph G and a positive integer g finds an embedding of G on a surface on genius g, if such an embedding exists. This algorithm runs in (v) O(g) steps where v is the number of vertices of G.

Details

STOC Conference 1977 Conference Paper

Graph Isomorphism, General Remarks

  • Gary L. Miller

An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative computational complexity of generalizations and restrictions of the graph isomorphism problem. In the first Section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say Tarski models from logic). Then we show that valence seems to be important. Finally we analyze symmetric cubic graphs.

Details
v2026.09.13