Let be an undirected graph with maximum degree and vertex conductance . We show that there exists a symmetric, stochastic matrix , with off-diagonal entries supported on , whose spectral gap satisfies
Our bound is optimal under the Small Set Expansion Hypothesis, and answers a question of Olesker-Taylor and Zanetti, who obtained such a result with replaced by .
In order to obtain our result, we show how to embed a negative-type semi-metric defined on into a negative-type semi-metric supported in , such that the (fractional) matching number of the weighted graph is approximately equal to that of .
Revised:
Accepted:
Published online:
Vishesh Jain 1; Huy Pham 2; Thuy-Duong Vuong 3
@article{CRMATH_2023__361_G5_869_0, author = {Vishesh Jain and Huy Pham and Thuy-Duong Vuong}, title = {Dimension reduction for maximum matchings and the {Fastest} {Mixing} {Markov} {Chain}}, journal = {Comptes Rendus. Math\'ematique}, pages = {869--876}, publisher = {Acad\'emie des sciences, Paris}, volume = {361}, year = {2023}, doi = {10.5802/crmath.447}, language = {en}, }
TY - JOUR AU - Vishesh Jain AU - Huy Pham AU - Thuy-Duong Vuong TI - Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain JO - Comptes Rendus. Mathématique PY - 2023 SP - 869 EP - 876 VL - 361 PB - Académie des sciences, Paris DO - 10.5802/crmath.447 LA - en ID - CRMATH_2023__361_G5_869_0 ER -
Vishesh Jain; Huy Pham; Thuy-Duong Vuong. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain. Comptes Rendus. Mathématique, Volume 361 (2023), pp. 869-876. doi : 10.5802/crmath.447. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.447/
[1] Dimensionality reduction: beyond the Johnson-Lindenstrauss bound, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, SIAM (2011), pp. 868-887 | DOI | Zbl
[2] Fastest mixing Markov chain on graphs with symmetries, SIAM J. Optim., Volume 20 (2009) no. 2, pp. 792-819 | DOI | Zbl
[3] Fastest mixing Markov chain on a graph, SIAM Rev., Volume 46 (2004) no. 4, pp. 667-689 | DOI | Zbl
[4] The Johnson–Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction (2022) (https://arxiv.org/abs/2205.00371)
[5] Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, 1997 | DOI
[6] Semidefinite programming in combinatorial optimization, Math. Program., Volume 79 (1997) no. 1, pp. 143-161 | DOI | Zbl
[7] Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues (2022) (https://arxiv.org/abs/2203.06168)
[8] Optimality of the Johnson-Lindenstrauss lemma, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE (2017), pp. 633-638 | DOI
[9] The complexity of approximating vertex expansion, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE (2013), pp. 360-369 | DOI
[10] Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019), pp. 1027-1038 | DOI | Zbl
[11] Geometric Bounds on the Fastest Mixing Markov Chain, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)
[12] Graph expansion and the unique games conjecture, Proceedings of the forty-second ACM symposium on Theory of computing (2010), pp. 755-764 | DOI | Zbl
[13] Bounding fastest mixing, Electron. Commun. Probab., Volume 10 (2005), pp. 282-296 | Zbl
Cited by Sources:
Comments - Policy