Discrete Poincaré inequalities and universal approximators for random graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908472527814656 |
|---|---|
| author | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| author_facet | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| contents | Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable algorithmic applications. A basic open problem, posed by Jon Kleinberg (2013), asks whether the optimal nonlinear Poincaré constant for maps between two independent $3$-regular random graphs is dimension-free, i.e., independent of vertex-set sizes. We give a complete and affirmative resolution to Kleinberg's problem, also allowing for arbitrary graph degrees. As a corollary, we obtain a stochastic construction of $O(1)\text{-universal}$ approximators for random graphs, answering a question of Mendel and Naor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrete Poincaré inequalities and universal approximators for random graphs Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos Metric Geometry Combinatorics Probability Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable algorithmic applications. A basic open problem, posed by Jon Kleinberg (2013), asks whether the optimal nonlinear Poincaré constant for maps between two independent $3$-regular random graphs is dimension-free, i.e., independent of vertex-set sizes. We give a complete and affirmative resolution to Kleinberg's problem, also allowing for arbitrary graph degrees. As a corollary, we obtain a stochastic construction of $O(1)\text{-universal}$ approximators for random graphs, answering a question of Mendel and Naor. |
| title | Discrete Poincaré inequalities and universal approximators for random graphs |
| topic | Metric Geometry Combinatorics Probability |
| url | https://arxiv.org/abs/2506.17433 |