Comptes Rendus
Combinatoire, Probabilités
Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
Vishesh Jain1  ; Huy Pham2 ; Thuy-Duong Vuong3
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
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′).

Reçu le :
Révisé le :
Accepté le :
Publié le :
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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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

  • Lap Chi Lau; Kam Chuen Tung; Robert Wang Cheeger inequalities for directed graphs and hypergraphs using reweighted eigenvalues, Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC '23, Orlando, FL, USA, June 20–23, 2023, New York, NY: Association for Computing Machinery (ACM), 2023, pp. 1834-1847 | DOI:10.1145/3564246.3585139 | Zbl:7844715

Cité par 1 document. Sources : zbMATH

Commentaires - Politique