Almost-Optimal Sublinear Additive Spanners @SimonsInstituteTOC

Simons Institute | Almost-Optimal Sublinear Additive Spanners @SimonsInstituteTOC | Uploaded 1 week ago | Updated 11 hours ago
Zihan Tan (Rutgers University)
https://simons.berkeley.edu/talks/zihan-tan-rutgers-university-2024-07-29
Sublinear Graph Simplification

Given an undirected unweighted graph G=(V, E) on n vertices and m edges, a subgraph H is a spanner of G with stretch function f, iff for every pair s, t of vertices, dist_H(s,t) is at most f(dist_G(s,t)). When f(d)=d+o(d), H is called a sublinear additive spanner. In this talk, we show that for any constant integer k＞=2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^{1-1/k}) and O(n^{1+1/(2^{k+1}-1)+o(1)}) edges. The size bound of our spanners almost matches the lower bound proved in [Abboud-Bodwin-Pettie 2017], which holds for any data structure that maintains distances within the same stretch function.

This talk is based on joint work with Tianyi Zhang

$Almost-Optimal Sublinear Additive Spanners Zihan Tan (Rutgers University) https://simons.berkeley.edu/talks/zihan-tan-rutgers-university-2024-07-29 Sublinear Graph Simplification Given an undirected unweighted graph G=(V, E) on n vertices and m edges, a subgraph H is a spanner of G with stretch function f, iff for every pair s, t of vertices, dist_H(s,t) is at most f(dist_G(s,t)). When f(d)=d+o(d), H is called a sublinear additive spanner. In this talk, we show that for any constant integer k＞=2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^{1-1/k}) and O(n^{1+1/(2^{k+1}-1)+o(1)}) edges. The size bound of our spanners almost matches the lower bound proved in [Abboud-Bodwin-Pettie 2017], which holds for any data structure that maintains distances within the same stretch function. This talk is based on joint work with Tianyi Zhang$

Randomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...

Reconsidering Overfitting in the Age of Overparameterized Models

Property Testing with Incomplete or Manipulated Inputs

The Development of Sociality in Language and Thought

The elusive generalization: classical bounds to double descent to grokking

Let’s Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation

Large ML potentials for chemistry: generalization, inductive biases, and cancellation of errors

AI and Emotions: opportunities and challenges (Virtual Talk)