Att utforma distribuerade och skalbara algoritmer för att förbättra nätverksanslutningen är ett centralt ämne i peer-to-peer-nätverk. I detta dokument fokuserar vi på följande välkända problem: med tanke på ett n-node d-regelbundet nätverk för d =  på (log n), vill vi utforma en decentraliserad, lokal algoritm som omvandlar grafen till en som har goda konnektivitetsegenskaper (låg diameter, expansion, etc.) utan att påverka grafens gleshet. Därför införde Mahlmann och Schindelhauer den slumpmässiga "flipp" omvandlingen, där i varje steg, ett slumpmässigt par hörn som har en kant bestämmer sig för att "svepa en granne". De förmodade att utföra O(nd) sådana flips på måfå skulle konvertera någon ansluten d-regelbunden graf till en d-regelbunden expander graf, med hög sannolikhet. Den mest kända övre gränsen för antalet steg är dock ungefär O(n 17 d 23 ), som erhålls genom en känslig Markov kedja jämförelse argument. Vårt huvudsakliga resultat är att bevisa att en naturlig omedelbarion av den slumpmässiga flip producerar en expander i som mest O(n 2 d 2 log n) steg, med hög sannolikhet. Vårt argument använder en potential-funktionsanalys baserad på matrisen exponentiellt, tillsammans med de senaste vackra resultaten på den högre ordningen Cheeger ojämlikhet i grafer. Vi visar också att vår teknik kan användas för att analysera en annan välstuderad slumpmässig process känd som 'random switch', och visa att den producerar en expander i O(nd) steg med hög sannolikhet. - Vad är det för fel på dig?
I REF, Allen-Zhu et al. Visa ett enkelt och lokalt protokoll som, med början från alla anslutna deregular anslutna grafen med d =  på (log n), returnerar en d-regelbunden expander.
Expanders via Local Edge Flips
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}