Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

\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 >>>

TR12-074 | 12th June 2012
Venkatesan Guruswami, Yuan Zhou

Approximating Bounded Occurrence Ordering CSPs

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 >>>

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

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.

\item ... more >>>

TR09-130 | 1st December 2009
Ryan O'Donnell, YI WU, Yuan Zhou

Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

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 >>>

ISSN 1433-8092 | Imprint