Are there graphs whose shortest path structure requires large edge weights?

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=OItGcQv2pUo


Duration: 0:00
38 views
0

Nicole Wein (University of Michigan)
https://simons.berkeley.edu/talks/nicole-wein-university-michigan-2024-08-02
Sublinear Graph Simplification

I will discuss a new structural graph problem that investigates the relationship between the shortest paths in a graph and the aspect ratio (the ratio of the largest to smallest edge weight in the graph). The question is: can one take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths? I will present upper and lower bounds for this question for undirected graphs, DAGs, and directed graphs.

Joint work with Aaron Bernstein and Greg Bodwin



Other Videos By Simons Institute for the Theory of Computing


2024-10-02Verifiable Data Science via Interactive Proofs
2024-10-02Dana is NOT average
2024-10-02Monotonicity testing, routing, and a theorem of Lehman and Ron
2024-10-02Conditional Sampling for Distribution Testing
2024-09-05Challenges in Making LLMs Safe and Robust
2024-09-04Understanding and Steering Generative AI Systems
2024-08-04On counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
2024-08-04Testing Intersectingness of Uniform Families or how Dana and I intersected
2024-08-04Recent Developments in Testing Bounded-Degree Graphs
2024-08-04Property Testing with Incomplete or Manipulated Inputs
2024-08-01Are there graphs whose shortest path structure requires large edge weights?
2024-07-31Recent Progress on Euclidean Spanners
2024-07-31Space is a latent sequence: A theory of hippocampus and PFC
2024-06-21Robust Equation Discovery and Sparse Sensing with Guarantees
2024-06-21Data is as Data Does: The Influence of Computation on Inference
2024-06-21Some thoughts on ML-based protein engineering
2024-06-21Machine learning models of differential gene expression
2024-06-21Open challenges in AI for molecular design: representation, experimental alignment, and...
2024-06-21Illuminating protein space with generative models
2024-06-21Symmetries in Machine Learning for Materials Science
2024-06-21Large ML potentials for chemistry: generalization, inductive biases, and cancellation of errors