Showing 2023Show all
2 papers · 1 filter
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…
cs.CC2023
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari +1
We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case an…