Comptes Rendus
Combinatorics, Probability theory
Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
Comptes Rendus. Mathématique, Volume 361 (2023), pp. 869-876.

Let G=(V,E) be an undirected graph with maximum degree Δ and vertex conductance Ψ * (G). We show that there exists a symmetric, stochastic matrix P, with off-diagonal entries supported on E, whose spectral gap γ * (P) satisfies

Ψ * (G) 2 /logΔγ * (P)Ψ * (G).

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 logΔ replaced by log|V|.

In order to obtain our result, we show how to embed a negative-type semi-metric d defined on V into a negative-type semi-metric d supported in O(logΔ) , such that the (fractional) matching number of the weighted graph (V,E,d) is approximately equal to that of (V,E,d ).

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/crmath.447

Vishesh Jain 1; Huy Pham 2; Thuy-Duong Vuong 3

1 Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago
2 Department of Mathematics, Stanford University
3 Department of Computer Science, Stanford University
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@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  - 
%0 Journal Article
%A Vishesh Jain
%A Huy Pham
%A Thuy-Duong Vuong
%T Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
%J Comptes Rendus. Mathématique
%D 2023
%P 869-876
%V 361
%I Académie des sciences, Paris
%R 10.5802/crmath.447
%G en
%F CRMATH_2023__361_G5_869_0
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] Yair Bartal; Ben Recht; Leonard J. Schulman 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] Stephen Boyd; Persi Diaconis; Pablo Parrilo; Lin Xiao Fastest mixing Markov chain on graphs with symmetries, SIAM J. Optim., Volume 20 (2009) no. 2, pp. 792-819 | DOI | Zbl

[3] Stephen Boyd; Persi Diaconis; Lin Xiao Fastest mixing Markov chain on a graph, SIAM Rev., Volume 46 (2004) no. 4, pp. 667-689 | DOI | Zbl

[4] Moses Charikar; Erik Waingarten The Johnson–Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction (2022) (https://arxiv.org/abs/2205.00371)

[5] Michel Marie Deza; Monique Laurent Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, 1997 | DOI

[6] Michel X. Goemans Semidefinite programming in combinatorial optimization, Math. Program., Volume 79 (1997) no. 1, pp. 143-161 | DOI | Zbl

[7] Tsz Chiu Kwok; Lap Chi Lau; Kam Chuen Tung Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues (2022) (https://arxiv.org/abs/2203.06168)

[8] Kasper Green Larsen; Jelani Nelson Optimality of the Johnson-Lindenstrauss lemma, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE (2017), pp. 633-638 | DOI

[9] Anand Louis; Prasad Raghavendra; Santosh Vempala The complexity of approximating vertex expansion, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE (2013), pp. 360-369 | DOI

[10] Konstantin Makarychev; Yury Makarychev; Ilya Razenshteyn 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] Sam Olesker-Taylor; Luca Zanetti 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] Prasad Raghavendra; David Steurer 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] Sébastien Roch Bounding fastest mixing, Electron. Commun. Probab., Volume 10 (2005), pp. 282-296 | Zbl

Cited by Sources:

Comments - Policy