Euiwoong Lee

activity

20142023

most citedSum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

14 citations · 51 across the 29 of their papers we have counts for

collaborators

Showing 2016 · cs.CCShow all

2 papers · 2 filters

cs.CC2016★ 10 cited

Improved Hardness for Cut, Interdiction, and Firefighter Problems

Euiwoong Lee

We study variants of the classic $s$ - $t$ cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant $k \geq 2$ and…

cs.CC2016★ 14 cited

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

For an $n$ -variate order- $d$ tensor $A$ , define $A_{m a x} := sup_{∥ x ∥_{2} = 1} ⟨ A, x^{\otimes d} ⟩$ to be the maximum value taken by the tensor on the unit sphere…