59 citations · 104 across the 8 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
math.PR2023
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
Guy Bresler, Chenghao Guo, Yury Polyanskiy
We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted cl…
cs.DS2023
Smoothed Complexity of SWAP in Local Graph Partitioning
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +1
We give the first quasipolynomial upper bound for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width…