Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Elchanan Mossel:

TR16-174 | 7th November 2016
Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

Linear Sketching over $\mathbb F_2$

Revisions: 5 , Comments: 2

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

TR12-016 | 24th February 2012
Anindya De, Elchanan Mossel

Explicit Optimal hardness via Gaussian stability results

Revisions: 3

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... more >>>

TR08-009 | 7th December 2007
Per Austrin, Elchanan Mossel

Approximation Resistant Predicates From Pairwise Independence

We study the approximability of predicates on $k$ variables from a
domain $[q]$, and give a new sufficient condition for such predicates
to be approximation resistant under the Unique Games Conjecture.
Specifically, we show that a predicate $P$ is approximation resistant
if there exists a balanced pairwise independent distribution over
more >>>

TR05-101 | 20th September 2005
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

On epsilon-Biased Generators in NC0

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there is always a
distinguisher; ... more >>>

ISSN 1433-8092 | Imprint