Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Recovering Communities in Structured Random Graphs
Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random…
cs.DS2023
New SDP Roundings and Certifiable Approximation for Cubic Optimization
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti +1
We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the -dimensional hypercube. In both cases, the resulti…