1 citations · 1 across the 8 of their papers we have counts for
5 papers · 1 filter
Rate-optimal community detection near the KS threshold via node-robust algorithms
Jingqiu Ding, Yiding Hua, Kasper Lindberg +2
We study community detection in the \emph{symmetric -stochastic block model}, where nodes are evenly partitioned into clusters with intra- and inter-cluster connection p…
Faster MAX-CUT on Bounded Threshold Rank Graphs
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman +1
We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than , sm…
Hesse's Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, Manuel Wiedmer
Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal sol…
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai, Yiding Hua, David Steurer +1
We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example,…
Low degree conjecture implies sharp computational thresholds in stochastic block model
Jingqiu Ding, Yiding Hua, Lucas Slot +1
We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture…