Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Vishesh Jain; Huy Pham; Thuy-Duong Vuong

doi:10.5802/crmath.447

Combinatoire, Probabilités

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Vishesh Jain ¹ ; Huy Pham ² ; Thuy-Duong Vuong ³

¹ Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago
² Department of Mathematics, Stanford University
³ Department of Computer Science, Stanford University

Comptes Rendus. Mathématique, Volume 361 (2023), pp. 869-876.

Résumé

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 : 2022-03-09
Révisé le : 2022-07-21
Accepté le : 2022-11-22
Publié le : 2023-07-18

DOI : 10.5802/crmath.447

Affiliations des auteurs :

Vishesh Jain ¹ ; Huy Pham ² ; Thuy-Duong Vuong ³

¹ Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago
² Department of Mathematics, Stanford University
³ 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/

Bibliographie
Cité par

[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

Cité par Sources :

Commentaires - Politique