7 citations · 14 across the 12 of their papers we have counts for
21 papers
Graph Inference with Effective Resistance Queries
Huck Bennett, Mitchell Black, Amir Nayyeri +1
The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruct…
Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering
Mitchell Black, Lucy Lin, Amir Nayyeri +1
Effective resistance is a distance between vertices of a graph that is both theoretically interesting and useful in applications. We study a variant of effective resistance called…
Comparing Graph Transformers via Positional Encodings
Mitchell Black, Zhengchao Wan, Gal Mishne +2
The distinguishing power of graph transformers is closely tied to the choice of positional encoding: features used to augment the base transformer with information about the graph.…
Topological -metrics
Willow Barkan-Vered, Huck Bennett, Amir Nayyeri
Metric spaces are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships between points .…
An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis
Mitchell Black, William Maxwell, Amir Nayyeri
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of…
Understanding Oversquashing in GNNs through the Lens of Effective Resistance
Mitchell Black, Zhengchao Wan, Amir Nayyeri +1
Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has…
Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
Mitchell Black, Amir Nayyeri
We describe a nearly-linear time algorithm to solve the linear system parameterized by the first Betti number of the complex, where is the 1-Laplacian of a simplic…
ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth
Mitchell Black, Nello Blaser, Amir Nayyeri +1
Given a simplicial complex with simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected sur…
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
Peyman Afshani, Mark de Berg, Kevin Buchin +7
We consider the following surveillance problem: Given a set of sites in a metric space and a set of robots with the same maximum speed, compute a patrol schedule of min…
Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton
Mitchell Black, Amir Nayyeri
We consider two problems on simplicial complexes: the Optimal Bounded Chain Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain Problem asks to find the min…
Generalized max-flows and min-cuts in simplicial complexes
William Maxwell, Amir Nayyeri
We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By view…
Low-stretch spanning trees of graphs with bounded width
Glencora Borradaile, Erin Wolf Chambers, David Eppstein +2
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph with a linear arrange…
Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
Glencora Borradaile, William Maxwell, Amir Nayyeri
We study two optimization problems on simplicial complexes with homology over , the minimum bounded chain problem: given a -dimensional complex embed…
Minimum Cuts in Surface Graphs
Erin W. Chambers, Jeff Erickson, Kyle Fox +1
We describe algorithms to efficiently compute minimum -cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph with $…
A Simple Algorithm for Computing a Cycle Separator
Sariel Har-Peled, Amir Nayyeri
We present a linear time algorithm for computing a cycle separator in a planar graph that is (arguably) simpler than previously known algorithms. Our algorithm builds on, and is so…
Minimum cycle and homology bases of surface embedded graphs
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox +1
We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of…
Towards single face shortest vertex-disjoint paths in undirected planar graphs
Glencora Borradaile, Amir Nayyeri, Farzad Zafarani
Given pairs of terminals in a graph , the min-sum vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ld…
Cost-Effective Conceptual Design Using Taxonomies
Ali Vakilian, Yodsawalai Chodpathumwan, Arash Termehchy +1
It is known that annotating named entities in unstructured and semi-structured data sets by their concepts improves the effectiveness of answering queries over these data sets. As…
Approximating Nearest Neighbor Distances
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller +3
Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes t…
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
Glencora Borradaile, David Eppstein, Amir Nayyeri +1
For an undirected -vertex graph with non-negative edge-weights, we consider the following type of query: given two vertices and in , what is the weight of a minim…
How to Walk Your Dog in the Mountains with No Magic Leash
Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour +1
We describe a -approximation algorithm for computing the homotopic \Frechet distance between two polygonal curves that lie on the boundary of a triangulated topological…