All reports by Author Yuan Zhou:

__
TR13-114
| 24th August 2013
__

Parikshit Gopalan, Salil Vadhan, Yuan Zhou#### Locally Testable Codes and Cayley Graphs

Revisions: 1

__
TR12-074
| 12th June 2012
__

Venkatesan Guruswami, Yuan Zhou#### Approximating Bounded Occurrence Ordering CSPs

__
TR10-063
| 12th April 2010
__

Venkatesan Guruswami, Yuan Zhou#### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

__
TR09-130
| 1st December 2009
__

Ryan O'Donnell, YI WU, Yuan Zhou#### Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

Parikshit Gopalan, Salil Vadhan, Yuan Zhou

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ...
more >>>

Venkatesan Guruswami, Yuan Zhou

A theorem of HÃ¥stad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>

Venkatesan Guruswami, Yuan Zhou

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em

near-satisfiable} instance.

\begin{enumerate}

\item ...
more >>>

Ryan O'Donnell, YI WU, Yuan Zhou

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>