Mathematical connections of some local-to-global expressivity results over geometric graphs and...

on YouTube ↗01h 03m

" summary

Claim: running geometric 1-WL on the complete distance graph reconstructs planar point clouds up to isometry after three rounds in 2D by using barycenter-derived distances and a triangulation/cone propagation algorithm (constructive but inefficient). Tools: multiset message passing, squared‑distance algebra, and rigidity tests (Maxwell‑style rank criterion). Failure: counterexamples in 3D show indistinguishable nonisometric clouds. Open directions: sparse local graphs, density of pathological cases, and links to tensegrity/Delone rigidity.

AI-written summary · about

" chapters (5)

1. 0:00Geometric message passing intro
2. 1:30Problem setup and geometric WL
3. 5:06Key results in 2D/3D point clouds
4. 25:32Open questions and future
5. 56:24Q&A

" related talks

• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 04mHigher-dimensional Expansion of Random Geometric ComplexesTselil Schramm · Structural Results 2023
• 01h 34mAlgorithmic High-Dimensional Geometry IIAlex Andoni · Big Data Boot Camp 2013
• 47mMultiscale Analysis on and of GraphsMauro Maggioni · Spectral Algorithms: From Theory to Practice 2014
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 01h 00mOn Approximating the Covering Radius and Finding Dense Lattice SubspacesDaniel Dadush · Lattices: Geometry, Algorithms and Hardness 2020
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)