All reports by Author Euiwoong Lee:

__
TR19-093
| 15th July 2019
__

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari#### Improved 3LIN Hardness via Linear Label Cover

__
TR18-097
| 15th May 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Approximating Operator Norms via Generalized Krivine Rounding

__
TR18-037
| 21st February 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Inapproximability of Matrix $p \rightarrow q$ Norms

__
TR16-185
| 18th November 2016
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

__
TR15-155
| 22nd September 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Nearly Optimal NP-Hardness of Unique Coverage

__
TR15-105
| 21st June 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Towards a Characterization of Approximation Resistance for Symmetric CSPs

__
TR14-043
| 2nd April 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

__
TR14-006
| 16th January 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Inapproximability of Feedback Vertex Set for Bounded Length Cycles

Revisions: 1

__
TR13-125
| 11th September 2013
__

Venkatesan Guruswami, Euiwoong Lee#### Complexity of approximating CSP with Balance / Hard Constraints

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

Venkatesan Guruswami, Euiwoong Lee

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to $1$ with some probability $\alpha$ achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>>

Venkatesan Guruswami, Euiwoong Lee

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation ... more >>>

Venkatesan Guruswami, Euiwoong Lee

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>