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

__
TR12-016
| 24th February 2012
__

Anindya De, Elchanan Mossel#### Explicit Optimal hardness via Gaussian stability results

Revisions: 3

__
TR08-009
| 7th December 2007
__

Per Austrin, Elchanan Mossel#### Approximation Resistant Predicates From Pairwise Independence

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

__
TR05-039
| 13th April 2005
__

Irit Dinur, Elchanan Mossel, Oded Regev#### Conditional Hardness for Approximate Coloring

__
TR03-043
| 14th May 2003
__

Elchanan Mossel, Amir Shpilka, Luca Trevisan#### On epsilon-Biased Generators in NC0

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

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

Anindya De, Elchanan Mossel

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

Per Austrin, Elchanan Mossel

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

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

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

Irit Dinur, Elchanan Mossel, Oded Regev

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

Elchanan Mossel, Amir Shpilka, Luca Trevisan

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