Gary L. Miller

Affiliations:
  • Carnegie Mellon University, Pittsburgh, USA


According to our database1, Gary L. Miller authored at least 145 papers between 1976 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2002, "For contributions to the design and analysis of algorithms in number theory and computational geometry.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser.
CoRR, 2023

2020
Functions that Preserve Manhattan Distances.
CoRR, 2020

Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities.
CoRR, 2020

Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues.
Proceedings of the Approximation, 2019

2018
Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
On Computing Min-Degree Elimination Orderings.
CoRR, 2017

Intrinsic Metrics: Nearest Neighbor and Edge Squared Distances.
CoRR, 2017

2016
Scalable Constrained Clustering: A Generalized Spectral Method.
CoRR, 2016

ScaleNet: a literature-based model of scale insect biology and systematics.
Database J. Biol. Databases Curation, 2016

Routing under balance.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Geometric median in nearly linear time.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

An Empirical Study of Cycle Toggling Based Laplacian Solvers.
Proceedings of the 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, 2016

Simple and Scalable Constrained Clustering: a Generalized Spectral Method.
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016

2015
Approximating Nearest Neighbor Distances.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Improved Parallel Algorithms for Spanners and Hopsets.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

The Revolution in Graph Theoretic Optimization Problems.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

2014
Approaching Optimality for Solving SDD Linear Systems.
SIAM J. Comput., 2014

Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs.
Theory Comput. Syst., 2014

A New Approach to Output-Sensitive Construction of Voronoi Diagrams and Delaunay Triangulations.
Discret. Comput. Geom., 2014

A Generalized Cheeger Inequality.
CoRR, 2014

Stretching Stretch.
CoRR, 2014

The Role of Public Comprehensive Universities in Closing the Innovation Deficit.
Computer, 2014

Solving SDD linear systems in nearly <i>m</i>log<sup>1/2</sup><i>n</i> time.
Proceedings of the Symposium on Theory of Computing, 2014

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Parallel Algorithms for Approximate Undirected Shortest Paths in $m\log^{3+α}n$ Work.
CoRR, 2013

Solving large optimization problems using spectral graph theory.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Parallel graph decompositions using random shifts.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Approximate Maximum Flow on Separable Undirected Graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Runtime guarantees for regression problems.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Iterative Row Sampling.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

A fast algorithm for well-spaced points and approximate delaunay graphs.
Proceedings of the Symposium on Computational Geometry 2013, 2013

A new approach to output-sensitive voronoi diagrams and delaunay triangulations.
Proceedings of the Symposium on Computational Geometry 2013, 2013

2012
Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning.
Internet Math., 2012

A New Approach to Output-Sensitive Voronoi Diagrams
CoRR, 2012

Iterative Approaches to Row Sampling
CoRR, 2012

A fast solver for a class of linear systems.
Commun. ACM, 2012

Faster approximate multicommodity flow using quadratically coupled flows.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
Triangle Sparsifiers.
J. Graph Algorithms Appl., 2011

Approximation algorithms for speeding up dynamic programming and denoising aCGH data.
ACM J. Exp. Algorithmics, 2011

Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing.
Comput. Vis. Image Underst., 2011

Electrical Flow Algorithms for Total Variation Minimization
CoRR, 2011

Solving SDD linear systems in time Õ(mlog nlog(1/ε))
CoRR, 2011

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs.
Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

A Nearly-m log n Time Solver for SDD Linear Systems.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Beating the spread: time-optimal point meshing.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Approximate Dynamic Programming for Fast Denoising of aCGH Data
CoRR, 2010

Approaching optimality for solving SDD systems
CoRR, 2010

Approximate centerpoints with proofs.
Comput. Geom., 2010

Hierarchical Diagonal Blocking and Precision Reduction Applied to Combinatorial Multigrid.
Proceedings of the Conference on High Performance Computing Networking, 2010

Topological inference via meshing.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
Approximate Triangle Counting
CoRR, 2009

Size complexity of volume meshes vs. surface meshes.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

DOULION: counting triangles in massive graphs with a coin.
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28, 2009

Approximate center points with proofs.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

The Centervertex Theorem for Wedge Depth.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

2008
Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Linear-Size Meshes.
Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007
Sparse parallel Delaunay mesh refinement.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

A linear work, O(n<sup>1/6</sup>) time, parallel algorithm for solving planar Laplacians.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

SVR: Practical Engineering of a Fast 3D Meshing Algorithm*.
Proceedings of the 16th International Meshing Roundtable, 2007

Size Competitive Meshing Without Large Angles.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Sparse Voronoi Refinement.
Proceedings of the 15th International Meshing Roundtable, 2006

Representing Topological Structures Using Cell-Chains.
Proceedings of the Geometric Modeling and Processing, 2006

Graph Partitioning by Spectral Rounding: Applications in Image Segmentation and Clustering.
Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), 2006

2005
When and why delaunay refinement algorithms work.
Int. J. Comput. Geom. Appl., 2005

Finding effective support-tree preconditioners.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Corrected Laplacians: Closer Cuts and Segmentation with Shape Priors.
Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 2005

2004
Lower bounds for graph embeddings and combinatorial preconditioners.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

A time efficient Delaunay refinement algorithm.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A Bezier-Based Moving Mesh Framework for Simulation with Elastic Membranes.
Proceedings of the 13th International Meshing Roundtable, 2004

A Bézier-based approach to unstructured moving meshes.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Using bistellar flips for rotations in point location structures.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003
When and Why Ruppert's Algorithm Works.
Proceedings of the 12th International Meshing Roundtable, 2003

2002
Fully Incremental 3D Delaunay Refinement Mesh Generation.
Proceedings of the 11th International Meshing Roundtable, 2002

2001
Persistent triangulations Journal of Functional Programming.
J. Funct. Program., 2001

2000
Graph Embeddings and Laplacian Eigenvalues.
SIAM J. Matrix Anal. Appl., 2000

Smoothing and cleaning up slivers.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

A Parallel Dynamic-Mesh Lagrangian Method for Simulation of Flows with Dynamic Interfaces.
Proceedings of the Proceedings Supercomputing 2000, 2000

1999
The Dynamic Parallel Complexity of Computational Circuits.
SIAM J. Comput., 1999

Optimal Coarsening of Unstructured Meshes.
J. Algorithms, 1999

Data Generation for Geometric Algorithms on Non-Uniform Distributions.
Int. J. Comput. Geom. Appl., 1999

The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian.
Comb. Probab. Comput., 1999

Design and Implementation of a Practical Parallel Delaunay Algorithm.
Algorithmica, 1999

Tradeoffs Between Parallelism and Fill in Nested Dissection.
Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999

Estimating Interpolation Error: A Combinatorial Approach.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Redeeming Nested Dissection: Parallelism Implies Fill.
Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, 1999

1998
On the Quality of Spectral Separators.
SIAM J. Matrix Anal. Appl., July, 1998

Geometric Separators for Finite-Element Meshes.
SIAM J. Sci. Comput., 1998

Geometric Mesh Partitioning: Implementation and Experiments.
SIAM J. Sci. Comput., 1998

Control Volume Meshes Using Sphere Packing.
Proceedings of the Solving Irregularly Structured Problems in Parallel, 1998

1997
Moments of Inertia and Graph Separators.
J. Comb. Optim., 1997

Separators for sphere-packings and nearest neighbor graphs.
J. ACM, 1997

Tree-Based Parallel Algorithm Design.
Algorithmica, 1997

Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

The Path Resistance Method for Bounding lambda<sub>2</sub> of a Laplacian.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Parallelizing Elimination Orders with Linear Fill.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Approximating center points with iterative Radon points.
Int. J. Comput. Geom. Appl., 1996

Developing a Practical Projection-Based Parallel Delaunay Algorithm.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Flow in Planar Graphs with Multiple Sources and Sinks.
SIAM J. Comput., 1995

A Deterministic Linear Time Algorithm for Geometric Separators and its Applications.
Fundam. Informaticae, 1995

A Delaunay based numerical method for three dimensions: generation, formulation, and partition.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On the Performance of Spectral Graph Partitioning Methods.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Performance evaluation of a new parallel preconditioner.
Proceedings of IPPS '95, 1995

1993
Approximating Center Points with Iterated Radon Points.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992
A new graph triconnectivity algorithm and its parallelization.
Comb., 1992

A Contraction Procedure for Planar Directed Graphs.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Separator Based Parallel Divide and Conquer in Computational Geometry.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

1991
Parallel Tree Contraction, Part 2: Further Applications.
SIAM J. Comput., 1991

Deterministic Parallel List Ranking.
Algorithmica, 1991

Density Graphs and Separators.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

A Unified Geometric Approach to Graph Separators
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
A Simple Randomized Parallel Algorithm for List-Ranking.
Inf. Process. Lett., 1990

Subtree isomorphism is in random NC.
Discret. Appl. Math., 1990

Separators in Two and Three Dimensions
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Planar Separators and the Euclidean Norm.
Proceedings of the Algorithms, 1990

1989
Parallel Tree Contraction Part 1: Fundamentals.
Adv. Comput. Res., 1989

Constructing Trees in Parallel.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits.
SIAM J. Comput., 1988

An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph.
Inf. Process. Lett., 1988

1987
Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers.
SIAM J. Comput., 1987

An additivity theorem for the genus of a graph.
J. Comb. Theory B, 1987

A Parallel Algorithm for Finding a Separator in Planar Graphs
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Sums of Divisors, Perfect Numbers and Factoring.
SIAM J. Comput., 1986

Finding Small Simple Cycle Separators for 2-Connected Planar Graphs.
J. Comput. Syst. Sci., 1986

Efficient Parallel Evaluation of Straight-line Code and Arithmetric Circuits.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
Solvability by Radicals is in Polynomial Time.
J. Comput. Syst. Sci., 1985

Parallel Tree Contraction and Its Application
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields.
Proceedings of the Advances in Cryptology, 1985

1984
Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
An Asymptotically Optimal Layout for the Shuffle-Exchange Graph.
J. Comput. Syst. Sci., 1983

Isomorphism of Graphs Which are Pairwise k-separable
Inf. Control., 1983

Isomorphism of k-Contractible Graphs. A Generalization of Bounded Valence and Bounded Genus
Inf. Control., 1983

Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus).
Proceedings of the Fundamentals of Computation Theory, 1983

1981
New Layouts for the Shuffle-Exchange Graph (Extended Abstract)
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980
Regular groups of automorphisms of cubic graphs.
J. Comb. Theory B, 1980

Isomorphism Testing for Graphs of Bounded Genus
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Graph Isomorphism, General Remarks.
J. Comput. Syst. Sci., 1979

On Determining the Genus of a Graph in O(v^O(g)) Steps
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978
On the n^log n Isomorphism Technique: A Preliminary Report
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977
On Taking Roots in Finite Fields
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976
Riemann's Hypothesis and Tests for Primality.
J. Comput. Syst. Sci., 1976


  Loading...